16.3. LINEAR INDEPENDENCE AND BASES 381

Theorem 16.3.10 If V = span(u1, · · · ,un) then some subset of {u1, · · · ,un} is a basis for V.Also, if {u1, · · · ,uk} ⊆V is linearly independent and the vector space is finite dimensional,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 from Lemma 16.3.9, {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 not, there would exist un+1 as just described and {u1, · · · ,un+1} would be lin-early independent having n+ 1 elements even though {v1, · · · ,vn} is a basis. This wouldcontradict Theorem 16.3.5. Therefore, this list is a basis. ■

Theorem 16.3.11 Let V be a nonzero subspace of a finite dimensional vector space W ofdimension n. Then V has a basis with no more than n vectors.