Jordan normal form

1 Principal ideal domains

A commutative ring R is an integral domain if it has no zero divisors, i.e., a · b = 0 for some a, b ∈ R
implies a = 0 or b = 0. An integral domain R is a principal ideal domain (PID) if every ideal in R
is generated by a single element. Examples of PID-s include Z and polynomial rings F [x] of a single
variable over a field F . Both examples have a norm function N : R \ {0} → N that satisfies the
Euclidean property: for all a ∈ R and b ∈ R \ {0} there is a q ∈ R and and r ∈ R such that a = qb + r
and r = 0 or N (r) < N (b). (For R = Z, the norm function may be chosen to be the absolute value,
for R = F [x] the norm function may be chosen as the degree function.) Such domains are called
Euclidean domains and they have a Euclidean algorithm.

Lemma 1 Every Euclidean domain R is a PID.

Proof: Let I be a nonzero ideal of R and let b ∈ I \ {0} be an element whose norm is smallest among
the norms of elements of I \ {0}. We claim that I = (b). In fact, for any a ∈ I, we may write a = qb + r
such that r = 0 or N (r) < N (b). If r = 0 then a = qb ∈ (b). If r 6= 0 then r = a − qb ∈ I \ {0} has
smaller norm than b, in contradiction with the choice of b. Thus we must have a ∈ (b) for all a ∈ I,
and so I ⊆ (b). The other inclusion (b) ⊆ I is obvious. 3

An element p ∈ R is prime if p | ab implies p | a or p | b. An element i ∈ R is irreducible if it can not

be written in the form i = i1 · i2 without at least one of i1 and i2 being a unit (=a divisor of 1). If
a = ub where u is a unit, then we call a and b associates and use the notation a ∼ b. It is easy to see
that ∼ is an equivalence relation, and that a ∼ b if and only if (a) = (b).

Lemma 2 In every integral domain R all primes are irreducible.

Proof: Assume p is a prime and p = a · b. Then either p | a or p | b, w.l.o.g. p | a. Thus a = r · p

for some r ∈ R, and we have p = rpb. Since R is an integral domain, we may simplify by p and get
1 = rb. Thus b is a unit, a ∼ p. 3

1
In a PID the converse holds as well.

Lemma 3 In a PID every irreducible is prime.

Proof: Assume p is irreducible and that p | a · b. If p | a, we are done. Otherwise, consider the ideal
(p, a). This is generated by a single element d. The element p is irreducible and a multiple of d, thus
either d ∼ p or d is a unit. If d ∼ p then d | a implies p | a, a contradiction. Thus d must be a unit,
w.l.o.g. d = 1. Hence (p, a) = (1) and so (pb, ab) = (b). Now p divides pb and ab, so p divides b. 3

Theorem 1 Every PID R is a unique factorization domain (UFD): every r ∈ R may be written as a
product of powers of primes. This decomposition is unique up to taking associates.

2 Finitely generated modules over principal ideal domains

An R-module M is finitely generated if there is a finite set {m1 , . . . , mk } ⊆ M such that each m ∈ M
may be written as m = r1 m1 + · · · + rk mk for some r1 , . . . , rk ∈ R. An R-module is cyclic if it is
generated by a single element of M .

The main theorem is the following.

Theorem 2 Let R be a PID and M a finitely generated R-module. Then M may be written as a
finite direct sum of cyclic modules M1 ⊕ · · · ⊕ Mk such that each Mi is either isomorphic to R (torsion
free), or to R/(pα ) for some prime power pα . This decomposition is unique up to the numbers of Mi ’s
that are isomorphic to R or a given R/(pα ).

Example 1 Every Abelian group is a Z-module. Thus we obtain that every finitely generated Abelian
group is a direct sum of copies of Z and copies of Zpα ’s, and that this decomposition is essentially
unique.

Our main application of Theorem 2 is to show that every linear operator T : V → V on finite
dimensional complex vector space V has a Jordan normal form. For that purpose consider first a
finite dimensional vector space V over an arbitrary field and a linear map T : V → V .

Lemma 4 The scalar multiplication defined as p(x)·v := p(T )(v) turns V into a unitary F [x]-module.

2
Since F [x] is a PID, Theorem 2 is applicable, and we may write V as a direct sum of cyclic F [x]-
modules.

