28 CHAPTER 1. REVIEW OF SOME LINEAR ALGEBRA

Proof.That A∼ A is obvious. Consider the second claim. By Theorem 1.6.6, there existelementary matrices E1,E2, · · · ,Em such that

B = E1E2 · · ·EmA.

It follows from Lemma 1.6.8 that (E1E2 · · ·Em)−1 exists and equals the product of the

inverses of these matrices in the reverse order. Thus

E−1m E−1

m−1 · · ·E−11 B = (E1E2 · · ·Em)

−1 B

= (E1E2 · · ·Em)−1 (E1E2 · · ·Em)A = A.

By Theorem 1.6.6, each E−1k is an elementary matrix. By Theorem 1.6.6 again, the above

shows that A results from a sequence of row operations applied to B. The last claim is leftfor an exercise. This proves the proposition. ■

There are three choices for row operations at each step in Theorem 1.7.5. A naturalquestion is whether the same row reduced echelon matrix always results in the end fromfollowing any sequence of row operations.

We have already made use of the following observation in finding a linear relationshipbetween the columns of the matrix A, but here it is stated more formally. x1

...xn

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

so to say two column vectors are equal, is to say the column vectors are the same linearcombination of the special vectors e j.

Corollary 1.7.9 The row reduced echelon form is unique. That is if B,C are two ma-trices in row reduced echelon form and both are obtained from A by a sequence of rowoperations, then B =C.

Proof.Suppose B and C are both row reduced echelon forms for the matrix A. It followsthat B and C have zero columns in the same positions because row operations do not affectzero columns. By Proposition 1.7.8, B and C are row equivalent. In reading from leftto right in B, suppose e1, · · · ,er occur first in positions i1, · · · , ir respectively. Then fromthe description of the row reduced echelon form, each of these columns of B, in positionsi1, · · · , ir, is not a linear combination of the preceding columns. Since C is row equivalentto B, it follows from Lemma 1.6.10, that each column of C in positions i1, · · · , ir is not alinear combination of the preceding columns of C. By the description of the row reducedechelon form, e1, · · · ,er occur first in C, in positions i1, · · · , ir respectively. Therefore,both B and C have the sequence e1,e2, · · · ,er occurring first (reading from left to right) inthe positions, i1, i2, · · · , ir. Since these matrices are row equivalent, it follows from Lemma1.6.10, that the columns between the ik and ik+1 position in the two matrices are linearcombinations involving the same scalars, of the columns in the i1, · · · , ik position. Similarly,the columns after the ir position are linear combinations of the columns in the i1, · · · , irpositions involving the same scalars in both matrices. This is equivalent to the assertionthat each of these columns is identical in B and C. ■

Now with the above corollary, here is a very fundamental observation. The number ofnonzero rows in the row reduced echelon form is the same as the number of pivot columns.