# Elementary row operations do not alter the no. of linearly independent columns.

I came across this theorem from this post on MSE. I wanted to prove this theorem.

Let $A$ be an $m\times n$ matrix. Then the elementary row operations performed on $A$ do not alter the number of linearly independent columns of $A.$

Attempt: Let $A_1,A_2,\dots,A_k$ be the linearly independent columns of $A.$ Then we know that \begin{align} x_1A_1+x_2A_2+ \cdots +x_kA_k=0 \implies x_1=x_2=\cdots=x_k=0. \end{align} Let $C$ be the matrix formed by these linearly independent columns of $A$ and $X=[x_1,x_2,\ldots,x_k]^T.$ Then the above statement can be translated as $$CX=0\implies X=0.$$

Now, any elementary row operation performed on $C,$ can be rendered by pre-multiplying $C$ by an elementary matrix $E$ corresponding to the operation. Now consider the matrix $B=E\,C$. Solving $BX=0$ making use of the fact that elementary matrices are invertible ; pre-multiply by $E^{-1}$ to obtain the trivial solution $X=0.$

Thus columns of $B$ are also linearly independent, i.e. , elementary row operations do not alter the no. of linearly independent columns of $C.$

I think I am just one step short of proving that elementary row operations do not alter the no. of linearly independent columns of $\color{red}{A}.$ But I am not able to complete it. Some help please!

EDIT: I think the proof can be completed along these lines. If I show that the property remains true regardless of the addition of more linearly dependent columns into $C$, I'm done.

So once again consider $C$ as mentioned above. Consider '$p$' $m\times 1$ column vectors $C_1,C_2,\ldots ,C_p$ which is in the span of columns of $C.$ "Embed" these columns into $C$ to form the matrix $D.$ Consider $ED.$ The previous linearly independent columns of $D$ get transformed to a new set of linearly independent columns. We wish to show that $EC_i,1\le i\le p$ is in the span of columns of $EC.$ But this is nothing but solving for $Y$ in $ECY=EC_i.$ Pre-multiplying by $E^{-1}$ we obtain the required solution. Hence $EC_i$ is in the span of columns of $EC.$ Thus the linearly independent columns of $D$ and $ED$ is the same.

• Instead of saying "Let $x_1,\ldots,x_k$ be the linearly independent columns" I might say "Let $x_1,\ldots,x_k$ be linearly independent columns. The word "the" implies that there is only one set of linearly independent columns. If a matrix has four columns $A_1,A_2,A_3,A_4$ it may be that $A_1,A_2,A_3$ are linearly independent and $A_1,A_2,A_4$ are linearly independent and $A_1,A_3,A_4$ are linearly independent and $A_2,A_3,A_4$ are linearly independent. The number of linearly independent columns would be three, but no particular set of three would be "the" linearly independent columns. – Michael Hardy May 25 '17 at 16:05
• One could also mention that any columns that are linearly dependent remain linearly dependent when the row operation is done. That is because of the invertibility of row operations: if the columns after the row operation are linearly independent, then a row operation transforms them back to what they were, and that row operation would preserve linear independence. – Michael Hardy May 25 '17 at 16:14
• @MichaelHardy Thank you for the insightful comments. What if instead I choose to say "maximum number of linearly independent columns"? – Bijesh K.S May 25 '17 at 18:08
• That doesn't appear to be what you meant. You were specifying a set of columns, not merely a number. – Michael Hardy May 25 '17 at 20:12
• @MichaelHardy Yes Yes! Got it. – Bijesh K.S May 26 '17 at 6:06

An elementary row operation replaces a matrix $A$ by $EA$ where $E$ is an (invertible) elementary matrix. A set $S$ of columns of $A$ is linearly independent iff $Av=0$ for some vector $v$ which is nonzero and only has nonzero entries in places corresponding to some of the columns in $S$. But $Ay=0$ iff $EAv=0$. Thus a set of columns of $A$ is linearly dependent iff the corresponding columns in $EA$ are linearly independent. So the largest sets of linearly independent columns in $A$ and $EA$ must be the same.