Lemma 5 A subspace U ≤ V is an F [x]-submodule if and only if it is a T -invariant subspace.

Lemma 6 A subspace U ≤ V is a cyclic F [x]-module if and only if it is a T -cyclic submodule of V .

Note that, no cyclic F [x]-submodule of V can be isomorphic to F [x], since V is a finite dimensional, and
F [x] is an infinite dimensional vector space. Thus every cyclic F [x]-submodule U of V is appearing in
this instance of Theorem 2 is isomorphic to F [x]/(p(x)α ) for some irreducible polynomial p(x) ∈ F [x].
Note that the characteristic polynomial of x acting on F [x]/(p(x)α ) is p(x)α .

Assume from now on that F = C. Every irreducible polynomial of C[x] is linear. Thus every
cyclic C[x]-submodule appearing in Theorem 2 applied to R = C[x] is of the form C[x]/((x − λ)α for
some λ ∈ C and α ∈ N. Let v be the generator of such a submodule U . Then v, (T − λI)v, . . . ,
(T − λI)α−1 v are linearly independent, whereas (T − λI)α v = 0. The submodule U is the linear span
of v, (T − λI)v, . . . , (T − λI)α−1 v, and these vectors form a basis of U . Since

T (T − λI)k (v) = (T − λI)k+1 (v) + λ(T − λI)k (v) for k = 1, 2, . . . , α − 1.

the matrix of TU in this basis is

 
λ 0 0 ··· 0
0

 1 λ 0 ··· 0 
0 

 0 1 λ ··· 0 
0 
 ..  .

 0 0 1 λ . 

.. .. .. .. . 
. .. 

 . . .
0 0 ... 0 1 λ

Such a matrix is called a Jordan block. Theorem 2 implies that the matrix of every linear map
T : V → V on a finite dimensional complex vector space V may be written as a block-diagonal matrix
of Jordan blocks.

3 The proof of the main theorem

In this section R is a PID.

Lemma 7 Let P be an n×n matrix with entries from R. Then P has an inverse if and only if det(P )
is a unit.

3
Proof: If P · Q = I then det(P ) det(Q) = 1. Conversely, if det(P ) is a unit, then det(P )−1 ∈ R and
P −1 may be obtained “using Cramer’s rule”. 3

Lemma 8 Assume that the ideal (r1 , . . . , rn ) is generated by the single element δ. (“The GCD of
r1 , . . . , rn is δ”). Then there is an n × n matrix with entries from R whose first row is r1 , . . . , rn and
whose determinant is δ.

Proof: Induction on n. Assume the Lemma is true for some n, and consider (r1 , . . . , rn+1 ) = (δn+1 ).
Introducing δn for a generator of (r1 , . . . , rn ) we may write δn+1 = δn · ξ + rn+1 · η for some ξ, η ∈ R. By
our induction hypothesis there is an n × n matrix whose first row is r1 , . . . , rn and whose determinant
is δn . Add now (−ηr1 /δn , . . . , −ηrn /δn , ξ) as the last row to the matrix and (rn+1 , 0, . . . , 0, ξ)T as the
last column, to obtain the following matrix:
 
r1 ··· rn rn+1

 0 
 .. 

 . 

 0 
−ηr1 /δn · · · −ηrn /δn ξ

Expanding by the last column yields that the determinant of this matrix is ξ · δn + rn+1 · η = δn+1 . 3

Lemma 9 Assume A is an n × n matrix with entries from R. Then there are invertible matrices P
and Q with entries from R such that P AQ is a diagonal matrix diag(α1 , . . . , αn ) such that αi | αi+1
holds for i = 1, 2, . . . , n − 1.

Proof: We proceed by induction on n. Let (r1 , . . . , rn )T be the first column of A and assume that a
generator of the ideal (r1 , . . . , rn ) is α = ξ1 r1 + · · · ξn rn . Then we have
r1 rn
1 = ξ1 + · · · ξn
α α
and so (ξ1 , . . . , ξn ) = 1. By Lemma 8, there is a matrix whose first row is (ξ1 , . . . , ξn ) and whose
determinant is 1. By Lemma 7 such a matrix is invertible. Multiplying A by such a matrix from the
right we obtain a matrix whose first column contains the GCD of the column entries in its first row.
Repeat the same procedure for the first row, and we obtain a new matrix whose first row contains the
GCD of the row entries in the first column. Now repeat the same procedure for the first column again
and so on. At the end of each phase the first row first column entry becomes a divisor of the first row
first column entry of the previous phase. Since R has unique factorization, this procedure can not
keep giving proper divisors for ever, since the number of prime factors (counted with multiplicities) of

4
the first row first entry can not decrease indefinitely. Hence after finitely many steps we obtain a first
row first column entry δ that divides all entries in the first row and all entries in the first column. If
δ does not divide all entries in the matrix, say it does not divide an entry in the k-th row, exchange
the first and the k-th row and restart the procedure. (Note that δ remains in the first column, so
after two steps we get a proper divisor of δ in the first row first column.) Again, we can not have an
infinite descending chain of proper divisors, thus after finitely many steps we arrive at a matrix whose
only nonzero entry in the first row and in the first column is the first row, first column entry α1 that
divides all other entries in the matrix. By our induction hypothesis, we may transform the matrix
formed by rows 2, 3, . . . , n and columns 2, 3, . . . , n into a diagonal matrix diag(α2 , . . . , αn ) such that
αi | αi+1 holds for i = 2, . . . , n − 1. 3

Lemma 10 The entries α1 , . . . , αn in the previous lemma are unique, up to taking associates.

Proof: Let ∆i (A) be the GCD of all i × i minors of A. Using Cauchy-Binet, it is easy to show that
∆i (AB) is a multiple of ∆i (A) for all n × n matrix A with entries in R. Assume now B = P AQ where
P and Q are invertible. From B = P AQ we have ∆i (A) | ∆i (B) for all i, from A = P −1 BQ−1 we have
∆i (B) | ∆i (A) for all i. Thus ∆i (B) ∼ ∆i (A) for all i. Assume now that B is diag(α1 , . . . , αn ) such
that αi | αi+1 holds for i = 1, 2, . . . , n − 1. Then ∆i (B) = α1 · · · αi and so we must have α1 ∼ ∆1 (A)
and αi ∼ ∆i (A)/∆i−1 (A) for i = 2, . . . , n. 3

An R-module is free if it is the direct sum of modules isomorphic to R.

Proposition 1 Assume M is a free R-module, isomorphic to the direct sum of n-copies of R. Then
every submodule N of M is free.

Proof: First we show by induction on n that N may be generated by n elements. Consider the set

I := {r ∈ R : ∃r2 , . . . , rn ∈ R (r, r2 , · · · , rn ) ∈ N }.

Obviously, I is an ideal of R. Since R is a PID, I is generated by an element ε. By the definition

of I, there are entries ε2 , . . . , εn such that (ε, ε2 , . . . , εn ) ∈ N . Furthermore, for any (r1 , . . . , rn ) ∈ N
the first coordinate r1 is a multiple of ε. Subtracting the appropriate multiple of (ε, ε2 , . . . , εn ) from
(r1 , . . . , rn ) we get an element of N whose first coordinate is zero. We obtained that N is generated
by (ε, ε2 , . . . , εn ) and the submodule

N0 := {(r1 , . . . , rn ) ∈ N : r1 = 0}.

By our induction hypothesis, N0 may be generated by n − 1 elements, and so N may be generated by

n elements.

5
 Assume now that N is generated by f1 , . . . , fn and that M is freely generated by e1 , . . . , en . Then
Pn
each fi may be uniquely written as fi = j=1 ai,j ej . Let us denote the matrix with entries ai,j
by A. By Lemma 9 there are invertible matrices P and Q such that P AQ is a diagonal matrix
diag(α1 , . . . , αn ) such that αi | αi+1 holds for i = 1, 2, . . . , n − 1. Replacing A with P AQ corresponds
to replacing the basis e1 , . . . , en of M by some basis e01 , . . . , e0n and and the generating system f1 , . . . , fn
by some generating system f10 , . . . , fn0 . (Note that e01 , . . . , e0n is still a basis since any nontrivial linear
relation r1 · e01 + · · · + rn e0n = 0 would induce a nontrivial linear relation among the ej -s.) Assume that
α1 , . . . , αk 6= 0 but αk+1 = · · · = αn = 0. This implies fk+1 0 = · · · = fn0 = 0 and that for j ≤ k, fj0 is a
nonzero multiple of e0j . As a consequence N is freely generated by f10 , . . . , fk0 . 3

Theorem 3 Every finitely generated R-module M has a finite basis, i.e., it is the direct sum of finitely
many cyclic R-modules.

Proof: Assume M is generated by u1 , . . . , un . Consider the homomorphism φ : Rn → M , sending

(r1 , . . . , rn ) into r1 u1 + · · · + rn un . By the proof of the previous Proposition, the kernel of φ is a free
submodule of Rn , and Rn has a basis e01 , . . . , e0n such that α1 e01 , . . . , αk e0k form a basis of the kernel of
φ for some integer k and some α1 , . . . , αk ∈ R. Consider now the generating system φ(e01 ), . . . , φ(e0n )
of M . We have
r1 φ(e01 ) + · · · + rn φ(e0n ) = 0

if and only if r1 e01 + · · · + rn e0n belongs to the kernel of φ which is equivalent to

r1 e01 + · · · + rn e0n = s1 α1 e01 + · · · + sk αk e0k

for some s1 , . . . , sk ∈ R. Since e01 , . . . , e0n is a free basis of Rn , this is only possible if rk+1 = · · · = rn = 0
and rj = sj αj for j ≤ k. But then we have

r1 φ(e01 ) = · · · = rn φ(e0n ) = 0

component-wise. 3

Proposition 2 Every cyclic R module is either isomorphic to R or isomorphic to a direct sum of

R-modules isomorphic to cyclic modules of the form R/(pα ) where p is a prime in R.

Proof: If M = (m) is a cyclic R-module then the kernel of the surjective homomorphism R → M
sending 1 into m is an ideal I of R and M is isomorphic to R/I. If I = 0 then M is isomorphic to
R, otherwise M is isomorphic to R/(r) for some r ∈ R \ {0}. This element r has a unique prime

6
factorization r = pα1 1 · · · pαk k and it is easy to see that R/(r) is isomorphic to R/(pα1 1 ) × · · · × R/(pαk k )
(“Chinese remainder theorem”). 3

As a consequence of Theorem 3 and Proposition 2 we have the existence part of Theorem 2. For the
uniqueness part let us introduce the submodule of torsion elements

T (M ) := {m ∈ M : ∃r ∈ R \ {0} rm = 0}.

It is easy to see that T (M ) is a submodule and that M/T (M ) is torsion free, i.e., T (M/T (M )) = 0.
Thus M/T (M ) is the direct sum of finitely many copies of R, and the number of these copies must
be the same irrespective of the basis, otherwise the transition matrix from one basis to the other can
not be invertible. Thus we may assume that T (M ) = M , i.e., each element of M is a torsion element.
Given a prime p ∈ R, the direct sum of all summands of isomorphic to R/(pα ) for some α forms the
submodule
Mp := {m ∈ M : ∃k ≥ 0 pk · m = 0}.

Here Mp is a submodule of M , defined in a “basis independent” way. Thus we may assume M = Mp

for some prime p ∈ R. Let us introduce now the submodules

Nk := {m ∈ M : pk · · · m = 0}.

Since M = Nk , for some appropriately high value of k, it is sufficient to show the uniqueness by
induction on k. If M = N1 , then M is a vector space over the field R/(p), and so all of its bases have
the same number of elements. Assume the statement is true for M = Nk−1 and consider M = Nk .
Assume a basis of M is of the form a1 , . . . ar ; b1 , . . . , bs where pai = 0 for all i and pbj 6= 0 for all j.
Then pb1 , . . . pbs is a basis of pM , a module satisfying pk−1 m = 0 for all m ∈ pM . By our induction
hypothesis the uniqueness holds for the orders of pb1 , . . . pbs . The submodule

M [p] := {m ∈ M : pm = 0}

has basis
|b1 | |bs |
a1 , . . . , ar , b1 , . . . , bs .
p p
Here |b| is the generator of the ideal {r ∈ R : rb = 0}. The elements |bp1 | b1 , . . . , |bps | bs form a basis
of M [p] ∩ pM . Thus a1 , . . . , ar is a basis of M [p]/(M [p] ∩ pM ), a vector space over R/(p). Thus
uniqueness holds also for a1 , . . . , ar .