8.2. SUBSPACES SPANS AND BASES 179

equals the zero vector is the trivial linear combination. Thus {x1, · · · ,xn} is called linearlyindependent if whenever

p

∑k=1

ckxk = 0

it follows that all the scalars, ck equal zero. A set of vectors,{

x1, · · · ,xp}, is called linearly

dependent if it is not linearly independent. Thus the set of vectors is linearly dependent ifthere exist scalars, ci, i = 1, · · · ,n, not all zero such that ∑

pk=1 ckxk = 0.

Lemma 8.2.2 A set of vectors{

x1, · · · ,xp}

is linearly independent if and only if none ofthe vectors can be obtained as a linear combination of the others.

Proof: Suppose first that{

x1, · · · ,xp}

is linearly independent. If

xk = ∑j ̸=k

c jx j,

then0 = 1xk + ∑

j ̸=k(−c j)x j,

a nontrivial linear combination, contrary to assumption. This shows that if the set is linearlyindependent, then none of the vectors is a linear combination of the others.

Now suppose no vector is a linear combination of the others. Is{

x1, · · · ,xp}

linearlyindependent? If it is not, there exist scalars, ci, not all zero such that

p

∑i=1

cixi = 0.

Say ck ̸= 0. Then you can solve for xk as

xk = ∑j ̸=k

(−c j)/ckx j

contrary to assumption. This proves the lemma.The following is called the exchange theorem.

Theorem 8.2.3 Ifspan(u1, · · · ,ur)⊆ span(v1, · · · ,vs)≡V

and {u1, · · · ,ur} are linearly independent, then r ≤ s.

Proof: Suppose r > s. Let Fp denote the first p vectors in {u1, · · · ,ur}. In case p= 0,Fpwill denote the empty set. Let Ep denote a finite list of vectors of {v1, · · · ,vs} and let

∣∣Ep∣∣

denote the number of vectors in the list. For 0≤ p≤ s, let Ep have the property

span(Fp,Ep) =V

and∣∣Ep∣∣ is as small as possible for this to happen. I claim

∣∣Ep∣∣≤ s− p if Ep is nonempty.