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. ■