it must be the case that ±1 , . . . , ±m span W .

That proves that W is ¬nite dimensional with dimF (W ) ¤ dimF (V ). It

remains to show that these dimensions are equal if and only if W = V . Now,

if W = V , then clearly dimF (W ) = dimF (V ). Conversely, if dimF (W ) =

dimF (V ), then by Theorem 14.23, any basis for W must already span V . 2

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

then the quotient space V /W is also ¬nite dimensional, and

dimF (V /W ) = dimF (V ) ’ dimF (W ).

Proof. Suppose that S is a ¬nite set of vectors that spans V . Then {± +

W : ± ∈ S} is a ¬nite set of vectors that spans V /W . It follows from

Theorem 14.19 that V /W has a basis, say, ±1 + W, . . . , ± + W . Suppose

that β1 , . . . , βm is a basis for W . The theorem will follow immediately from

the following:

Claim. The vectors

±1 , . . . , ± , β1 , . . . , βm (14.2)

form a basis for V .

14.5 Vector spaces and dimension 313

To see that these vectors span V , consider any element γ of V . Then since

±1 + W, . . . , ± + W span V /W , we have γ ≡ i ai ±i (mod W ) for some

a1 , . . . , a ∈ F . If we set β := γ ’ i ai ±i ∈ W , then since β1 , . . . , βm span

W , we have β = j bj βj for some b1 , . . . , bm ∈ F , and hence γ = i ai ±i +

j bj βj . That proves that the vectors (14.2) span V . To prove they are

linearly independent, suppose we have a relation of the form i ai ±i +

j bj βj = 0V , where a1 , . . . , a ∈ F and b1 , . . . , bm ∈ F . If any of the ai

were non-zero, this would contradict the assumption that ±1 +W, . . . , ± +W

are linearly independent. So assume that all the ai are zero. If any of the

bj were non-zero, this would contradict the assumption that β1 , . . . , βm are

linearly independent. Thus, all the ai and all the bj must be zero, which

proves that the vectors (14.2) are linearly independent. That proves the

claim. 2

Theorem 14.26. If V is of ¬nite dimension, then any linearly independent

set of elements of V can be extended to form a basis for V .

Proof. This is actually implicit in the proof of the previous theorem. Let

β1 , . . . , βm ∈ V be linearly independent. Let W be the subspace of V

spanned by β1 , . . . , βm , so that β1 , . . . , βm form a basis for W . As in the

proof of the previous theorem, we can choose ±1 , . . . , ± ∈ V such that

±1 + W, . . . , ± + W form a basis for the quotient space V /W , so that

±1 , . . . , ± , β1 , . . . , βm

form a basis for V . 2

Example 14.23. Suppose that F is ¬nite, say |F | = q, and that V is ¬nite

dimensional, say dimF (V ) = n. Then clearly |V | = q n . If W is a subspace

with dimF (W ) = m, then |W | = q m , and by Theorem 14.25, dimF (V /W ) =

n’m, and hence |V /W | = q n’m . Just viewing V and W as additive groups,

we know that the index of W in V is [V : W ] = |V /W | = |V |/|W | = q n’m ,

which agrees with the above calculations. 2

We next consider the relation between the notion of dimension and linear

maps.

Theorem 14.27. If V is of ¬nite dimension n, and V is isomorphic to V ,

then V is also of ¬nite dimension n.

Proof. If ±1 , . . . , ±n is a basis for V , then by Theorem 14.18, ρ(±1 ), . . . , ρ(±n )

is a basis for V . 2

314 Modules and vector spaces

Theorem 14.28. If ρ : V ’ V is an F -linear map, and if V and V are

¬nite dimensional with dimF (V ) = dimF (V ), then we have:

ρ is injective if and only if ρ is surjective.

Proof. Let ±1 , . . . , ±n be a basis for V . By Theorem 14.18, we know that

ρ is injective if and only if ρ(±1 ), . . . , ρ(±n ) are linearly independent, and

that ρ is surjective if and only if ρ(±1 ), . . . , ρ(±n ) span V . Moreover, by

Theorem 14.23, we know that the vectors ρ(±1 ), . . . , ρ(±n ) are linearly inde-

