Two row equivalent and reduced row echelon matrices are equal

Let $A$ and $C$ be matrices of the same dimension over a field $F$. Prove that if $A$ and $C$ are in reduced row echelon form and row equivalent, then $A = C$.

[I read this proof by Christian Roettger, and took a lemma. Ultimately this strategy went in a slightly different direction.]

We begin with some lemmas.

Lemma 1 (unused?): If $A$ and $C$ are row equivalent matrices over a field $F$, then $Ax = 0$ if and only if $Cx = 0$. Proof: Recall that, since $A$ and $C$ are row equivalent, there exists an invertible matix $P$ such that $PA = C$. We may consider $A$, $C$, and $P$ to be linear transformations $V \rightarrow W$ and $W \rightarrow W$ respectively. Fix appropriate bases so that $A = M^E_B(\varphi)$, $C = M^E_B(\psi)$, and $P = M^E_E(\theta)$. Then we have $\theta \circ \varphi = \psi$. In particular, $\mathsf{ker}\ \varphi \subseteq \mathsf{ker}\ \psi$. Similarly, $\varphi = \theta^{-1} \circ \psi$, so that $\mathsf{ker}\ \psi \subseteq \mathsf{ker}\ \varphi$. So $\mathsf{ker}\ \varphi = \mathsf{ker}\ \psi$, and the conclusion follows. $\square$

Lemma 2: If $A$ and $C$ are row equivalent matrices of dimension $n \times m$ over a field $F$, then the $j$th column of $A$ is zero if and only if the $j$th column of $C$ is zero. Proof: It suffices to show that the elementary row operations do not alter columns of zeros; this is clear. $\square$

Now we will proceed by induction on the number of rows.

For the base case, suppose $A$ and $C$ are $1 \times m$ matrices over $F$ which are row equivalent and in reduced row echelon form. If $A = 0$ and $C = 0$, then certainly $A = C$. Suppose $A \neq 0$; using Lemma 2, we have $C \neq 0$. Moreover, $A$ and $C$ have the same pivot. Since $A$ and $C$ are row equivalent, there exists a $1 \times 1$ matrix $P$ over $F$ (i.e. an element of $F$) such that $PA = C$. Say $P = [\alpha]$; since $A$ and $C$ have the same pivot, we have $\alpha \cdot 1 = 1$, so that $\alpha = 1$ and thus $A = C$.

For the inductive step, suppose that if $A$ and $C$ are row equivalent matrices in reduced row echelon form having $n$ rows, then $A = C$. Let $A = \left[ \begin{array}{c|c|c} 0 & 1 & V \\ \hline 0 & 0 & A_2 \end{array} \right]$ and $C = \left[ \begin{array}{c|c|c} 0 & 1 & W \\ \hline 0 & 0 & C_2 \end{array} \right]$ be $(n+1) \times m$ matrices in reduced row echelon form. Suppose $A$ and $C$ are row equivalent via the invertible matrix $P = \left[ \begin{array}{c|c} P_{1,1} & P_{1,2} \\ \hline P_{2,1} & P_{2,2} \end{array} \right]$, where $P_{1,1}$ has dimension $1 \times 1$ and $P_{2,2}$ has dimension $n \times n$ (and the dimensions of $P_{1,2}$ and $P_{2,1}$ are as required.) In particular, by Lemma 2, $A_2$ and $C_2$ have the same dimension since $A$ and $C$ must have the same number of leading zero columns.

Using the structural lemmas in this previous exercise, from $PA = C$ we have the following.

$\left[ \begin{array}{c|c|c} 0 & P_{1,1}1 & P_{1,1}V + P_{1,2}A_2 \\ \hline 0 & P_{2,1}1 & P_{2,1}V + P_{2,2}A_2 \end{array} \right] = \left[ \begin{array}{c|c|c} 0 & 1 & W \\ \hline 0 & 0 & C_2 \end{array} \right]$

In particular, note that $P_{1,1}1 = 1$, so that $P_{1,1} = [1]$. Similarly, Since $P_{2,1}1 = 0$, we have $P_{2,1} = 0$. Thus $P_{2,2}A_2 = C_2$. We claim that $P_{2,2}$ is invertible. To see this, note that since $P$ is invertible, there exists a matrix $Q = \left[ \begin{array}{c|c} Q_{1,1} & Q_{1,2} \\ \hline Q_{2,1} & Q_{2,2} \end{array} \right]$ such that $PQ = \left[ \begin{array}{c|c} Q_{1,1} + P_{1,2}Q_{2,1} & Q_{1,2} + P_{1,2}Q_{2,2} \\ \hline P_{2,2}Q_{2,1} & P_{2,2}Q_{2,2} \end{array} \right] = \left[ \begin{array}{c|c} 1 & 0 \\ \hline 0 & I \end{array} \right]$. In particular, $P_{2,2}$ is invertible. Note that at this point we have not proven that every invertible matrix is a product of elementary matrices- however, this is true, and we will assume it for now. We have shown, then, that $A_2$ and $C_2$ are row equivalent. They are also in reduced row echelon form, by our recursive definition of reduced row echelon form. Thus $A_2 = C_2$, and in fact $P_{2,2} = I$. That is, we have $P = \left[ \begin{array}{c|c} 1 & P_{1,2} \\ \hline 0 & I \end{array} \right]$, where $P_{1,2}$ has dimension $1 \times n$.

In particular, we can see that $P$ is a product of elementary matrices of the form $E_{1,t}(\alpha)$, where $t > 1$. (See our previous discussion about elementary matrices.) To see this, note that

$\left[ \begin{array}{c|c|c} I & V & W \\ \hline 0 & I & 0 \\ \hline 0 & 0 & I \end{array} \right] = \left[ \begin{array}{c|c|c} I & V & 0 \\ \hline 0 & I & 0 \\ \hline 0 & 0 & I \end{array} \right] \left[ \begin{array}{c|c|c} I & 0 & W \\ \hline 0 & I & 0 \\ \hline 0 & 0 & I \end{array} \right]$

and use induction.

It remains to be seen that $V = W$. To see this, say $V$ (and $W$) have dimension $1 \times (m-k)$. Recall that every row in $A$ either has a pivot or is 0. If the $t$th row of $A$ is 0, then the elementary matrix $E_{1,t}(\alpha)$ in the decomposition of $P$ has no effect. That is, we can say $P_{1,t} = 0$. If the $t$th row of $A$ has a pivot, say in column $k+j$, then the $(1,j)$ entry of $V$ is zero. Moreover, the $(1,j)$ entry of $W$ is simply the $(1,t)$ entry of $P$. Note, however, that the $t$th row of $C$ also has a pivot in column $k+j$. So in fact the $(1,t)$ entry of $P$ is 0. Thus we have $P = I$, and so $A = C$.