380 CHAPTER 16. VECTOR SPACES
Corollary 16.3.6 If {u1, · · · ,um} and {v1, · · · ,vn} are two bases for V, then m = n.
Proof: By Theorem 16.3.5, m≤ n and n≤ m. ■This corollary is very important so here is another proof of it given independent of the
exchange theorem above.
Theorem 16.3.7 Let V be a vector space and {u1, · · · ,uk} and {v1, · · · ,vm} are two basesfor V . Then k = m.
Proof: Suppose k > m. Then since the vectors, {u1, · · · ,uk} span V, there exist scalars,ci j such that
m
∑i=1
ci jvi = u j.
Therefore,k
∑j=1
d ju j = 0 if and only ifk
∑j=1
m
∑i=1
ci jd jvi = 0
if and only ifm
∑i=1
(k
∑j=1
ci jd j
)vi = 0
Now since{v1, · · · ,vn} is independent, this happens if and only if
k
∑j=1
ci jd j = 0, i = 1,2, · · · ,m.
However, this is a system of m equations in k variables, d1, · · · ,dk and m < k. Therefore,there exists a solution to this system of equations in which not all the d j are equal to zero.
Recall why this is so. The augmented matrix for the system is of the form(
C 0)
whereC is a matrix which has more columns than rows. Therefore, there are free variables andhence nonzero solutions to the system of equations. However, this contradicts the linearindependence of {u1, · · · ,uk} because, as explained above, ∑
kj=1 d ju j = 0. Similarly it
cannot happen that m > k. ■
Definition 16.3.8 A vector space V is of dimension n if it has a basis consisting of n vec-tors. This is well defined thanks to Corollary 16.3.6. It is always assumed here that n < ∞
and in this case, such a vector space is said to be finite dimensional.
The following says that if you add a vector which is not in the span of a linearly inde-pendent set of vectors to this set of vectors, then the resulting list is linearly independent.
Lemma 16.3.9 Suppose v /∈ span(u1, · · · ,uk) and {u1, · · · ,uk} is linearly independent.Then {u1, · · · ,uk,v} is also linearly independent.
Proof: Suppose ∑ki=1 ciui +dv = 0. It is required to verify that each ci = 0 and that d =
0. But if d ̸= 0, then you can solve for v as a linear combination of the vectors, {u1, · · · ,uk},
v =−k
∑i=1
(ci
d
)ui
contrary to assumption. Therefore, d = 0. But then ∑ki=1 ciui = 0 and the linear indepen-
dence of {u1, · · · ,uk} implies each ci = 0 also. ■