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 operations). 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 as 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 use 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
2
)
⊕ ··· ⊕
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
= 3. 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
)
.