4.3. THE ROW REDUCED ECHELON FORM 121

column, yields an r× r identity submatrix in which r is the number of pivot columns. Thusthe rank is at least r.

From Lemma 4.2.3 every column of A is a linear combination of the pivot columns sincethis is true by definition for the row reduced echelon form. Therefore, the rank is no morethan r. ■

Here is a fundamental observation related to the above.

Corollary 4.3.9 Suppose A is an m×n matrix and that m < n. That is, the number of rowsis less than the number of columns. Then one of the columns of A is a linear combinationof the preceding columns of A.

Proof: Since m < n, not all the columns of A can be pivot columns. That is, in therow reduced echelon form say ei occurs for the first time at ri where r1 < r2 < · · · < rpwhere p ≤ m. It follows since m < n, there exists some column in the row reduced echelonform which is a linear combination of the preceding columns. By Lemma 4.2.3 the same istrue of the columns of A. ■

Definition 4.3.10 Let A be an m×n matrix having rank, r. Then the nullity of A is definedto be n− r. Also define ker (A) ≡ {x ∈ Fn : Ax = 0} . This is also denoted as N (A) .

Observation 4.3.11 Note that ker (A) is a subspace because if a, b are scalars and x,y arevectors in ker (A), then

A (ax+ by) = aAx+ bAy = 0+ 0 = 0

Recall that the dimension of the column space of a matrix equals its rank and since thecolumn space is just A (Fn) , the rank is just the dimension of A (Fn). The next theoremshows that the nullity equals the dimension of ker (A).

Theorem 4.3.12 Let A be an m× n matrix. Then rank (A) + dim (ker (A)) = n.

Proof: Since ker (A) is a subspace, there exists a basis for ker (A) , {x1, · · · ,xk} . Alsolet {Ay1, · · · , Ayl} be a basis for A (Fn). Let u ∈ Fn. Then there exist unique scalars cisuch that

Au =

l∑i=1

ciAyi

It follows that

A

(u−

l∑i=1

ciyi

)= 0

and so the vector in parenthesis is in ker (A). Thus there exist unique bj such that

u =

l∑i=1

ciyi +

k∑j=1

bjxj

Since u was arbitrary, this shows {x1, · · · ,xk,y1, · · · ,yl} spans Fn. If these vectors areindependent, then they will form a basis and the claimed equation will be obtained. Supposethen that

l∑i=1

ciyi +

k∑j=1

bjxj = 0

Apply A to both sides. This yields

l∑i=1

ciAyi = 0

and so each ci = 0. Then the independence of the xj imply each bj = 0. ■