1.6. ELEMENTARY MATRICES 25

y

z

x

u

v

The following lemma states that linear relationships between columns in a matrix arepreserved by row operations. This simple lemma is the main result in understanding all themajor questions related to the row reduced echelon form as well as many other topics.

Lemma 1.6.10 Let A and B be two m× n matrices and suppose B results from a rowoperation applied to A. Then the kth column of B is a linear combination of the i1, · · · , ircolumns of B if and only if the kth column of A is a linear combination of the i1, · · · , ircolumns of A. Furthermore, the scalars in the linear combinations are the same. (Thelinear relationship between the kth column of A and the i1, · · · , ir columns of A is the sameas the linear relationship between the kth column of B and the i1, · · · , ir columns of B.)

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

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

b1 b2 · · · bn).

Then by Theorem 1.6.6 on Page 23, 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 = c1ai1 + · · ·+ crair .

Then multiplying by E,

bk = Eak = c1Eai1 + · · ·+ crEair = c1bi1 + · · ·+ crbir .

This proves the lemma. ■

Example 1.6.11 Find linear relationships between the columns of the matrix

A =

 1 3 11 10 361 2 8 9 231 1 5 8 10

 .

It is not clear what the relationships are, so we do row operations to this matrix. Lemma1.6.10 says that all the linear relationships between columns are preserved, so the idea is todo row operations until a matrix results which has the property that the linear relationshipsare obvious. First take −1 times the top row and add to the two bottom rows. This yields 1 3 11 10 36

0 −1 −3 −1 −130 −2 −6 −2 −26

