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. ■