378 CHAPTER 16. VECTOR SPACES
Not all of these scalars can equal zero because if this were the case, it would follow thatx1 = 0 and so {x1, · · · ,xr} would not be linearly independent. Indeed, if x1 = 0, 1x1 +
∑ri=2 0xi = x1 = 0 and so there would exist a nontrivial linear combination of the vectors{x1, · · · ,xr} which equals zero.
Say ck ̸= 0. Then solve (16.5) for yk and obtain
yk ∈ span
x1,
s-1 vectors here︷ ︸︸ ︷y1, · · · ,yk−1,yk+1, · · · ,ys
.
Define {z1, · · · ,zs−1} by
{z1, · · · ,zs−1} ≡ {y1, · · · ,yk−1,yk+1, · · · ,ys}
Therefore, span(x1,z1, · · · ,zs−1) =V because if v ∈V, there exist constants c1, · · · ,cs suchthat
v =s−1
∑i=1
cizi + csyk.
Replace the yk in the above with a linear combination of the vectors,
{x1,z1, · · · ,zs−1}
to obtain v ∈ span(x1,z1, · · · ,zs−1) . The vector yk, in the list {y1, · · · ,ys} , has now beenreplaced with the vector x1 and the resulting modified list of vectors has the same span asthe original list of vectors, {y1, · · · ,ys} .
Now suppose that r > s and that span(x1, · · · ,xl ,z1, · · · ,zp) = V, where the vectors,z1, · · · ,zp are each taken from the set, {y1, · · · ,ys} and l + p = s. This has now been donefor l = 1 above. Then since r > s, it follows that l ≤ s < r and so l+1≤ r. Therefore, xl+1is a vector not in the list, {x1, · · · ,xl} and since span(x1, · · · ,xl ,z1, · · · ,zp) =V there existscalars, ci and d j such that
xl+1 =l
∑i=1
cixi +p
∑j=1
d jz j. (16.6)
Not all the d j can equal zero because if this were so, it would follow that {x1, · · · ,xr}wouldbe a linearly dependent set because one of the vectors would equal a linear combination ofthe others. Therefore, (16.6) can be solved for one of the zi, say zk, in terms of xl+1 andthe other zi and just as in the above argument, replace that zi with xl+1 to obtain
span
x1, · · ·xl ,xl+1,
p-1 vectors here︷ ︸︸ ︷z1, · · ·zk−1,zk+1, · · · ,zp
=V.
Continue this way, eventually obtaining
span(x1, · · · ,xs) =V.
But then xr ∈ span(x1, · · · ,xs) contrary to the assumption that {x1, · · · ,xr} is linearly in-dependent. Therefore, r ≤ s as claimed. ■
Proof 3: Let V ≡ span(y1, · · · ,ys) and suppose r > s. Let
Al ≡ {x1, · · · ,xl} ,A0 = /0,