Basis for the Column Space This is a please check my proof question.  It's not homework.

Given a matrix $A_{n\times m}$ over some field, and its reduced row echelon form $R_{n\times m}$, show that the columns of $A$ corresponding to the columns in $R$ with pivots form a basis for the column space of $A$, $C(A)$.

And of course if anyone has a more elegant proof I'd be happy to see it.
 A: I think the simplest proof starts with the observation that the product of a matrix and a vector is a linear combination of the columns of the matrix. That is, if the columns of $A$ are $c_1,\dots,c_n$, and $x=(a_1,\dots,a_n)$, then $Ax=a_1c_1+\cdots+a_nc_n$. 
It follows that any particular set $S$ of columns of $A$ will be linearly dependent if and only if there is a solution $x$ to $Ax=0$ with nonzero entries only in the components corresponding to the columns in $S$. But solutions of $Ax=0$ are invariant under elementary row operations (that's why we use elementary row operations to solve systems of equations), so any solution of $Ax=0$ is also a solution of $Rx=0$ (where $R$ is the reduced form of $A$), so it's a linear dependence relation for the corresponding set of columns of $R$. That is, a set of columns of $A$ will be linearly dependent if and only if the same set of columns of $R$ is linearly dependent, and we're done. 
A: Assume $A_{n\times m}\in M^{\mathbb{F}}_{n\times m}$ and that $R_{n\times m}$ is it's reduced row echelon form.  By theorem we know that $rank(A)$ corresponds to the number of rows with pivots and those rows form a basis for the row space. We also know that the number of free variables is $k=m-rank(A)$.  
By writing $Rx=0$ as a system of homogeneous linear equations we can solve for each of the pivots and obtain a basis for the null space of $R$, by theorem.  We know by theorem that $Ax=0$ and $Rx=0$ have the same solution / null space.  
If  $k=0$ then there is only the trivial solution and all the columns of $A$ are linearly independent and form a basis for $C(A)$.  If $k > 0$ then there are $k$ free variables corresponding to the columns of $R$, and thus $A$, without pivots ( since we only performed row operations to obtain $R$ from $A$ ).  
Assume that we've chosen a solution, $x$, from the solution space such that each of the free variables is set to 1.  Then by theorem we can write $Ax=0$ as a linear combination of columns such that the coefficient of each column corresponding to a free variable equals 1.  It is then trivial to solve the equation for each of the these columns and show that it is a linear combination of the remaining $n-1$ columns.  Thus, we have $k$ linearly dependant columns of $A$ corresponding to the columns of $R$ which contained the free variables.  Thus, since by theorem $dimC(A)=rankA$ the remaining $rank(A)$ columns must form a basis for $C(A)$ and these columns must correspond to the columns of $R$ containing pivots.
