3Modules

IB Groups, Rings and Modules

3.3 Matrices over Euclidean domains

This is the part of the course where we deliver all our promises about proving

the classification of finite abelian groups and Jordan normal forms.

Until further notice, we will assume R is a Euclidean domain, and we write

φ

:

R \{

0

} → Z

≥0

for its Euclidean function. We know that in such a Euclidean

domain, the greatest common divisor gcd(a, b) exists for all a, b ∈ R.

We will consider some matrices with entries in R.

Definition

(Elementary row oeprations)

.

Elementary row operations on an

m × n matrix A with entries in R are operations of the form

(i)

Add

c ∈ R

times the

i

th row to the

j

th row. This may be done by

multiplying by the following matrix on the left:

1

.

.

.

1 c

.

.

.

1

.

.

.

1

,

where c appears in the ith column of the jth row.

(ii)

Swap the

i

th and

j

th rows. This can be done by left-multiplication of the

matrix

1

.

.

.

1

0 1

1

.

.

.

1

1 0

1

.

.

.

1

.

Again, the rows and columns we have messed with are the

i

th and

j

th

rows and columns.

(iii)

We multiply the

i

th row by a unit

c ∈ R

. We do this via the following

matrix:

1

.

.

.

1

c

1

.

.

.

1

Notice that if

R

is a field, then we can multiply any row by any non-zero

number, since they are all units.

We also have elementary column operations defined in a similar fashion, corre-

sponding to right multiplication of the matrices. Notice all these matrices are

invertible.

Definition

(Equivalent matrices)

.

Two matrices are equivalent if we can get

from one to the other via a sequence of such elementary row and column

operations.

Note that if A and B are equivalent, then we can write

B = QAT

−1

for some invertible matrices Q and T

−1

.

The aim of the game is to find, for each matrix, a matrix equivalent to it

that is a simple as possible. Recall from IB Linear Algebra that if

R

is a field,

then we can put any matrix into the form

I

r

0

0 0

via elementary row and column operations. This is no longer true when working

with rings. For example, over Z, we cannot put the matrix

2 0

0 0

into that form, since no operation can turn the 2 into a 1. What we get is the

following result:

Theorem

(Smith normal form)

.

An

m × n

matrix over a Euclidean domain

R

is equivalent to a diagonal matrix

d

1

d

2

.

.

.

d

r

0

.

.

.

0

,

with the d

i

all non-zero and

d

1

| d

2

| d

3

| ··· | d

r

.

Note that the divisibility criterion is similar to the classification of finitely-

generated abelian groups. In fact, we will derive that as a consequence of the

Smith normal form.

Definition

(Invariant factors)

.

The

d

k

obtained in the Smith normal form are

called the invariant factors of A.

We first exhibit the algorithm of producing the Smith normal form with an

algorithm in Z.

Example. We start with the matrix

3 7 4

1 −1 2

3 5 1

.

We want to move the 1 to the top-left corner. So we swap the first and second

rows to obtain.

1 −1 2

3 7 4

3 5 1

.

We then try to eliminate the other entries in the first row by column operations.

We add multiples of the first column to the second and third to obtain

1 0 0

3 10 −2

3 8 −5

.

We similarly clear the first column to get

1 0 0

0 10 −2

0 8 −5

.

We are left with a 2 × 2 matrix to fiddle with.

We swap the second and third columns so that 2 is in the 2

,

2 entry, and

secretly change sign to get

1 0 0

0 2 10

0 5 8

.

We notice that (2

,

5) = 1. So we can use linear combinations to introduce a 1 at

the bottom

1 0 0

0 2 10

0 1 −12

.

Swapping rows, we get

1 0 0

0 1 −12

0 2 10

.

We then clear the remaining rows and columns to get

1 0 0

0 1 0

0 0 34

.

Proof.

Throughout the process, we will keep calling our matrix

A

, even though

it keeps changing in each step, so that we don’t have to invent hundreds of names

for these matrices.

If

A

= 0, then done! So suppose

A 6

= 0. So some entry is not zero, say,

A

ij

6

= 0. Swapping the

i

th and first row, then

j

th and first column, we arrange

that

A

11

6

= 0. We now try to reduce

A

11

as much as possible. We have the

following two possible moves:

(i)

If there is an

A

1j

not divisible by

A

11

, then we can use the Euclidean

algorithm to write

A

1j

= qA

11

+ r.

By assumption,

r 6

