A presentation turns a module into a list of generators subject to linear relations. Over a field, elimination reduces such a list to free coordinates. Over the integers, division may not be available, so diagonal relations can survive: an equation such as describes a cyclic summand rather than a coordinate that can be discarded. Smith normal form makes that distinction systematic.
Motivation
Suppose two generators satisfy and . Their module is . It has twelve elements but is not cyclic: every element is killed by six. The number of elements alone cannot classify a finite abelian group. We need invariants that retain the orders and arrangement of the surviving cyclic pieces.
The same problem over classifies linear operators. A polynomial relation says that a cyclic vector generates an summand. Factorizations of then express how different eigenvalue behaviors separate. The scalar ring has changed, but the mechanism remains generators, relations, and changes of basis.
A principal ideal domain is precisely strong enough for a useful diagonal reduction. Every ideal has one generator, so pairs of entries admit a greatest common divisor expressed as their linear combination. That combination can replace two incompatible entries by a better pivot. We must also explain why repeating this improvement stops; a computation that is always improvable is not yet an algorithm or an existence proof.
Definitions
For this chapter, is a commutative principal ideal domain, abbreviated PID: it is an integral domain in which every ideal is principal. The integers and are examples. We use the background facts that a PID has unique factorization into irreducibles and that irreducible elements generate maximal ideals. Both are standard consequences of the PID hypothesis; the matrix argument below does not assume a Euclidean division algorithm for an arbitrary PID.
Definition 3.1
(Unimodular matrix and presented module)
A matrix is unimodular if it is invertible over . For a square matrix over a commutative ring, this is equivalent to its determinant being a unit, by the adjugate identity. Elementary row and column operations using invertible operations are unimodular. They change bases or replace generators of the relation module and preserve the presented module.
If is an by matrix, it presents , where column vectors encode the relations. Multiplying on the left by an invertible matrix changes the coordinates of ; multiplying on the right changes the generators of . The resulting cokernels are isomorphic. Multiplying one row by a nonunit is not an allowable basis change.
Definition 3.2
(Torsion element and annihilator)
An element of an -module is torsion if some nonzero scalar kills it. Over a domain, the torsion elements form a submodule : if and , then , and . The annihilator of an element is the ideal . A cyclic module generated by is therefore isomorphic to by the first isomorphism theorem.
Theorem/proposition
Theorem 3.3
(Smith normal form)
For every finite matrix over a PID, there are unimodular such that is rectangular diagonal, with nonzero diagonal entries satisfying . The other entries are zero. The are determined up to multiplication by units by the ideals generated by the minors of .
Theorem 3.4
(Structure theorem over a PID)
Every finitely generated -module has a decomposition
where each is nonzero and not a unit, and . The integer and the factors up to associates are unique. In particular, a finitely generated torsion-free module over a PID is free.
Unit diagonal entries contribute zero quotient summands and are omitted from the structure theorem. A zero row coordinate contributes a free summand. Confusing a unit relation with a zero relation reverses these two cases: kills a generator completely, while imposes no restriction.
Proof sketch or proof idea
Proof
(Finite presentations and Smith reduction)
First, every submodule is free of finite rank at most . We prove this by induction on . Project onto its first coordinate. If its image is zero, use induction inside . Otherwise the image is with ; choose whose first coordinate is . Every has first coordinate for a unique , so has first coordinate zero. Thus , with contained in the remaining coordinates. The sum is direct because the first coordinate of is : if it is zero, the domain property gives . Induction completes the proof. Consequently the kernel of a finite free surjection onto a finitely generated module has a finite basis, giving a finite presentation.
To reduce its matrix, move a nonzero entry into the first position. For any entry below it in the first column, choose generating and coefficients with . Write and . The row operation on the two rows given by
is invertible because its determinant is . This replaces the pivot by a greatest common divisor. The analogous column operation treats entries in the first row. If the pivot already divides the entry being treated, ordinary subtraction clears that entry without changing the pivot.
Every genuine pivot improvement strictly enlarges its principal ideal: becomes when does not divide . Such enlargements cannot continue indefinitely in a PID. Indeed, the union of an ascending chain of ideals is an ideal, hence ; its generator belongs to one member of the chain, after which the chain is constant. Between genuine improvements only finitely many entries of the first row and column need clearing. Once no improvement is needed there, clear both to isolate the pivot.
If that pivot fails to divide an entry in the remaining block, add the corresponding lower row to the first row. The first position remains the pivot because the lower first-column entry is zero, while the troublesome block entry now occurs in the first row. A greatest-common-divisor column operation strictly improves the pivot. The same ascending-chain argument shows that eventually the pivot divides the entire remaining block. Isolate it and apply induction to that block. Subsequent invertible operations within the block preserve divisibility by the first pivot. Induction yields the required divisibility chain.
For uniqueness of Smith entries for a given matrix, let be the ideal generated by its by minors, with . Invertible row or column changes preserve this ideal: expansion of a minor after a change expresses it as a linear combination of old minors, and applying the inverse change gives the reverse inclusion. On a diagonal Smith matrix, for . The divisibility chain makes that product divide every other nonzero -fold diagonal product. These ideals recover each successive diagonal factor up to units.
Proof X-ray
Where the PID hypothesis does its work
The reduction uses the PID hypothesis twice, in different ways. Locally, Bézout's identity supplies the invertible operation that replaces a pivot by a gcd. Without it a Smith form may not exist at all: over the entries of the matrix generate the non-principal ideal , which would have to equal . Globally, the ascending chain condition stops the improvements: each genuine improvement strictly enlarges the ideal generated by the pivot, and a PID has no infinite strictly ascending chain of ideals. Adding a lower row to the first row is the one non-obvious move: it transfers a divisibility failure inside the block to the first row, where the gcd step can repair it. Uniqueness is a separate invariance argument: the minor ideals are unchanged by unimodular operations, so every reduction path yields the same products .
Proof
(Existence and intrinsic uniqueness of the decomposition)
The existence part of the structure theorem now follows by reading the quotient of a diagonal relation matrix coordinate by coordinate. For uniqueness independent of a chosen presentation, first pass to fractions: inverting all nonzero scalars produces a vector space over the fraction field of , of dimension . Torsion disappears under this operation, so is intrinsic. This uses only the usual localization construction; alternatively, it can be verified directly from a finite presentation over the fraction field.
For each irreducible , let . Factoring the annihilators of the finitely many cyclic torsion summands and applying the Chinese remainder theorem decomposes the torsion submodule into these primary pieces. If , then
Each cyclic summand contributes one dimension until its exponent is exhausted and then contributes zero. The dimensions of these intrinsic quotients determine every exponent and multiplicity. Sorting each prime's exponents and aligning them on the right recovers the unique invariant-factor divisibility chain. This proves module uniqueness rather than assuming a presentation was canonical.
Worked examples
Worked example 3.5
(A relation matrix over the integers)
Let . Subtract three times the first row from the second to obtain ; subtract twice the first column from the second to obtain . Change a sign to get . Thus . As checks, the first factor is the gcd of all entries, two, and the product of both factors is the absolute determinant, eight. The group has eight elements but is not cyclic because every element is killed by four.
The explorer below replays the unimodular row and column operations that reduce , checks at every step, and compares with the gcd of all minors; it also shows that is diagonal but not yet in Smith form.
Worked example 3.6
(Invariant factors versus elementary divisors)
For , the displayed factors do not form a divisibility chain. Factoring prime powers gives . Align the powers of two as and the powers of three as . Their coordinatewise products are , so . Both descriptions have 216 elements. The prime-power pieces are elementary divisors; the factors six and thirty-six are invariant factors. These are two encodings of one structure, not competing answers.
Worked example 3.7
(An operator without an eigenbasis)
Let on have a cyclic vector satisfying but . The vectors are independent: applying to a relation first kills the coefficient of , then applying kills the coefficient of , and finally the last coefficient vanishes. Thus as an -module. In the ordered basis , the matrix is a single nilpotent Jordan block. It has only the eigenvalue zero and a one-dimensional eigenspace, so no eigenbasis exists. The module relation describes exactly the information that an eigenvalue list misses.
More generally, a finite-dimensional -vector space equipped with an operator is a finitely generated torsion -module. Torsion follows because the powers of the operator are linearly dependent in the finite-dimensional space of endomorphisms, so some nonzero polynomial kills the whole space. The structure theorem gives cyclic polynomial quotients and therefore rational canonical form over any field. Jordan form requires the relevant polynomials to split into linear factors over that field. This is a hypothesis about the field and the operator, rather than a cosmetic change of notation.
Counterexample mode
Rank does not see torsion
Claim: two finitely generated -modules of the same rank are isomorphic. Compare with . Both have rank zero: once every nonzero integer is invertible, the generator of satisfies . Yet has two elements, so it is not isomorphic to . Passing to fractions recovers only ; the torsion part is recovered by the prime-power dimensions from the uniqueness proof.
Common mistakes
Common mistake
(Do not divide a relation by a nonunit)
Do not perform Gaussian elimination over by dividing a row by two. An equation contains real torsion information. Dividing it would replace by zero. Determinants used as order checks also require a square relation matrix of full rank over the fraction field; a zero determinant may signal a free part rather than a finite group of order zero.
Counterexample mode
Torsion-free without finite generation
Claim: every torsion-free -module is free. The additive group is torsion-free, since a nonzero integer times a nonzero rational is nonzero. Suppose it had a basis; the basis is nonempty because , so select a basis element . Divisibility gives with . In the finite basis expansion of , comparing the coefficients of would require an integer doubled to equal one. Hence is not free. The structure theorem does not apply because is not finitely generated over ; with finite generation restored, torsion-free does imply free.
Common mistake
(A diagonal matrix need not be in Smith form)
Reading invariant factors straight off a diagonal relation matrix requires the divisibility chain. The matrix is diagonal, but . Since and , its Smith form is . The cokernel is therefore cyclic, isomorphic to , with the single invariant factor .
Summary
Over a PID, finite presentations can be diagonalized by invertible operations. Nonunit diagonal entries give cyclic torsion summands, zero coordinates give free summands, and units give nothing. Prime-power filtrations distinguish the cyclic pieces intrinsically. For this classifies finitely generated abelian groups; for it organizes linear operators and explains when a Jordan description is available.
Exercises
Quick check
(Determine the Smith factors of and the structure of its cokernel over .)
Solution · Answer
The gcd of the entries is two, and the absolute determinant is sixty. Hence the factors are two and thirty, with . The cokernel is . It has sixty elements and exponent thirty, in agreement with the original product's least common multiple.
Quick check
(Let . Compute the dimensions of over for all and recover its elementary divisors.)
Solution · Answer
The dimensions are two for , one for , and zero thereafter. The number of exponents exactly is the difference between the dimensions for and . Thus there is one exponent two and one exponent three, giving orders four and eight. The quotient dimensions count cyclic chains still surviving at a given level, not the sizes of the subgroups themselves.
Quick check
(Explain why can correspond to a real operator with no real eigenvector when , although the operator has a matrix of size two.)
Solution · Answer
In the basis of classes , multiplication by has matrix . A real eigenvalue would satisfy , which has no real solution. Rational canonical form still applies over ; real Jordan blocks with only real eigenvalues do not. Extending scalars to changes the factorization and produces eigenvalues .
Quick check
(Show directly that every finitely generated torsion-free abelian group is free using the structure theorem. Specify where both adjectives enter.)
Solution · Answer
Finite generation invokes the PID structure theorem over , yielding plus finitely many finite cyclic factors. Every nonzero element in any such factor is torsion, so torsion-freeness forces all those factors to be absent. The result is . Dropping finite generation allows ; dropping torsion-freeness allows .