pendent if and only if they span V . The theorem now follows immediately.

2

This last theorem turns out to be extremely useful in a number of set-

tings. Generally, of course, if we have a function f : A ’ B, injectivity does

not imply surjectivity, nor does surjectivity imply injectivity. If A and B

are ¬nite sets of equal size, then these implications do indeed hold. Theo-

rem 14.28 gives us another important setting where these implications hold,

with ¬nite dimensionality playing the role corresponding to ¬niteness.

Theorem 14.28 may be generalized as follows:

Theorem 14.29. If V is ¬nite dimensional, and ρ : V ’ V is an F -linear

map, then img(ρ) is a ¬nite dimensional vector space, and

dimF (V ) = dimF (img(ρ)) + dimF (ker(ρ)).

Proof. As the reader may verify, this follows immediately from Theo-

rem 14.25, together with Theorems 14.27 and 14.11. 2

Intuitively, one way to think of Theorem 14.29 is as a “law of conservation”

for dimension: any “dimensionality” going into ρ that is not “lost” to the

kernel of ρ must show up in the image of ρ.

Exercise 14.5. Show that if V1 , . . . , Vn are ¬nite dimensional vector spaces,

then V1 — · · · — Vn has dimension n dimF (Vi ).

i=1

Exercise 14.6. Show that if V is a ¬nite dimensional vector space with

subspaces W1 and W2 , such that W1 + W2 = V and W1 © W2 = {0V }, then

dimF (V ) = dimF (W1 ) + dimF (W2 ).

Exercise 14.7. The theory of dimension for ¬nitely generated vector spaces

is quite elegant and powerful. There is a theory of dimension (of sorts) for

modules over an arbitrary, non-trivial ring R, but it is much more awkward

and limited. This exercise develops a proof of one aspect of this theory: if

an R-module M has a basis at all, then any two bases have the same size.

14.5 Vector spaces and dimension 315

To prove this, we need the fact that any non-trivial ring has a maximal ideal

(this was proved in Exercise 9.30 for countable rings). Let n, m be positive

integers, let ±1 , . . . , ±m be elements of R—n , and let I be an ideal of R.

(a) Show that if ±1 , . . . , ±m span R—n , then every element of I —n can be

expressed as a1 ±1 + · · · am ±m , where a1 , . . . , am belong to I.

(b) Show that if m > n and I is a maximal ideal, then there exist

a1 , . . . , am ∈ R, not all in I, such that a1 ±1 + · · · am ±m ∈ I —n .

(c) From (a) and (b), deduce that if m > n, then ±1 , . . . , ±m cannot be

a basis for R—n .

(d) From (c), conclude that any two bases for a given R-module M must

have the same size.

15

Matrices

In this chapter, we discuss basic de¬nitions and results concerning matrices.

We shall start out with a very general point of view, discussing matrices

whose entries lie in an arbitrary ring R. Then we shall specialize to the case

where the entries lie in a ¬eld F , where much more can be said.

One of the main goals of this chapter is to discuss “Gaussian elimination,”

which is an algorithm that allows us to e¬ciently compute bases for the

image and kernel of an F -linear map.

In discussing the complexity of algorithms for matrices over a ring R, we

shall treat a ring R as an “abstract data type,” so that the running times of

algorithms will be stated in terms of the number of arithmetic operations in

R. If R is a ¬nite ring, such as Zm , we can immediately translate this into a

running time on a RAM (in later chapters, we will discuss other ¬nite rings

and e¬cient algorithms for doing arithmetic in them).

If R is, say, the ¬eld of rational numbers, a complete running time analysis

would require an additional analysis of the sizes of the numbers that appear

in the execution of the algorithm. We shall not attempt such an analysis

here”however, we note that all the algorithms discussed in this chapter do

in fact run in polynomial time when R = Q, assuming we represent rational

numbers as fractions in lowest terms. Another possible approach for dealing

with rational numbers is to use ¬‚oating point approximations. While this

approach eliminates the size problem, it creates many new problems because

of round-o¬ errors. We shall not address any of these issues here.

15.1 Basic de¬nitions and properties

Throughout this section, R denotes a ring.