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.

Advertisements
Post a comment or leave a trackback: Trackback URL.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: