Why do row operations not change the column rank?

Question

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?

Answer 1

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.

Answer 2

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}$$