2
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Michael Hardy May 25 '17 at 16:05
  • $\begingroup$ 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. $\endgroup$ – Michael Hardy May 25 '17 at 16:14
  • $\begingroup$ @MichaelHardy Thank you for the insightful comments. What if instead I choose to say "maximum number of linearly independent columns"? $\endgroup$ – Bijesh K.S May 25 '17 at 18:08
  • 1
    $\begingroup$ That doesn't appear to be what you meant. You were specifying a set of columns, not merely a number. $\endgroup$ – Michael Hardy May 25 '17 at 20:12
  • $\begingroup$ @MichaelHardy Yes Yes! Got it. $\endgroup$ – Bijesh K.S May 26 '17 at 6:06
2
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ There is a small typo, it should be "a set of columns are linearly dependent iff ... " $\endgroup$ – AgentSmith Apr 2 '19 at 18:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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