Integer Matrix Normal Forms
Z-Modules and Integer Matrix Problems
Finitely generated abelian groups as integer matrix problems, and the two normal forms that answer the two basic questions about them.
Engineering / MathematicsInteger Matrix Normal Forms2 min readKV-MATH-0536
A finitely generated abelian group is presented by an integer matrix. Two normal forms answer the two questions one asks about such a presentation, and nearly all number field computation reduces to one or the other.
The setting
A subgroup of a free abelian group of rank n is generated by the columns of an integer matrix. Two matrices generate the same subgroup exactly when they differ by an invertible integer matrix acting on the columns.
- Unimodular matrix
- An integer matrix with determinant plus or minus one. Its inverse is again an integer matrix, so it represents a change of basis.
- Column operations
- Adding an integer multiple of one column to another, swapping columns, negating a column. These generate all unimodular column transformations.
- Row operations
- The same on rows, corresponding to a change of basis in the ambient group.
The two normal forms
| Form | Operations allowed | Answers |
|---|---|---|
| Hermite normal form | Column operations only | What is a canonical basis of this subgroup? |
| Smith normal form | Both row and column operations | What is the structure of the quotient group? |
Why both are needed
In class group computation, the relation matrix is first reduced by Hermite normal form to obtain a clean basis for the relation lattice, then by Smith normal form to read off the invariant factors of the class group. Both steps are necessary — see recovering group structure.
The practical obstacle
Where these arise in number fields
- Ideals of a number field, represented by their basis matrix relative to an integral basis.
- Orders, represented as modules containing the equation order.
- Relation lattices in class group computation.
- Unit lattices under the logarithmic embedding.
Source. Henri Cohen, A Course in Computational Algebraic Number Theory, Springer GTM 138 — 2.4.1. 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.