6
$\begingroup$

From this question link, I got to know that row operation(row subtraction and row permutation) do change column space.

But still it seems that it does not change the column rank.

I am trying to prove that row rank == columns rank, but for that I need confirm the statement above. I am referring to this note

Have any intuitive explanation or proof for that row operation does not change the column rank?

$\endgroup$
  • $\begingroup$ Because row operations are used so you can find all row (or column) vectors that are linearly independent. This is, finding a basis for the row (or column) space. For a more thorough answer, check this explanation. $\endgroup$ – Thomas Bladt Nov 10 '17 at 5:51
  • $\begingroup$ I fully understand what you mentioned, but what I am wondering is that why row operation reserve the column rank, not only row rank? $\endgroup$ – DongukJu Nov 10 '17 at 5:54
  • $\begingroup$ Because the column rank of your matrix $A$ is the maximum number of columns that are linearly independent. Any elementary operation does not change the linear independence of the columns. $\endgroup$ – Thomas Bladt Nov 10 '17 at 6:03
  • $\begingroup$ Then, I am asking the reason why it does now... $\endgroup$ – DongukJu Nov 10 '17 at 6:04
  • 1
    $\begingroup$ Many good answers to the related question here. $\endgroup$ – A.Γ. Nov 10 '17 at 6:07
12
$\begingroup$

If a collection of columns are linearly independent (respectively linearly dependent) then they remain so under elementary row operations. Therefore elementary row operations do not change the largest set of linearly independent columns.

To see this, notice that a linear dependence relation between some columns of a matrix $A$ is given by a nonzero column vector $v$ with $Av=0$. If $E$ is an elementary matrix and $B=EA$ then $Bv=EAv=0$; conversely if $Bv=0$ then $Av=E^{-1}Bv=0$. Therefore if a set of columns of $A$ is linearly dependent then the corresponding set of columns of $B$ is also linearly dependent and vice versa. This means $A$ and $B$ have the same column rank.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Your answer is simple and perfectly intuitive!! Thanks a lot, but I still wonder a little bit. From my understanding, you proved that column dependence/independence is preserved during row operation, not the rank is preserved. It seems that this is connected to what I want. Can you explain this a bit more? $\endgroup$ – DongukJu Nov 10 '17 at 6:04
  • 2
    $\begingroup$ @DongukJu The column rank is the maximum size of a set of linearly independent columns. $\endgroup$ – Angina Seng Nov 10 '17 at 6:10
0
$\begingroup$

Here is an elaboration on Lord Shark the Unknown's answer. Let $A$ be the original matrix, let $E$ be an elementary matrix, and let $B := EA$ be the new matrix. Let $k$ be the dimension of the column space of $A$, and let $r$ be the dimension of the column space of $B$. Then there is some way to choose $k$ of the columns of $A$ that are linearly independent. After we apply the row operations to these columns, the new list (which lives in the column space of $B$) is also linearly independent, so we must have $r \geq k$. Now we can do the same thing starting with the columns of $B$: choose $r$ that are linearly independent, apply the inverse row operation, obtain $r$ linearly independent vectors in the column space of $A$, and conclude $k \geq r$.


Here is a more explicit/concrete answer.

Let $A$ be an $m\times n$ matrix and let $C_1,\ldots,C_n$ be the columns of $A$. If $e_1,\ldots,e_n$ is the standard basis, this means $Ae_j = C_j$ for $j \in \{1,\ldots,n\}$. If $E$ is an elementary matrix, then the result of applying this row operation to $A$ is $B:=EA$. So the columns of $B$ are $Be_j = EAe_j = EC_j$. In other words, to get the columns of the new matrix, we can just apply the row operation separately to each column.

We want to show that $\dim \operatorname{span}(C_1,\ldots,C_n) = \dim \operatorname{span}(EC_1,\ldots,EC_n)$. Every spanning list contains a basis, so we can choose columns $C_{n_1},\ldots,C_{n_k}$ of $A$ which are linearly independent and which span the column space of $A$ (i.e. $\operatorname{span}(C_1,\ldots,C_n) = \operatorname{span}(C_{n_1},\ldots,C_{n_k})$).

Now consider the list $EC_{n_1},\ldots,EC_{n_k}$, which are the corresponding columns of $B$. We claim that this is a basis for the column space of $B$. Suppose $a_1EC_{n_1} + \cdots + a_kEC_{n_k} = 0$ for some choice of constants $a_1,\ldots,a_k$. Then we can apply $E^{-1}$ to both sides to conclude that $a_1C_{n_1} + \cdots + a_kC_{n_k} = 0$. Since $C_{n_1},\ldots,C_{n_k}$ are linearly independent, we must have $a_1 = \cdots = a_k = 0$. Thus $EC_{n_1},\ldots,EC_{n_k}$ are linearly independent.

