Vector space and linear independence If a generic set  $\{v_1, \dots , v_m\}$ with $m\geq n$ in $\mathbb{R}^n$ generates all the space, does there exist $i_1, \dots , i_n$ such that $\{v_{i_1}, \dots , v_{i_n}\}$ is a basis of $\mathbb{R}^n$ ?
 A: Yes. We use induction over $m$ to prove that:
If m=n, then the set is already a basis. 
If the proposition holds for some $m \ge n$, consider a set $\{v_1,\ldots,v_{m+1}\}$ generating the whole space. Since $m+1 > n$, the vectors are linear dependent, so there exist $\lambda_1,\ldots,\lambda_{m+1} \in \mathbb{R}$, not all equal to zero, with
$$\sum_{i=1}^{m+1}\lambda_iv_i=\vec{0}$$
Since at least one lambda is not zero (wlog $\lambda_{m+1}$), the corresponding $v_{m+1}$ can be expressed via the other members of the set:
$$v_{m+1}=\sum_{i=1}^m \frac{-\lambda_i}{\lambda_{m+1}}v_i$$
That means $\{v_1,\ldots,v_m\}$ is already generating the whole space, and by induction hypothesis, this means some $n$-element subset of it will be a basis of $\mathbb{R}^n$.
A: Since m> n, this set cannot be all "independent".  That means there exist linear combinations of the vectors, not all coefficient 0, equal to 0.  Use those equations to solve for some of the vectors in terms of the others.  If that reduced set is "independent" it is a basis.  If not repeat the procedure.  In any case, there always exist a subset of a spanning set that is a basis.
For example, take (1, 1, 1), (1, 2, 2), (2, 0, 1), and (3, 2, 1) as a set that spans $R^3$.  Since these are four vectors in a three dimensional space they cannot be independent.  There must exist numbers, a, b, c, and d, not all 0, such that a(1, 1, 1)+ b(1, 2, 2)+ c(2, 0, 1)+ d(3, 2, 1)= (0, 0, 0).  We have the three equations a+ b+ 2c+ 3d= 0, a+ 2b+ 2d= 0, and a+ 2b+ c+ d= 0.  From the third, a= -2b- 2d.  Putting that into the first equation, a+ b+ 2c+ 3d= -2b- 2d+ b+ 2c 3d= -b+ 2c- d= 0 so b= 2c- d.  Then a= -2b- 2d= -4c+ 2d- 2d= -4c.  Putting a= -4c and b= 2c- d into the third equation, a+ 2b+ c+ d= -4c+ 4c- 2d+ c+ d= c- 2d= 0. So c= 2d and then a= -4c= -8d and b= 2c- d= 4d- d= 3d.  We have a(1, 1, 1)+ b(1, 2, 2)+ c(2, 0, 1)+ d(3, 2, 1)= -8d(1, 1, 1)+ 3d(1, 2, 2)+ 2d(2, 0, 1)+ d(3, 2, 1)= (0, 0, 0).  Dividing through by d gives -8(1, 1, 1)+ 3(1, 2, 2)+ 2(2, 0, 1)+ (3, 2, 1)= (0, 0, 0) so (3, 2, 1)= 8(1, 1, 1)- 3(1, 2, 2)- 2(2, 0, 1).  That means that, in any linear combination of the original four vectors, we can replace (3, 2, 1) by that combination so we really only need those three vectors.  Those three vectors, from the original set of 4, form a basis.
