M.

14.5 Vector spaces and dimension 309

Proof. (i) follows immediately from part (i) of Theorem 14.16. (ii) follows

from part (ii) of Theorem 14.16 and Theorem 14.17. (iii) follows from (i)

and (ii). 2

Exercise 14.1. Show that if a ¬nite collection of elements of an R-module

is linearly independent, then any sub-collection is also linearly independent.

Exercise 14.2. Assume R is non-trivial. Show that if a ¬nite collection of

elements of an R-module contains the zero element, or contains two identical

elements, then it is not linearly independent.

Exercise 14.3. Assume R is trivial and that M is an R-module (which

must also be trivial). Show that any ¬nite collection of zero or more copies

of 0M is a basis for M .

Exercise 14.4. Let ρ : M ’ M be an R-linear map. Show that if

±1 , . . . , ±n ∈ M are linearly dependent, then ρ(±1 ), . . . , ρ(±n ) ∈ M are

also linearly dependent.

14.5 Vector spaces and dimension

Throughout this section, F denotes a ¬eld.

A module over a ¬eld is also called a vector space. In particular, an

F -module is called an F -vector space, or a vector space over F .

For vector spaces over F , one typically uses the terms subspace and

quotient space, instead of (respectively) submodule and quotient module;

likewise, one usually uses the terms F -vector space homomorphism,

isomorphism and automorphism, as appropriate.

Throughout the rest of this section, V denotes a vector space over F .

We now develop the basic theory of dimension for ¬nitely generated vector

spaces. The following two theorems provide the keys to this theory.

Theorem 14.19. If V is ¬nitely generated, then any ¬nite set of vectors

that spans V contains a subset that is a basis.

Proof. We give an “algorithmic” proof. Let ±1 , . . . , ±n be a given set of

vectors that spans V . Let S0 be the empty set, and for i = 1, . . . , n, do

the following: if ±i does not belong to the subspace spanned by Si’1 , set

Si := Si’1 ∪ {±i }, and otherwise, set Si := Si’1 . We claim that Sn is a basis

for V .

First, we show that Sn spans V . To do this, ¬rst note that for i = 1, . . . , n,

if ±i is not in Sn , then by de¬nition, ±i is a linear combination of vectors in

310 Modules and vector spaces

Si’1 ⊆ Sn . In any case, each ±i is a linear combination of the vectors in Sn .

Since any element β of V is a linear combination of ±1 , . . . , ±n , and each

±i is a linear combination of elements of Sn , it follows (see Example 14.12)

that β is a linear combination of elements of Sn .

Second, we show that Sn is linearly independent. Suppose it were not.

Then we could express 0V as a non-trivial linear combination of elements in

Sn . Let us write this as

0V = a1 ±1 + a2 ±2 + · · · + an ±n ,

where the only non-zero coe¬cients ai are those with ±i ∈ Sn . If j is the

highest index with aj = 0F , then by de¬nition ±j ∈ Sn . However, we see

that ±j is in fact in the span of Sj’1 ; indeed,

±j = (’a’1 a1 )±1 + · · · + (’a’1 aj’1 )±j’1 ,

j j

and by de¬nition, the only terms with non-zero coe¬cients are those corre-

sponding to the vectors in Sj’1 . This means that we would not have added

±j to Sj at step j, which means ±j is not in Sn , a contradiction. 2

Theorem 14.20. If V has a basis of size n, then any collection of n + 1

elements of V is linearly dependent.

Proof. Let ±1 , . . . , ±n be a basis, and let β1 , . . . , βn+1 be any collection of

n + 1 vectors. We wish to show that β1 , . . . , βn+1 are linearly dependent.

Since the ±i span V , we know that β1 is a linear combination of the ±i , say,

β1 = a1 ±1 +· · · an ±n . If all the ai were zero, then we would have β1 = 0V , and

so trivially, β1 , . . . , βn+1 would be linearly dependent (see Exercise 14.2). So

assume that not all ai are zero, and for convenience, let us say that a1 = 0F .

It follows that ±1 is a linear combination of β1 , ±2 , . . . , ±n ; indeed,

±1 = a’1 β1 + (’a’1 a2 )±2 + · · · + (’a’1 an )±n .

1 1 1

It follows that β1 , ±2 , . . . , ±n span V (see Example 14.12).

Next, consider β2 . This is a linear combination of β1 , ±2 , . . . , ±n , and

