## Every matrix over a field is row equivalent to a matrix in reduced row echelon form

Let $F$ be a field and let $A$ be a matrix over $F$. Prove that $A$ 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 $1 \times m$ matrix is in row echelon form if it is 0 or if the first nonzero entry is 1. For the recursive step, an $n \times m$ matrix $A$ is said to be in row echelon form if we have $A = 0$ or $A = \left[ \begin{array}{c|c|c} 0 & 1 & V \\ \hline 0 & 0 & A^\prime \end{array} \right]$, where $1$ is the $1 \times 1$ identity matrix, $V$ has dimension $1 \times k$ for some $k < m$, and $A^\prime$ is in row echelon form and has dimension $(n-1) \times k$. (Note that the leftmost submatrices have $m-k-1$ columns.)

To each matrix in row echelon form, we associate a (possibly empty) set of pairs $(i,j)$ called pivots as follows. For $A$ has dimension $1 \times m$, if $A = 0$ then $A$ has no pivots. If $j$ is minimal such that the $(1,j)$ entry of $A$ is nonzero, then $\{(i,j)\}$ is the set of pivots for $A$. For the recursive step, suppose $A$ has dimension $n \times m$. If $A = 0$, then $A$ has no pivots. If $A = \left[ \begin{array}{c|c|c} 0 & 1 & V \\ \hline 0 & 0 & A^\prime \end{array} \right]$, where $V$ has dimension $1 \times k$, then the pivots of $A$ are $(1,m-k)$ and $(i+1,j+1)$ where $(i,j)$ is a pivot of $A^\prime$.

We will say that a matrix $A = [a_{i,j}]$ is in reduced row echelon form if it is in row echelon form and for each pivot $(i,j)$, we have $a_{k,j} = 0$ for all $k < i$.

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 $A = [a_{i,j}]$ be a $1 \times m$ matrix. If $A = 0$, then $A$ is in row echelon form. If $A \neq 0$, then there exists a minimal index $j$ such that $a_{1,j} \neq 0$. Let $P$ be the elementary matrix $P = E_{1,1}(1/a_{1,j})$. Then $PA$ is in row echelon form. For the inductive step, let $A$ be an $(n+1) \times m$ matrix. If $A = 0$, then $A$ is in row echelon form. Suppose now that $A = [a_{i,j}] \neq 0$, and let $k$ be minimal such that $a_{i,k} \neq 0$ for some $i$. Then we have $A = [0 | C | A_2]$, where $C = [a_{i,k}] \neq 0$ has dimension $n \times 1$. Choose an index $\ell$ such that $a_{\ell,k} \neq 0$. We have a product $P$ of elementary matrices which interchanges rows 1 and $\ell$. Now $PA = [0 | C | A_2]$ (different $C$ and $A_2$) where the first entry of $C$, say $c_1$, is nonzero. Let $Q = E_{1,1}(1/c_1)$. Then $QPA = \left[ \begin{array}{c|c|c} 0 & 1 & V \\ \hline 0 & C & A_2 \end{array} \right]$ (again, with different $C$ and $A_2$, and where $V$ has dimension $1 \times (m-k)$.) Let $C = [c_{i,j}]$ be indexed from 2 in the $i$ variable. Then for each nonzero $c_{i,1}$, we let $R_i = E_{i,1}(-c_i)$ and let $R = \prod R_i$. Now $RQPA = \left[ \begin{array}{c|c|c} 0 & 1 & V \\ \hline 0 & 0 & A_2 \end{array} \right]$ (again, with a different $V$ and $A_2$.) By the induction hypothesis, there exists a product $T_2$ of elementary matrices such that $T_2A_2$ is in row echelon form. Let $T = \left[ \begin{array}{c|c} 1 & 0 \\ \hline 0 & T_2 \end{array} \right]$. Using the lemmas from this previous exercise, we have the following.

 $TRQPA$ = $\left[ \begin{array}{c|c} 1 & 0 \\ \hline 0 & T_2 \end{array} \right] \left[ \begin{array}{c|c|c} 0 & 1 & V \\ \hline 0 & 0 & A_2 \end{array} \right]$ = $\left[ \begin{array}{c|c} I[0|1] + 0[0|0] & IV + 0A_2 \\ \hline 0[0|1] + T_2[0|0] & 0V + T_2A_2 \end{array} \right]$ = $\left[ \begin{array}{c|c|c} 0 & 1 & V \\ \hline 0 & 0 & T_2A_2 \end{array} \right]$

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 $1 \times m$ matrix in row echelon form is already in reduced row echelon form (there is nothing to show). Suppose now that $A = \left[ \begin{array}{c|c|c} 0 & 1 & V \\ \hline 0 & 0 & A_2 \end{array} \right]$ is in row echelon form, where $A_2$ is also in row echelon form. There is a product $P_2$ of elementary matrices such that $P_2A_2$ is in reduced row echelon form. Let $P = \left[ \begin{array}{c|c} 1 & 0 \\ \hline 0 & A_2 \end{array} \right]$. Let $V = [v_{i,j}]$. For each pivot $(i,j)$ of $P_2A_2$, let $Q_{i,j} = E_{1,i}(-v_{1,j})$, and let $Q = \prod Q_{i,j}$. Then $QPA$ is in reduced row echelon form.

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