= 0. So

φ

(

r

)

< φ

(

A

11

) (where

φ

is the Euclidean

function).

So we subtract

q

copies of the first column from the

j

th column. Then

in position (1

, j

), we now have

r

. We swap the first and

j

th column such

that

r

is in position (1

,

1), and we have strictly reduced the value of

φ

at

the first entry.

(ii)

If there is an

A

i1

not divisible by

A

11

, we do the same thing, and this

again reduces φ(A

11

).

We keep performing these until no move is possible. Since the value of

φ

(

A

11

)

strictly decreases every move, we stop after finitely many applications. Then we

know that we must have

A

11

dividing all

A

ij

and

A

i1

. Now we can just subtract

appropriate multiples of the first column from others so that

A

1j

= 0 for

j 6

= 1.

We do the same thing with rows so that the first row is cleared. Then we have a

matrix of the form

A =

d 0 ··· 0

0

.

.

. C

0

.

We would like to say “do the same thing with

C

”, but then this would get us a

regular diagonal matrix, not necessarily in Smith normal form. So we need some

preparation.

(iii) Suppose there is an entry of C not divisible by d, say A

ij

with i, j > 1.

A =

d 0 ··· 0 ··· 0

0

.

.

.

0 A

ij

.

.

.

0

We suppose

A

ij

= qd + r,

with

r 6

= 0 and

φ

(

r

)

< φ

(

d

). We add column 1 to column

j

, and subtract

q

times row 1 from row

i

. Now we get

r

in the (

i, j

)th entry, and we want

to send it back to the (1

,

1) position. We swap row

i

with row 1, swap

column j with row 1, so that r is in the (1, 1)th entry, and φ(r) < φ(d).

Now we have messed up the first row and column. So we go back and do

(i) and (ii) again until the first row and columns are cleared. Then we get

A =

d

0

0 ··· 0

0

0 C

0

0

,

where

φ(d

0

) ≤ φ(r) < φ(d).

As this strictly decreases the value of

φ

(

A

11

), we can only repeat this finitely

many times. When we stop, we will end up with a matrix

A =

d 0 ··· 0

0

.

.

. C

0

,

and

d

divides every entry of

C

. Now we apply the entire process to

C

. When

we do this process, notice all allowed operations don’t change the fact that

d

divides every entry of C.

So applying this recursively, we obtain a diagonal matrix with the claimed

divisibility property.

Note that if we didn’t have to care about the divisibility property, we can

just do (i) and (ii), and we can get a diagonal matrix. The magic to get to the

Smith normal form is (iii).

Recall that the

d

i

are called the invariant factors. So it would be nice if we

can prove that the

d

i

are indeed invariant. It is not clear from the algorithm

that we will always end up with the same

d

i

. Indeed, we can multiply a whole

row by

−

1 and get different invariant factors. However, it turns out that these

are unique up to multiplication by units.

To study the uniqueness of the invariant factors of a matrix

A

, we relate

them to other invariants, which involves minors.

Definition

(Minor)

.

A

k ×k

minor of a matrix

A

is the determinant of a

k ×k

sub-matrix of

A

(i.e. a matrix formed by removing all but

k

rows and all but

k

columns).

Any given matrix has many minors, since we get to decide which rows and

columns we can throw away. The idea is to consider the ideal generated by all

the minors of matrix.

Definition

(Fitting ideal)

.

For a matrix

A

, the

k

th Fitting ideal

Fit

k

(

A

)

C R

is the ideal generated by the set of all k × k minors of A.

A key property is that equivalent matrices have the same Fitting ideal, even

if they might have very different minors.

Lemma. Let A and B be equivalent matrices. Then

Fit

k

(A) = Fit

k

(B)

for all k.

Proof.

It suffices to show that changing

A

by a row or column operation does

not change the Fitting ideal. Since taking the transpose does not change the

determinant, i.e.

Fit

k

(

A

) =

Fit

k

(

A

T

), it suffices to consider the row operations.

The most difficult one is taking linear combinations. Let

B

be the result of

adding

c

times the

i

th row to the

j

th row, and fix

C

a

k ×k

minor of

A

. Suppose

the resultant matrix is C

0

. We then want to show that det C

0

∈ Fit

k

(A).

If the

j

th row is outside of

C

, then the minor

det C

is unchanged. If both

the

i

th and

j

th rows are in

C

, then the submatrix

C

changes by a row operation,

which does not affect the determinant. These are the boring cases.

