Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

2 Answers 2

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.

share|improve this answer

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.

share|improve this answer
    
+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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.