194 CHAPTER 7. VECTOR SPACES AND FIELDS

contrary to assumption. Therefore, d = 0. But then∑k

i=1 ciui = 0 and the linear indepen-dence of {u1, · · · ,uk} implies each ci = 0 also. ■

Given a spanning set, you can delete vectors till you end up with a basis. Given a linearlyindependent set, you can add vectors till you get a basis. This is what the following theoremis about, weeding and planting.

Theorem 7.2.11 If V = span (u1, · · · ,un) then some subset of {u1, · · · ,un} is a basis forV. Also, if {u1, · · · ,uk} ⊆ V is linearly independent and the vector space is finite dimen-sional, then the set, {u1, · · · ,uk}, can be enlarged to obtain a basis of V.

Proof: LetS = {E ⊆ {u1, · · · ,un} such that span (E) = V }.

For E ∈ S, let |E| denote the number of elements of E. Let

m ≡ min{|E| such that E ∈ S}.

Thus there exist vectors{v1, · · · ,vm} ⊆ {u1, · · · ,un}

such thatspan (v1, · · · ,vm) = V

and m is as small as possible for this to happen. If this set is linearly independent, it followsit is a basis for V and the theorem is proved. On the other hand, if the set is not linearlyindependent, then there exist scalars

c1, · · · , cm

such that

0 =

m∑i=1

civi

and not all the ci are equal to zero. Suppose ck ̸= 0. Then the vector, vk may be solved forin terms of the other vectors. Consequently,

V = span (v1, · · · ,vk−1,vk+1, · · · ,vm)

contradicting the definition of m. This proves the first part of the theorem.To obtain the second part, begin with {u1, · · · ,uk} and suppose a basis for V is

{v1, · · · ,vn} .

Ifspan (u1, · · · ,uk) = V,

then k = n. If not, there exists a vector,

uk+1 /∈ span (u1, · · · ,uk) .

Then by Lemma 7.2.10, {u1, · · · ,uk,uk+1} is also linearly independent. Continue addingvectors in this way until n linearly independent vectors have been obtained. Then

span (u1, · · · ,un) = V

because if it did not do so, there would exist un+1 as just described and {u1, · · · ,un+1}would be a linearly independent set of vectors having n+1 elements even though {v1, · · · ,vn}is a basis. This would contradict Theorem 7.2.4. Therefore, this list is a basis. ■