Suppose the

j

th row is in

C

and the

i

th row is not. Suppose the

i

th row is

f

1

, ··· , f

k

. Then C is changed to C

0

, with the jth row being

(C

j1

+ cf

1

, C

j

2

+ cf

2

, ··· , C

jk

+ cf

k

).

We compute det C

0

by expanding along this row. Then we get

det C

0

= det C + c det D,

where

D

is the matrix obtained by replacing the

j

th row of

C

with (

f

1

, ··· , f

k

).

The point is that

det C

is definitely a minor of

A

, and

det D

is still a minor of

A

, just another one. Since ideals are closed under addition and multiplications,

we know

det(C

0

) ∈ Fit

k

(A).

The other operations are much simpler. They just follow by standard properties

of the effect of swapping rows or multiplying rows on determinants. So after any

row operation, the resultant submatrix C

0

satisfies

det(C

0

) ∈ Fit

k

(A).

Since this is true for all minors, we must have

Fit

k

(B) ⊆ Fit

k

(A).

But row operations are invertible. So we must have

Fit

k

(A) ⊆ Fit

k

(B)

as well. So they must be equal. So done.

We now notice that if we have a matrix in Smith normal form, say

B =

d

1

d

2

.

.

.

d

r

0

.

.

.

0

,

then we can immediately read off

Fit

k

(B) = (d

1

d

2

···d

k

).

This is clear once we notice that the only possible contributing minors are from

the diagonal submatrices, and the minor from the top left square submatrix

divides all other diagonal ones. So we have

Corollary. If A has Smith normal form

B =

d

1

d

2

.

.

.

d

r

0

.

.

.

0

,

then

Fit

k

(A) = (d

1

d

2

···d

k

).

So d

k

is unique up to associates.

This is since we can find

d

k

by dividing the generator of

Fit

k

(

A

) by the

generator of Fit

k−1

(A).

Example. Consider the matrix in Z:

A =

2 0

0 3

.

This is diagonal, but not in Smith normal form. We can potentially apply the

algorithm, but that would be messy. We notice that

Fit

1

(A) = (2, 3) = (1).

So we know d

1

= ±1. We can then look at the second Fitting ideal

Fit

2

(A) = (6).

So d

1

d

2

= ±6. So we must have d

2

= ±6. So the Smith normal form is

1 0

0 6

.

That was much easier.

We are now going to Smith normal forms to do things. We will need some

preparation, in the form of the following lemma:

Lemma.

Let

R

be a principal ideal domain. Then any submodule of

R

m

is

generated by at most m elements.

This is obvious for vector spaces, but is slightly more difficult here.

Proof. Let N ≤ R

m

be a submodule. Consider the ideal

I = {r ∈ R : (r, r

2

, ··· , r

m

) ∈ N for some r

2

, ··· , r

m

∈ R}.

It is clear this is an ideal. Since

R

is a principle ideal domain, we must have

I = (a) for some a ∈ R. We now choose an

n = (a, a

2

, ··· , a

m

) ∈ N.

Then for any vector (

r

1

, r

2

, ··· , r

m

)

∈ N

, we know that

r

1

∈ I

. So

a | r

1

. So we

can write

r

1

= ra.

Then we can form

(r

1

, r

2

, ··· , r

m

) − r(a, a

2

, ··· , a

m

) = (0, r

2

− ra

2

, ··· , r

m

− ra

m

) ∈ N.

This lies in

N

0

=

N ∩

(

{

0

} × R

m−1

)

≤ R

m−1

. Thus everything in

N

can

be written as a multiple of

n

plus something in

N

0

. But by induction, since

N

0

≤ R

m−1

, we know

N

0

is generated by at most

m −

1 elements. So there are

n

2

, ··· , n

m

∈ N

0

generating N

0

. So n, n

2

, ··· , n

m

generate N.

If we have a submodule of

R

m

, then it has at most

m

generators. However,

these might generate the submodule in a terrible way. The next theorem tells us

there is a nice way of finding generators.

Theorem.

Let

R

be a Euclidean domain, and let

N ≤ R

m

be a submod-

ule. Then there exists a basis

v

1

, ··· , v

m

of

R

m

such that

N

is generated by

d

1

v

1

, d

2

v

2

, ··· , d

r

v

r

for some 0 ≤ r ≤ m and some d

i

∈ R such that

d

1

| d

2

| ··· | d

r

.