Now let $v:=b_1EC_1 + \cdots + b_nEC_n$ be a vector in the column space of $B$. Applying $E^{-1}$ we obtain $E^{-1}v= b_1C_1 + \cdots + b_nC_n$. Thus $E^{-1}v$ is in the column space of $A$. Since $C_{n_1},\ldots,C_{n_k}$ is a basis for the column space of $A$, this means we can write $E^{-1}v = c_1C_{n_1} + \cdots + c_kC_{n_k}$ for some choice of constants $c_1,\ldots,c_k$. Applying $E$ we have $v = EE^{-1}v = c_1EC_{n_1} + \cdots + c_kEC_{n_k}$. Thus we have written $v$ as a linear combination of $EC_{n_1},\ldots,EC_{n_k}$, so this list spans the column space of $B$.

Thus $EC_{n_1},\ldots,EC_{n_k}$ is a basis of $\operatorname{span}(EC_1,\ldots,EC_n)$. Now we have $$\begin{align}\dim \operatorname{span}(C_1,\ldots,C_n) &= \dim\operatorname{span}(C_{n_1},\ldots,C_{n_k}) \\ &=k \\ &= \dim\operatorname{span}(EC_{n_1},\ldots,EC_{n_k}) \\ &= \dim\operatorname{span}(EC_1,\ldots,EC_n)\end{align}$$


Finally, here is a more abstract version.

We first show the following: Let $T : V\to V$ be an invertible linear map, and let $U$ be a subspace of $V$. Then $\dim U = \dim \operatorname{range} T|_U$. (Here $T|_U : U \to V$ is the restriction of $T$ to the subspace $U$, i.e. $T|_U(u) := Tu$ for all $u \in U$.)

Proof. Let $u_1, u_2$ be two vectors in $U$ such that $T|_U(u_1) = T|_U(u_2)$. Then we have $$Tu_1 = T|_U(u_1) = T|_U(u_2) = Tu_2$$ Since $T$ is invertible, $u_1=u_2$. This shows that $T|_U$ is injective. Now the fundamental theorem of linear maps states that $$\dim U = \dim \operatorname{null} T|_U + \dim \operatorname{range} T|_U$$ Since $T|_U$ is injective, we have $\dim \operatorname{null} T|_U = 0$. Thus $\dim U = \dim \operatorname{range} T|_U$. $\Box$

Now that we have proved the above result, we can apply it to our particular case. In our case, $V = \mathbf R^m$, $T$ is the $m\times m$ elementary matrix $E$, and $U$ is the span of the columns of $A$. So the abstract result states that $\dim \operatorname{span}(C_1, \ldots, C_n) = \dim \operatorname{range} E|_{\operatorname{span}(C_1, \ldots, C_n)}$. This is basically what we want, and the only tricky thing is decoding what $\operatorname{range} E|_{\operatorname{span}(C_1, \ldots, C_n)}$ means. We have $E|_{\operatorname{span}(C_1, \ldots, C_n)} : \operatorname{span}(C_1, \ldots, C_n) \to \mathbf R^m$, so the range of that is $\{Ev : v \in \operatorname{span}(C_1, \ldots, C_n)\}$. But that's just $\operatorname{span}(EC_1, \ldots, EC_n)$. So $\operatorname{range} E|_{\operatorname{span}(C_1, \ldots, C_n)} = \operatorname{span}(EC_1, \ldots, EC_n)$, and we have $$\dim \operatorname{span}(C_1, \ldots, C_n) = \dim \operatorname{range} E|_{\operatorname{span}(C_1, \ldots, C_n)} = \dim \operatorname{span}(EC_1, \ldots, EC_n)$$

This may seem overly complicated, but the main point is that we've stuffed away all the "hard" parts (reasoning about linear independence and so forth) into the fundamental theorem of linear maps, so that what is left is just decoding what the notation means.


Here is another abstract version.

Let $A: V \to W$ be linear, and let $E : W \to W$ be invertible. Then $EAv = 0$ iff $Av = 0$ (we can just multiply by $E$ or $E^{-1}$ to get the other equation). So $\operatorname{null} EA = \operatorname{null} A$. But now $$\begin{align}\dim \operatorname{range} EA &= \dim V - \dim \operatorname{null} EA \\ &=\dim V - \dim \operatorname{null} A \\ &= \dim \operatorname{range} A\end{align}$$

| cite | improve this answer | |
$\endgroup$

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.