From a relation matrix to a group structure
Every integer matrix can be brought by row and column unimodular operations to a diagonal form whose entries divide one another successively. These invariant factors are unique, and they determine the isomorphism class of the quotient group presented by the matrix. This is the mechanism by which a class group's structure — not merely its order — is extracted from a matrix of relations between prime ideals.
Learning objectives
- State the SNF and the divisibility condition on its entries.
- Read a finitely generated abelian group's structure from an SNF.
- Distinguish invariant factors from elementary divisors.
- Apply the SNF to a relation matrix to determine class group structure.
- Understand why the SNF is more expensive than the HNF.
Section 01The form and its invariants
For any A ∈ ℤm×n there are unimodular U, V with
The di are the invariant factors and are unique. They can be characterised without reference to the algorithm: the product of the first k is the GCD of all k×k minors of A. That characterisation is what proves uniqueness, and it also provides an independent check on a computed result.
The HNF uses row operations only, preserving the row module. The SNF uses row and column operations, so it does not preserve the module — it preserves only the quotient. That is exactly why it reveals group structure and the HNF does not.
Section 02Structure of finitely generated abelian groups
If A is the relation matrix of a group presented by n generators, then
Entries equal to 1 contribute trivial factors and are discarded; zero columns contribute free rank. For a finite group the free part is absent and the order is the product of the invariant factors.
| SNF diagonal | Group | Interpretation |
|---|---|---|
| (1, 1, 1) | Trivial | Relations generate everything — e.g. class number 1 |
| (1, 1, 12) | ℤ/12ℤ | Cyclic of order 12 |
| (1, 2, 4) | ℤ/2 ⊕ ℤ/4 | Order 8, non-cyclic — two invariants |
| (1, 0, 0) | ℤ2 | Free rank 2 — e.g. a unit lattice of rank 2 |
| (2, 2, 6) | ℤ/2 ⊕ ℤ/2 ⊕ ℤ/6 | Order 24, 2-rank of 3 |
Invariant factors form a divisibility chain; elementary divisors are their prime-power components. (1, 2, 4) has invariant factors 2 and 4 and elementary divisors 2, 4. Both describe the same group; publications differ in which they report, so always check which convention is in use before comparing results.
Section 03Application to class groups
- Stage 01Collect relationsFind multiplicative relations among the ideals of a factor base, each recorded as an exponent vector.
- Stage 02Form the matrixRows are relations, columns are factor base primes.
- Stage 03Compute the SNFThe invariant factors give the class group structure; their product is the class number of the group generated by the factor base.
- Stage 04VerifyCompare h · R against the analytic class number formula. Agreement is the standard evidence that enough relations were collected.
If relation collection stops early, the SNF returns the structure of a proper subgroup of the class group — a perfectly well-formed answer that is simply wrong. There is no internal signal of the shortfall. Only the analytic comparison detects it, which is why that check is part of the algorithm rather than an optional extra.
Section 04Computational cost
The SNF is more expensive than the HNF and suffers worse entry growth, because eliminating in both directions repeatedly reintroduces entries that had already been cleared.
HNF first
Reduce to HNF, then run the SNF on the triangular result. Substantially cheaper than attacking the original matrix directly.
Modulo the determinant
Work modulo a known multiple of the largest invariant factor, bounding all entries.
Prime by prime
Determine the p-rank for each relevant prime separately, then assemble. Often the fastest route when only the structure at a few primes is wanted.
ReferenceFrequently asked questions
Can the SNF be computed without the transformation matrices?
Yes, and it should be when only the group structure is wanted. The transformation matrices are much larger than the SNF itself and computing them can dominate the total cost.
How do I check an SNF result?
Use the minor characterisation: the product of the first k invariant factors must equal the GCD of all k×k minors. Checking the first invariant factor — the GCD of all entries — is cheap and catches many errors immediately.
Does the SNF work over other rings?
Over any principal ideal domain, yes — including polynomials over a field, where it gives the rational canonical form of a matrix. Over rings that are not PIDs, the form generally does not exist.
NavigateContinue in this stream
Curated next steps from this page. The site also surfaces algorithmically related reading below.
ProvenanceSources and further reading
This page is an original KEVOS explanatory article. It presents the underlying mathematics — definitions, algorithms, complexity results and selection criteria — in KEVOS editorial voice. No text is reproduced from any copyrighted source. Where numerical tables are relevant, KEVOS links to live authoritative databases rather than republishing static values.