4.3. LINEAR RELATIONS AND ROW OPERATIONS 87

B,C must be exactly the same. This is why there is only one row reduced echelon formfor a given matrix and it justifies the use of the definite article when referring to the rowreduced echelon form.

This proves the following theorem.

Theorem 4.3.3 The row reduced echelon form is unique.

Now from this theorem, we can obtain the following.

Theorem 4.3.4 Let A be an n× n matrix. Then it is invertible if and only if there is asequence of row operations which produces I.

Proof: ⇒ Since A is invertible, it follows from Theorem 4.2.3 that the columns of Amust be independent. Hence, in the row reduced echelon form for A, the columns mustbe e1,e2, · · · ,en in order from left to right. In other words, there is a sequence of rowoperations which produces I.⇐ Now suppose such a sequence of row operations produces I. Then since row oper-

ations preserve linear combinations between columns, it follows that no column is a linearcombination of the others and consequently the columns are linearly independent. By The-orem 4.2.3 again, A is invertible. ■

It would be possible to define things like rank in terms of the row reduced echelonform and this is often done. However, in this book, these things will be defined in terms ofvector space language and the row reduced echelon form will be a useful tool to determinethe rank.

Definition 4.3.5 Let A be an m×n matrix, the entries being in F a field. Then rank(A) isdefined as the dimension of Im(A)≡ A(Fn). Note that, from the way we multiply matricestimes a vector, this is just the same as the dimension of span(columns of A), sometimescalled the column space.

Now here is a very useful result.

Proposition 4.3.6 Let A be an m× n matrix. Then rank(A) equals the number of pivotcolumns in the row reduced echelon form of A. These are the columns of A which are not alinear combination of those columns on the left.

Proof: This is obvious if the matrix is already in row reduced echelon form. In thiscase, the pivot columns consist of e1,e2, · · · ,er and every other column is a linear com-bination of these. Thus the rank of this matrix is r because these vectors are obviouslylinearly independent. However, the linear relations between a column and its preceedingcolumns are preserved by row operations and so the columns in A corresponding to the firstoccurance of e1, first occurance of e2 and so forth, in the row reduced echelon form, thepivot columns, are also a basis for the span of the columns of A and so there are r of these.■

Note that from the description of the row reduced echelon form, the rank is also equalto the number of nonzero rows in the row reduced echelon form.