1.7. THE ROW REDUCED ECHELON FORM OF A MATRIX 27

e1 and if, in viewing the columns of the matrix from left to right, you have encounterede1,e2, · · · ,ek, the next column is either ek+1 or this next column is a linear combination ofthe vectors, e1,e2, · · · ,ek.

Example 1.7.3 The following matrices are in row reduced echelon form.

 1 0 4 00 1 3 00 0 0 1

 ,

0 1 0 0 70 0 0 1 30 0 0 0 00 0 0 0 0

 ,

 0 1 0 30 0 1 −50 0 0 0

 .

Definition 1.7.4 Given a matrix A, row reduction produces one and only one rowreduced matrix B with A∼ B. See Corollary 1.7.9. We call B the row reduced echelon formof A.

Theorem 1.7.5 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 equal to zero. Thus the firstnonzero column is now e1. Denote the resulting matrix by A1. Consider the sub-matrixof A1 to the right of this column and below the first row. Do exactly the same thing forthis sub-matrix that was done for A. This time the e1 will refer to Fm−1. Use the first 1obtained by the above process which is in the top row of this sub-matrix and row operations,to produce a zero in place of every entry above it and below it. Call the resulting matrix A2.Thus A2 satisfies the conditions of the above definition up to the column just encountered.Continue this way till every column has been dealt with and the result must be in rowreduced echelon form. ■

Here is some terminology about pivot columns.

Definition 1.7.6 The first pivot column of A is the first nonzero column of A whichbecomes e1 in the row reduced echelon form. The next pivot column is the first columnafter this which becomes e2 in the row reduced echelon form. The third is the next columnwhich becomes e3 in the row reduced echelon form and so forth.

The algorithm just described for obtaining a row reduced echelon form shows that thesecolumns are well defined, but we will deal with this issue more carefully in Corollary 1.7.9where we show that every matrix corresponds to exactly one row reduced echelon form.

Definition 1.7.7 Two matrices A,B are said to be row equivalent if B can be ob-tained from A by a sequence of row operations. When A is row equivalent to B, we writeA∼ B.

Proposition 1.7.8 In the notation of Definition 1.7.7. A ∼ A. If A ∼ B, then B ∼ A. IfA∼ B and B∼C, then A∼C.