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.