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

[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 and are row equivalent matrices over a field , then if and only if . Proof: Recall that, since and are row equivalent, there exists an invertible matix such that . We may consider , , and to be linear transformations and respectively. Fix appropriate bases so that , , and . Then we have . In particular, . Similarly, , so that . So , and the conclusion follows.

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

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

For the base case, suppose and are matrices over which are row equivalent and in reduced row echelon form. If and , then certainly . Suppose ; using Lemma 2, we have . Moreover, and have the same pivot. Since and are row equivalent, there exists a matrix over (i.e. an element of ) such that . Say ; since and have the same pivot, we have , so that and thus .

For the inductive step, suppose that if and are row equivalent matrices in reduced row echelon form having rows, then . Let and be matrices in reduced row echelon form. Suppose and are row equivalent via the invertible matrix , where has dimension and has dimension (and the dimensions of and are as required.) In particular, by Lemma 2, and have the same dimension since and must have the same number of leading zero columns.

Using the structural lemmas in this previous exercise, from we have the following.

In particular, note that , so that . Similarly, Since , we have . Thus . We claim that is invertible. To see this, note that since is invertible, there exists a matrix such that . In particular, 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 and are row equivalent. They are also in reduced row echelon form, by our recursive definition of reduced row echelon form. Thus , and in fact . That is, we have , where has dimension .

In particular, we can see that is a product of elementary matrices of the form , where . (See our previous discussion about elementary matrices.) To see this, note that

and use induction.

It remains to be seen that . To see this, say (and ) have dimension . Recall that every row in either has a pivot or is 0. If the th row of is 0, then the elementary matrix in the decomposition of has no effect. That is, we can say . If the th row of has a pivot, say in column , then the entry of is zero. Moreover, the entry of is simply the entry of . Note, however, that the th row of also has a pivot in column . So in fact the entry of is 0. Thus we have , and so .