150 CHAPTER 8. RANK OF A MATRIX

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 casebut first, here is a fundamental lemma.

In rough terms, the following lemma states that linear relationships between columnsin a matrix are preserved by row operations. This simple lemma is the main result inunderstanding all the major questions related to the row reduced echelon form as well asmany other topics.

Lemma 8.2.5 Let A and B be two m×n matrices and suppose B results from a row opera-tion applied to A. Then the kth column of B is a linear combination of the i1, · · · , ir columnsof B if and only if the kth column of A is a linear combination of the i1, · · · , ir columns ofA. Furthermore, the scalars in the linear combination are the same. (The linear relation-ship between the kth column of A and the i1, · · · , ir columns of A is the same as the linearrelationship between the kth column of B and the i1, · · · , ir columns of B.)

Proof: Let A equal the following matrix in which the ak are the columns(a1 a2 · · · an

)and let B equal the following matrix in which the columns are given by the bk(

b1 b2 · · · bn

)Then by Theorem 8.1.10 on Page 146 bk = Eak where E is an elementary matrix. Supposethen that one of the columns of A is a linear combination of some other columns of A. Say

ak = ∑r∈S

crar.

Then multiplying by E,

bk = Eak = ∑r∈S

crEar = ∑r∈S

crbr. ■

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

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 e j.

Thus the row reduced echelon form is completely determined by the positions of colum-ns which 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 ofthese special pivot columns to obtain the other columns. All of these considerations pertainonly to linear relations between the columns of the matrix, which by Lemma 8.2.5 are allpreserved. Therefore, there is only one row reduced echelon form for any given matrix.The proof of the following corollary is just a more careful exposition of this simple idea.