This is not hard, given what we’ve developed so far.

Proof.

By the previous lemma,

N

is generated by some elements

x

1

, ··· , x

n

with

n ≤ m

. Each

x

i

is an element of

R

m

. So we can think of it as a column vector

of length m, and we can form a matrix

A =

↑ ↑ ↑

x

1

x

2

··· x

n

↓ ↓ ↓

.

We’ve got an

m ×n

matrix. So we can put it in Smith normal form! Since there

are fewer columns than there are rows, this is of the form

d

1

d

2

.

.

.

d

r

0

.

.

.

0

0

.

.

.

0

Recall that we got to the Smith normal form by row and column operations.

Performing row operations is just changing the basis of

R

m

, while each column

operation changes the generators of N.

So what this tells us is that there is a new basis

v

1

, ··· , v

m

of

R

m

such

that

N

is generated by

d

1

v

1

, ··· , d

r

v

r

. By definition of Smith normal form, the

divisibility condition holds.

Corollary.

Let

R

be a Euclidean domain. A submodule of

R

m

is free of rank

at most

m

. In other words, the submodule of a free module is free, and of a

smaller (or equal) rank.

Proof.

Let

N ≤ R

m

be a submodule. By the above, there is a basis

v

1

, ··· , v

n

of

R

m

such that

N

is generated by

d

1

v

1

, ··· , d

r

v

r

for

r ≤ m

. So it is certainly

generated by at most

m

elements. So we only have to show that

d

1

v

1

, ··· , d

r

v

r

are

independent. But if they were linearly dependent, then so would be

v

1

, ··· , v

m

.

But

v

1

, ··· , v

n

are a basis, hence independent. So

d

1

v

1

, ··· , d

r

v

r

generate

N

freely. So

N

∼

=

R

r

.

Note that this is not true for all rings. For example, (2

, X

)

C Z

[

X

] is a

submodule of Z[X], but is not isomorphic to Z[X].

Theorem

(Classification of finitely-generated modules over a Euclidean domain)

.

Let R be a Euclidean domain, and M be a finitely generated R-module. Then

M

∼

=

R

(d

1

)

⊕

R

(d

1

)

⊕ ··· ⊕

R

(d

r

)

⊕ R ⊕ R ⊕ ··· ⊕ R

for some d

i

6= 0, and

d

1

| d

2

| ··· | d

r

.

This is either a good or bad thing. If you are pessimistic, this says the world

of finitely generated modules is boring, since there are only these modules we

already know about. If you are optimistic, this tells you all finitely-generated

modules are of this simple form, so we can prove things about them assuming

they look like this.

Proof.

Since

M

is finitely-generated, there is a surjection

φ

:

R

m

→ M

. So by

the first isomorphism, we have

M

∼

=

R

m

ker φ

.

Since

ker φ

is a submodule of

R

m

, by the previous theorem, there is a basis

v

1

, ··· , v

m

of

R

m

such that

ker φ

is generated by

d

1

v

1

, ··· , d

r

v

r

for 0

≤ r ≤ m

and d

1

| d

2

| ··· | d

r

. So we know

M

∼

=

R

m

((d

1

, 0, ··· , 0), (0, d

2

, 0, ··· , 0), ··· , (0, ··· , 0, d

r

, 0, ··· , 0))

.

This is just

R

(d

1

)

⊕

R

(d

2

)

⊕ ··· ⊕

R

(d

r

)

⊕ R ⊕ ···⊕ R,

with m − r copies of R.

This is particularly useful in the case where

R

=

Z

, where

R

-modules are

abelian groups.

Example. Let A be the abelian group generated by a, b, c with relations

2a + 3b + c = 0,

a + 2b = 0,

5a + 6b + 7c = 0.

In other words, we have

A =

Z

3

((2, 3, 1), (1, 2, 0), (5, 6, 7))

.

We would like to get a better description of

A

. It is not even obvious if this

module is the zero module or not.

To work out a good description, We consider the matrix

X =

2 1 5

3 2 6

1 0 7

.

To figure out the Smith normal form, we find the fitting ideals. We have

Fit

1

(X) = (1, ···) = (1).

So d

1

= 1.

We have to work out the second fitting ideal. In principle, we have to check

all the minors, but we immediately notice

2 1

3 2

= 1.

So Fit

2

(X) = (1), and d

2

= 1. Finally, we find

Fit

3

(X) =

2 1 5

3 2 6

1 0 7

