4.3. THE ROW REDUCED ECHELON FORM 119

For example, here are some matrices which are in row reduced echelon form. 0 1 3 0 3

0 0 0 1 5

0 0 0 0 0

 ,

 1 0 3 −11 0

0 1 4 4 0

0 0 0 0 1

 .

Theorem 4.3.2 Let A be an m × n matrix. Then A has a row reduced echelon formdetermined by a simple process.

Proof: Viewing the columns of A from left to right take the first nonzero column. Picka nonzero entry in this column and switch the row containing this entry with the top row ofA. Now divide this new top row by the value of this nonzero entry to get a 1 in this positionand then use row operations to make all entries below this entry equal to zero. Thus thefirst nonzero column is now e1. Denote the resulting matrix by A1. Consider the submatrixof A1 to the right of this column and below the first row. Do exactly the same thing for itthat was done for A. This time the e1 will refer to Fm−1. Use this 1 and row operationsto zero out every entry above it in the rows of A1. Call the resulting matrix A2. Thus A2

satisfies the conditions of the above definition up to the column just encountered. Continuethis way till every column has been dealt with and the result must be in row reduced echelonform. ■

Definition 4.3.3 The first pivot column of A is the first nonzero column of A. The nextpivot column is the first column after this which is not a linear combination of the columns toits left. The third pivot column is the next column after this which is not a linear combinationof those columns to its left, and so forth. Thus by Lemma 4.2.3 if a pivot column occursas the jth column from the left, it follows that in the row reduced echelon form there will beone of the ek as the jth column.

There are three choices for row operations at each step in the above theorem. A naturalquestion is whether the same row reduced echelon matrix always results in the end fromfollowing the above algorithm applied in any way. The next corollary says this is the case.

Definition 4.3.4 Two matrices are said to be row equivalent if one can be obtained fromthe other by a sequence of row operations.

Since every row operation can be obtained by multiplication on the left by an elementarymatrix and since each of these elementary matrices has an inverse which is also an elementarymatrix, it follows that row equivalence is a similarity relation. Thus one can classify matricesaccording to which similarity class they are in. Later in the book, another more profoundway of classifying matrices will be presented.

It has been shown above that every matrix is row equivalent to one which is in rowreduced echelon form. Note 

x1...

xn

 = x1e1 + · · ·+ xnen

so to say two column vectors are equal is to say they are the same linear combination of thespecial vectors ej .

Thus the row reduced echelon form is completely determined by the positions of columnswhich are not linear combinations of preceding columns (These become the ei vectors inthe row reduced echelon form.) and the scalars which are used in the linear combinations of