# 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.

-

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.

-
+1 for the nice proof. I assume that since $S$ is the set of linearly dependent columns it automatically implies that the remaining columns are linearly independent. – Robert S. Barnes Oct 22 '12 at 17:13
Also, is my proof correct, even if suboptimal? – Robert S. Barnes Oct 22 '12 at 17:14
There is no such thing as the set of linearly dependent columns. What I prove is that any set of columns of $A$ is a linearly dependent set if and only if the corresponding set of columns of $R$ is a linearly dependent set; it follows that any set of columns of $A$ is a linearly independent set if and only if the corresponding set of columns of $R$ is a linearly independent set. I hope someone else will have a good look at your proof. If you're enrolled at a university, maybe someone in the Math Department there would be happy to have a look at it. – Gerry Myerson Oct 22 '12 at 22:00

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.

-