= (3).

So d

3

= 21. So we know

A

∼

=

Z

(1)

⊕

Z

(1)

⊕

Z

(3)

∼

=

Z

(3)

∼

=

C

3

.

If you don’t feel like computing determinants, doing row and column reduction

is often as quick and straightforward.

We re-state the previous theorem in the specific case where

R

is

Z

, since this

is particularly useful.

Corollary

(Classification of finitely-generated abelian groups)

.

Any finitely-

generated abelian group is isomorphic to

C

d

1

× ··· × C

d

r

× C

∞

× ··· × C

∞

,

where C

∞

∼

=

Z is the infinite cyclic group, with

d

1

| d

2

| ··· | d

r

.

Proof.

Let

R

=

Z

, and apply the classification of finitely generated

R

-modules.

Note that if the group is finite, then there cannot be any

C

∞

factors. So it

is just a product of finite cyclic groups.

Corollary. If A is a finite abelian group, then

A

∼

=

C

d

1

× ···C

d

r

,

with

d

1

| d

2

| ··· | d

r

.

This is the result we stated at the beginning of the course.

Recall that we were also to decompose a finite abelian group into products of

the form

C

p

k

, where

p

is a prime, and we said it was just the Chinese remainder

theorem. This is again in general true, but we, again, need the Chinese remainder

theorem.

Lemma

(Chinese remainder theorem)

.

Let

R

be a Euclidean domain, and

a, b ∈ R be such that gcd(a, b) = 1. Then

R

(ab)

∼

=

R

(a)

×

R

(b)

as R-modules.

The proof is just that of the Chinese remainder theorem written in ring

language.

Proof. Consider the R-module homomorphism

φ :

R

(a)

×

R

(b)

→

R

(ab)

by

(r

1

+ (a), r

2

+ (b)) 7→ br

1

+ ar

2

+ (ab).

To show this is well-defined, suppose

(r

1

+ (a), r

2

+ (b)) = (r

0

1

+ (a), r

0

2

+ (b)).

Then

r

1

= r

0

1

+ xa

r

2

= r

0

2

+ yb.

So

br

1

+ ar

2

+ (ab) = br

0

1

+ xab + ar

0

2

+ yab + (ab) = br

0

1

+ ar

0

2

+ (ab).

So this is indeed well-defined. It is clear that this is a module map, by inspection.

We now have to show it is surjective and injective. So far, we have not used

the hypothesis, that

gcd

(

a, b

) = 1. As we know

gcd

(

a, b

) = 1, by the Euclidean

algorithm, we can write

1 = ax + by

for some x, y ∈ R. So we have

φ(y + (a), x + (b)) = by + ax + (ab) = 1 + (ab).

So 1 ∈ im φ. Since this is an R-module map, we get

φ(r(y + (a), x + (b))) = r · (1 + (ab)) = r + (ab).

The key fact is that

R/

(

ab

) as an

R

-module is generated by 1. Thus we know

φ

is surjective.

Finally, we have to show it is injective, i.e. that the kernel is trivial. Suppose

φ(r

1

+ (a), r

2

+ (b)) = 0 + (ab).

Then

br

1

+ ar

2

∈ (ab).

So we can write

br

1

+ ar

2

= abx

for some

x ∈ R

. Since

a | ar

2

and

a | abx

, we know

a | br

1

. Since

a

and

b

are

coprime, unique factorization implies a | r

1

. Similarly, we know b | r

2

.

(r

1

+ (a), r

2

+ (b)) = (0 + (a), 0 + (b)).

So the kernel is trivial.

Theorem

(Prime decomposition theorem)

.

Let

R

be a Euclidean domain, and

M be a finitely-generated R-module. Then

M

∼

=

N

1

⊕ N

2

⊕ ··· ⊕ N

t

,

where each N

i

is either R or is R/(p

n

) for some prime p ∈ R and some n ≥ 1.

Proof. We already know

M

∼

=

R

(d

1

)

⊕ ··· ⊕

R

(d

r

)

⊕ R ⊕ ···⊕ R.

So it suffices to show that each R/(d

1

) can be written in that form. We let

d = p

n

1

1

p

n

2

2

···p

n

k

k

with

p

i

distinct primes. So each

p

n

i

i

is coprime to each other. So by the lemma

iterated, we have

R

(d

1

)

∼

=

R

(p

n

1

1

)

⊕ ··· ⊕

R

(p

n

k

k

)

.