166 CHAPTER 8. RANK OF A MATRIX

Proof: Since {y1, · · · ,ys} is a spanning set, there exist scalars ai j such that

x j =s

∑i=1

ai jyi

Suppose s < r. Then the matrix A whose i jth entry is ai j has fewer rows, s than columns, r.By Corollary 8.2.8 there exists d such that d ̸= 0 but Ad = 0. In other words,

r

∑j=1

ai jd j = 0, i = 1,2, · · · ,s

Therefore,

r

∑j=1

d jx j =r

∑j=1

d j

s

∑i=1

ai jyi

=s

∑i=1

(r

∑j=1

ai jd j

)yi =

s

∑i=1

0yi = 0

which contradicts {x1, · · · ,xr} is linearly independent, because not all the d j = 0. Thuss≥ r. ■

Note how this lemma was totally dependent on algebraic considerations and was inde-pendent of context. This will be considered more later in the chapter on abstract vectorspaces. I didn’t need to know what the xk, yk were, only that the {x1, · · · ,xr} were inde-pendent and contained in the span of the yk.

8.5.3 Basis Of A SubspaceIt was just shown in Corollary 8.5.11 that every subspace of Fn is equal to the span of alinearly independent collection of vectors of Fn. Such a collection of vectors is called abasis.

Definition 8.5.13 Let V be a subspace of Fn. Then {u1, · · · ,uk} is a basis for V if thefollowing two conditions hold.

1. span(u1, · · · ,uk) =V.

2. {u1, · · · ,uk} is linearly independent.

The plural of basis is bases.

The main theorem about bases is the following.

Theorem 8.5.14 For V be a subspace of Fn and {u1, · · · ,uk}, {v1, · · · ,vm} two bases forV , it follows k = m.

Proof: This follows right away from Lemma 8.5.12. {u1, · · · ,uk} is a spanning setwhile {v1, · · · ,vm} is linearly independent so k ≥ m. Also {v1, · · · ,vm} is a spanning setwhile {u1, · · · ,uk} is linearly independent so m≥ k.