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.