Let be a field and let be a matrix over . Prove that is row equivalent to a matrix in reduced row echelon form.

We begin with a discussion about row echelon and reduced row echelon forms of matrices.

We will define row echelon form for matrices recursively as follows. For the base case, a matrix is in row echelon form if it is 0 or if the first nonzero entry is 1. For the recursive step, an matrix is said to be in *row echelon form* if we have or , where is the identity matrix, has dimension for some , and is in row echelon form and has dimension . (Note that the leftmost submatrices have columns.)

To each matrix in row echelon form, we associate a (possibly empty) set of pairs called *pivots* as follows. For has dimension , if then has no pivots. If is minimal such that the entry of is nonzero, then is the set of pivots for . For the recursive step, suppose has dimension . If , then has no pivots. If , where has dimension , then the pivots of are and where is a pivot of .

We will say that a matrix is in *reduced row echelon form* if it is in row echelon form and for each pivot , we have for all .

To prove that every matrix is row equivalent to a matrix in reduced row echelon form, we will first show that every matrix is row equivalent to a matrix in row echelon form. We will then show that every row echelon matrix is row equivalent to a reduced row echelon matrix.

Lemma 1: Every matrix is row equivalent to a matrix in row echelon form. Proof: We will proceed by induction on the number of rows. For the base case, let be a matrix. If , then is in row echelon form. If , then there exists a minimal index such that . Let be the elementary matrix . Then is in row echelon form. For the inductive step, let be an matrix. If , then is in row echelon form. Suppose now that , and let be minimal such that for some . Then we have , where has dimension . Choose an index such that . We have a product of elementary matrices which interchanges rows 1 and . Now (different and ) where the first entry of , say , is nonzero. Let . Then (again, with different and , and where has dimension .) Let be indexed from 2 in the variable. Then for each nonzero , we let and let . Now (again, with a different and .) By the induction hypothesis, there exists a product of elementary matrices such that is in row echelon form. Let . Using the lemmas from this previous exercise, we have the following.

= | ||

= | ||

= |

Which is in row echelon form, by our recursive definition. By induction, then, every matrix is row equivalent to a matrix in row echelon form.

Finally, we need to see that every row echelon matrix is row equivalent to a reduced row echelon matrix. Again, we proceed by induction on the number of rows. A nonzero matrix in row echelon form is already in reduced row echelon form (there is nothing to show). Suppose now that is in row echelon form, where is also in row echelon form. There is a product of elementary matrices such that is in reduced row echelon form. Let . Let . For each pivot of , let , and let . Then is in reduced row echelon form.

Thus every matrix is row equivalent to a matrix in reduced row echelon form.