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,