Integer Matrix Normal Forms
Recovering Abelian Group Structure from a Relation Matrix
Recovering the structure and explicit generators of a finite abelian group from a matrix of relations among a generating set.
Engineering / MathematicsInteger Matrix Normal Forms2 min readKV-MATH-0541
Class group computation ends with a matrix of relations among candidate generators. Turning that matrix into a group structure with explicit generators is a pure linear algebra step, and it is the same step in every setting where relations are collected.
The setup
Suppose a finite abelian group is generated by k known elements, and a set of relations among them has been collected. Each relation is a vector of exponents whose corresponding product is trivial.
The procedure
Group structure from relations
- Assemble the matrixRows are relations, columns are generators.
- ReduceCompute the Smith normal form, tracking the column transformation.
- Read invariant factorsNon-unit diagonal entries give the cyclic factors.
- Recover generatorsApply the column transformation to the original generators to obtain generators of each cyclic factor.
Completeness
The critical question is whether enough relations have been collected. Too few relations give a quotient that is too large — a multiple of the true group order.
| Situation | Consequence |
|---|---|
| Too few relations | Computed order is a multiple of the truth |
| Enough relations | Correct structure |
| Generators do not generate | Computed group is a quotient of the truth; undetectable from the matrix alone |
Free part and units
Zero columns in the Smith normal form indicate a free part. In class group computation the group is finite so no free part should appear; if one does, more relations are needed. In the combined class group and unit computation the free part is exactly what yields the units — see regulator recovery.
Sparse relation matrices
Source. Henri Cohen, A Course in Computational Algebraic Number Theory, Springer GTM 138 — 2.4.4. Structural reference unverified: the source file was not available during authoring; chapter and section numbers are taken from the published edition and have not been checked against a physical copy.