16.3. LINEAR INDEPENDENCE AND BASES 379

and let Bs−l denote a subset of the vectors, {y1, · · · ,ys} which contains s− l vectors andhas the property that span(Al ,Bs−l) = V. Note that the assumption of the theorem saysspan(A0,Bs) =V.

Now an exchange operation is given for span(Al ,Bs−l) = V . Since r > s, it followsl < r. Letting

Bs−l ≡ {z1, · · · ,zs−l} ⊆ {y1, · · · ,ys} ,it follows there exist constants, ci and di such that

xl+1 =l

∑i=1

cixi +s−l

∑i=1

dizi,

and not all the di can equal zero. (If they were all equal to zero, it would follow thatthe set, {x1, · · · ,xr} would be dependent since one of the vectors in it would be a linearcombination of the others.)

Let dk ̸= 0. Then zk can be solved for as follows.

zk =1dk

xl+1−l

∑i=1

ci

dkxi−∑

i̸=k

di

dkzi.

This implies V = span(Al+1,Bs−l−1), where Bs−l−1 ≡ Bs−l \{zk} , a set obtained by delet-ing zk from Bk−l . The process exchanged a vector in Bs−l with one from {x1, · · · ,xr} andkept the span the same. Starting with V = span(A0,Bs) , do the exchange operation un-til V = span(As−1,z) where z ∈ {y1, · · · ,ys} . Then one more application of the exchangeoperation yields V = span(As) . But this implies xr ∈ span(As) = span(x1, · · · ,xs) , contra-dicting the linear independence of {x1, · · · ,xr} . It follows that r ≤ s as claimed. ■

Proof 4: Suppose r > s. Let zk denote a vector of {y1, · · · ,ys} . Thus there exists j assmall as possible such that

span(y1, · · · ,ys) = span(x1, · · · ,xm,z1, · · · ,z j)

where m+ j = s. It is given that m = 0, corresponding to no vectors of {x1, · · · ,xm} andj = s, corresponding to all the yk results in the above equation holding. If j > 0 then m < sand so

xm+1 =m

∑k=1

akxk +j

∑i=1

bizi

Not all the bi can equal 0 and so you can solve for one of the zi in terms of

xm+1,xm, · · · ,x1,

and the other zk. Therefore, there exists{z1, · · · ,z j−1

}⊆ {y1, · · · ,ys}

such thatspan(y1, · · · ,ys) = span

(x1, · · · ,xm+1,z1, · · · ,z j−1

)contradicting the choice of j. Hence j = 0 and

span(y1, · · · ,ys) = span(x1, · · · ,xs)

It follows thatxs+1 ∈ span(x1, · · · ,xs)

contrary to the assumption the xk are linearly independent. Therefore, r ≤ s as claimed. ■