Let $V$ be a [[vector space]] over the [[field]] $K$. Let $\left\{v_{1}, \ldots, v_{m}\right\}$ be a [[basis for vector space|basis]] of $V$ over $K$. Let $w_{1}, \ldots, w_{n}$ be elements of $V$, and assume that $n>m$. Then $w_{1}, \ldots, w_{n}$ are [[linearly dependent vectors]] #### Proof Assume the contrary, and allow $w_{1}, \ldots, w_{n}$ to be [[linearly independent vectors]], obviously being non-zero. So a $w_i$ can be written as a [[linear combination]] of $v_1 \ldots v_m$, and we will know at least one of the [[scalar]], let's say $a_i$, will be non-zero, so it will have an [[multiplicative inverse]]. $\begin{aligned} w_{1}&=a_{1} v_{1}+\cdots+ a_i v_i+\cdots+a_{m} v_{m}\\ -a_1v_1&=-w_1+a_2v_2+\cdots +a_mv_m\\ v_1&=\frac{1}{a_1}w_1-\frac{a_2}{a_1}v_2-\cdots-\frac{a_m}{a_1}v_m \end{aligned}$ So $w_1,v_2,\ldots v_m$ generate the same $V$ To apply [[Proof by Induction]], make the assumption that $w_1,\ldots,w_r,v_{r+1},\ldots,v_m$ can generate $V$ as well. $V\ni w_{r+1}$ would have to be representable as a combination of $w_1,\ldots,w_r,v_{r+1},\ldots,v_m$, using scalars $b_{1}, \ldots, b_{r}, c_{r+1}, \ldots, c_{m}\in K$ $w_{r+1}=b_{1} w_{1}+\cdots+b_{r} w_{r}+c_{r+1} v_{r+1}+\cdots+c_{m} v_{m}$ Notice that there must be a non-zero $c$, or else there is dependence in the $w$ set. Since renumbering is allowed, make sure $c_{r+1}$ is non-zero. Solve for $v_{r+1}$ $\begin{aligned} -c_{r+1} v_{r+1}&=&&-w_{r+1}+b_{1} w_{1}+\cdots+b_{r} w_{r}\\&&&+c_{r+2} v_{r+2}+\cdots+c_{m} v_{m} \\ v_{r+1}&=&&\frac{1}{c_{r+1}}w_{r+1}-\frac{b_1}{c_{r+1}}w_1-\ldots-\frac{b_r}{c_{r+1}}w_r\\&&&-\frac{c_{r+2}}{c_{r+1}}v_{r+2}-\ldots-\frac{c_{m}}{c_{r+1}}v_{m} \end{aligned}$ In summary so far: - $w_1,v_2,\ldots v_m$ generate $V$ - $w_1,\ldots,w_r,v_{r+1},\ldots,v_m$ generating $V$ implies that $w_1,\ldots,w_{r+1},v_{r+2},\ldots,v_m$ also generates $V$ - So $w_1,\ldots w_m$ generate $V$ as long as they are independent, which is still being assumed Since the current set $w_1,\ldots, w_m$ is sufficient to generate $V$, the additional vectors, such as $w_n\in V$ would have be representable as a linear combination of $w_1,\ldots, w_m$, this time using $d_{1}, \ldots, d_{m} \in K$. $w_{n}=d_{1} w_{1}+\cdots+d_{m} w_{m}$ Making it clear that the assumtion leads to a contradiction, and that $w_1,\ldots, w_n$ are dependent