we may assume that in this linear combination, the coe¬cient of one of

±2 , . . . , ±n is non-zero (otherwise, we ¬nd a linear dependence among the

βj ), and for convenience, let us say that the coe¬cient of ±2 is non-zero. As

in the previous paragraph, it follows that β1 , β2 , ±3 , . . . , ±n span V .

Continuing in this way, we ¬nd that β1 , . . . , βn are either linearly depen-

dent or they span V . In the latter case, we ¬nd that βn+1 is a linear com-

bination of β1 , . . . , βn , and hence, the vectors β1 , . . . , βn , βn+1 are linearly

dependent. 2

14.5 Vector spaces and dimension 311

We stress that the proofs of Theorems 14.19 and 14.20 both made critical

use of the assumption that F is a ¬eld. An important corollary of Theo-

rem 14.20 is the following:

Theorem 14.21. If V is ¬nitely generated, then any two bases have the

same size.

Proof. If one basis had more elements than another, then Theorem 14.20

would imply that the ¬rst basis was linearly dependent, which contradicts

the de¬nition of a basis. 2

Theorem 14.21 allows us to make the following de¬nition:

De¬nition 14.22. If V is ¬nitely generated, the common size of any basis

is called the dimension of V , and is denoted dimF (V ).

Note that from the de¬nitions, we have dimF (V ) = 0 if and only if V is

the trivial vector space (i.e., V = {0V }). We also note that one often refers

to a ¬nitely generated vector space as a ¬nite dimensional vector space.

We shall give preference to this terminology from now on.

To summarize the main results in this section up to this point: if V is ¬nite

dimensional, it has a basis, and any two bases have the same size, which is

called the dimension of V . The next theorem is simple consequences of these

results.

Theorem 14.23. Suppose that V is of ¬nite dimension n, and let

±1 , . . . , ±n ∈ V . The following are equivalent:

(i) ±1 , . . . , ±n are linearly independent.

(ii) ±1 , . . . , ±n span V .

(iii) ±1 , . . . , ±n form a basis for V .

Proof. Let W be the subspace spanned by ±1 , . . . , ±n .

First, let us show that (i) implies (ii). Suppose ±1 , . . . , ±n are linearly

independent. Also, by way of contradiction, suppose that W V . Choose

β ∈ V \ W . Then it follows that ±1 , . . . , ±n , β are linearly independent;

indeed, if we had a relation 0V = a1 ±1 + · · · + an ±n + bβ, then we must have

b = 0F (otherwise, β ∈ W ), and by the linear independence of ±1 , . . . , ±n ,

all the ai must be zero as well. But then we have a set of n + 1 linearly

independent vectors in V , which is impossible by Theorem 14.20.

Second, let us prove that (ii) implies (i). Let us assume that ±1 , . . . , ±n are

linearly dependent, and prove that W V . By Theorem 14.19, we can ¬nd a

basis for W among the ±i , and since the ±i are linearly dependent, this basis

312 Modules and vector spaces

must contain strictly fewer than n elements. Hence, dimF (W ) < dimF (V ),

and therefore, W V .

The theorem now follows from the above arguments, and the fact that,

by de¬nition, (iii) holds if and only if both (i) and (ii) hold. 2

We next examine the dimension of subspaces of ¬nite dimensional vector

spaces.

Theorem 14.24. If V is ¬nite dimensional, and W is a subspace of V ,

then W is also ¬nite dimensional, and dimF (W ) ¤ dimF (V ). Moreover,

dimF (W ) = dimF (V ) if and only if W = V .

Proof. To see this, suppose dimF (V ) = n, and assume that W is non-trivial.

We shall construct a basis ±1 , . . . , ±m for W , where m ¤ n. We can take ±1

to be any non-zero vector in W , ±2 to be any vector in W not in the subspace

spanned by ±1 , and so on. More generally, at stage i = 1, 2, . . . , we take ±i to

be any element of W not in the subspace spanned by ±1 , . . . , ±i’1 . It is easy

to see that at each stage i, the vectors ±1 , . . . , ±i are linearly independent:

if we had a relation a1 ±1 + · · · aj ±j = 0V , where j ¤ i and aj = 0F , this

would imply that ±j lies in the subspace generated by ±1 , . . . , ±j’1 , which

contradicts the de¬nition of how ±j was selected. Because of Theorem 14.20,