Gaussian elimination tells us what a matrix does over a field. Smith and Hermite normal forms tell us what an integer matrix does when division is not freely available.
Over the rationals, multiplying a row by 1/2 is harmless. Over the integers, it can change the set of integer combinations completely. Computational number theory therefore uses a smaller set of legal transformations: swaps, sign changes and addition of integer multiples. These are encoded by unimodular matrices with determinant ±1.
Hermite normal form gives a canonical-style triangular description of an integer lattice or module under a chosen row/column convention. Smith normal form goes further by allowing unimodular transformations on both sides and reveals the invariant factors of an integer linear map.
This is Guide 18 in the Bukit Timah Tutor Computational Number Theory series. It connects the lattice representation of Guide 15 with the ideal and class-group algorithms of Guides 16 and 20. Return to the BTT Mathematics Hub for the wider Mathematics estate.
1. Integer linear algebra has stricter legal moves
Suppose the columns of an integer matrix B generate a lattice. Replacing one column by itself plus k times another column, swapping columns, or changing the sign of a column preserves the generated lattice.
These operations are reversible using integer operations. Their matrices are unimodular: integer matrices U with det(U)=±1, equivalently matrices whose inverse also has integer entries.
Multiplying a column by 2 is not unimodular. It generally changes the lattice index and discards lattice points.
2. Row modules and column lattices
A matrix can be interpreted in several ways: its rows generate a submodule of Z^n; its columns generate a submodule of Z^m; or it defines a homomorphism Z^n→Z^m.
Hermite normal form depends on which side is being normalised. Some references use row HNF, others column HNF. The matrices can look transposed even though the underlying theorem is the same.
A computational result should therefore state its convention rather than compare raw HNF matrices from two libraries without checking whether they normalise rows or columns.
3. Euclid is already an integer matrix algorithm
For two integers a,b, Euclid replaces (a,b) by (b,a−qb). This is multiplication by an integer matrix of determinant −1.
The gcd algorithm can therefore be viewed as normalising a one-row or one-column integer matrix. Hermite and Smith algorithms repeatedly embed this same Euclidean step inside larger matrices.
The fundamental engine is not arbitrary division. It is quotient-and-remainder reduction combined with unimodular transformations.
4. Hermite normal form: the purpose
Hermite normal form (HNF) gives a triangular or echelon-like representative of an integer row or column module. In a row-HNF convention, pivot positions progress to the right, pivots are positive, entries below pivots are zero and entries above pivots are reduced to a prescribed range.
The exact inequalities differ slightly among conventions, but the key properties are stable: HNF is reached by unimodular operations on one side and encodes the same integer module.
Because only one side is changed, HNF preserves the ambient coordinate interpretation. This is why it is useful for ideal lattices, submodule membership and exact basis normalisation.
5. A row-HNF worked example
Take the row module generated by
A = [[2,4,4],
[6,8,10]].
Subtract three times the first row from the second:
R2 ← R2−3R1 = [0,−4,−2].
Change its sign:
R2 = [0,4,2].
Now subtract R2 from R1:
R1 = [2,0,2].
One row-Hermite representative under this convention is therefore
H = [[2,0,2],
[0,4,2]].
Every operation was unimodular, so H and A generate the same row module in Z³.
6. Membership using HNF
Once a submodule has triangular structure, membership can be tested by integer back-substitution and divisibility.
For the row module generated by H above, a vector v=(v1,v2,v3) has to be expressible as
u(2,0,2)+w(0,4,2).
The first coordinate requires v1 even. The second requires v2 divisible by four. The third must then equal v1+(v2/2) after the corresponding coefficients are fixed.
The HNF has exposed constraints that were harder to see in the original basis.
7. Lattice index and determinant
For a full-rank square integer basis matrix B, the lattice index in Z^n is |det B|. Unimodular changes preserve this absolute determinant.
For a triangular HNF, the index is the product of the positive diagonal pivots. This makes HNF a convenient way to compute indices and ideal norms.
In algebraic number theory, an ideal represented in an integral basis is precisely such a full-rank integer sublattice. Its norm is the index of that lattice.
8. Smith normal form: diagonal structure
For an integer m×n matrix A, Smith normal form seeks unimodular P and Q such that
PAQ = diag(d1,d2,…,dr,0,…)
with each d_i positive and
d1 | d2 | … | dr.
The nonzero d_i are the invariant factors. Unlike HNF, Smith normal form uses transformations on both rows and columns. It therefore classifies the abstract integer linear map or module rather than preserving one fixed coordinate basis.
Over a principal ideal domain, the diagonal invariant-factor form is unique.
9. A complete 2×2 Smith example
Let
A = [[2,4],
[6,8]].
The gcd of all entries is 2, so the first Smith invariant d1 must be 2. The determinant is
2·8−4·6 = −8.
For a full-rank 2×2 matrix, d1d2=|det A|=8. Therefore d2=4. The Smith normal form is
D = [[2,0],
[0,4]].
The divisibility condition 2|4 holds. This argument identifies the invariant factors without displaying every elementary transformation.
10. Determinantal divisors
Define Δ_k as the gcd of all k×k minors of A, with Δ_0=1. For rank r, the Smith invariants satisfy
d_k = Δ_k/Δ_(k−1).
In the 2×2 example, Δ1=gcd(2,4,6,8)=2 and Δ2=|det A|=8. Hence d1=2 and d2=4.
Determinantal divisors give strong verification data. A proposed Smith diagonal can be checked by comparing products d1…d_k with the gcds of minors.
11. Cokernels and finite abelian groups
The matrix A defines a homomorphism Z^n→Z^m. Its cokernel is Z^m/im(A). Smith form decomposes this quotient:
coker(A) ≅ Z/d1Z ⊕ … ⊕ Z/drZ ⊕ Z^(m−r).
For the full-rank matrix [[2,4],[6,8]], the quotient is
Z/2Z ⊕ Z/4Z.
Its finite order is 8, matching |det A|.
This is the structure theorem for finitely generated abelian groups appearing computationally as matrix diagonalisation.
12. Solving integer linear systems
To solve Ax=b over the integers, Smith form transforms the equation:
PAQ y = Pb, where x=Qy.
With D=PAQ diagonal, each nonzero equation becomes
d_i y_i = c_i.
An integer solution exists exactly when d_i divides c_i for every pivot equation, together with zero-row consistency. Free variables describe the full solution set.
This converts a coupled Diophantine system into independent divisibility tests.
13. Example of solvability from the Smith diagonal
Suppose a transformed system has Smith diagonal diag(2,4) and transformed right side c=(6,12). Then y1=3 and y2=3 give an integer solution.
If c=(6,10), the second equation 4y2=10 has no integer solution. The obstruction is exact divisibility, not a numerical approximation issue.
To recover x, one needs the unimodular column transformation Q. A routine that returns only the invariant factors can classify solvability after transforming b only if it also supplies or can apply the transformation matrices.
14. Modular linear equations
Systems such as Ax=0 modulo n can also be analysed with Smith form. After diagonalisation, each coordinate equation becomes d_i y_i=0 modulo n.
The number of solutions to d y=0 mod n is gcd(d,n). Thus invariant factors give kernel sizes and module structure over finite quotient rings.
This connects integer normal forms to congruence solving without pretending that Z/nZ is always a field.
15. Integer relations among generators
If columns of A represent generators of an abelian group, the integer kernel of A records relations. HNF or Smith computations can produce a basis for these relations.
Conversely, if rows of a relation matrix present a group, Smith form tells us the group’s invariant-factor decomposition.
This is precisely the pattern used in computational class-group algorithms: collect multiplicative ideal relations as integer exponent vectors, then apply exact integer linear algebra.
16. Smith versus Hermite: different jobs
HNF is usually the better tool when one wants a canonical basis for a sublattice while preserving the ambient coordinate system. Smith form is better when one wants the invariant structure of a quotient or homomorphism.
HNF changes one side. Smith changes both. HNF looks triangular. Smith looks diagonal. HNF is heavily used for ideal-basis normalisation; Smith is heavily used for classifying finitely generated abelian groups.
Using one where the other is required can preserve the wrong object.
17. Normal forms and LLL are not interchangeable
LLL tries to make a basis geometrically short and nearly orthogonal. HNF and Smith forms aim at exact algebraic normalisation.
An HNF basis may contain long vectors. An LLL-reduced basis is not canonical and does not directly reveal invariant factors. A computational number-theory pipeline often uses both: exact normal form for module structure, LLL for coefficient control and geometry.
18. Coefficient growth
Naïve repeated Euclidean row and column operations can create large intermediate entries. Efficient normal-form algorithms use modular methods, fraction-free techniques, pivot strategies and reconstruction to control growth.
The output entries may be small even when a careless transformation path passes through enormous integers. Complexity analysis must therefore consider intermediate bit length, not only the dimensions of the matrix.
Fast integer multiplication from Guide 14 becomes relevant here because exact matrix operations repeatedly multiply and divide large integers.
19. Verification certificates
For HNF, return a unimodular U with H=UA for a row convention or H=AU for a column convention. Check det(U)=±1 when square, exact matrix multiplication and the HNF inequalities.
For Smith form, return P,Q with D=PAQ. Verify that P and Q are unimodular, D is diagonal, every invariant factor divides the next, and determinantal divisors agree.
These certificates separate discovery from verification. A complicated algorithm can be checked by simpler exact matrix multiplication and gcd computations.
20. Common mistakes
1. Using rational row scaling and claiming the same integer module. 2. Comparing row-HNF and column-HNF matrices without translating conventions. 3. Treating determinant equality as proof of lattice equality. 4. Forgetting the invariant-factor divisibility chain in Smith form.
5. Returning only a diagonal when a transformed solution vector is needed. 6. Calling LLL output a Smith or Hermite normal form. 7. Ignoring rank-deficient free components in a cokernel. 8. Performing fixed-width operations that overflow before exact reduction.
21. Practice set
1. List the elementary unimodular row operations. 2. Why does multiplying a row by 2 fail to preserve the row module? 3. Reduce the displayed 2×3 matrix to the row-HNF shown. 4. State one use of HNF.
5. Find Δ1 and Δ2 for [[2,4],[6,8]]. 6. Derive its Smith invariant factors. 7. What is its cokernel? 8. What is the order of that finite quotient?
9. If D=diag(2,4) and c=(6,12), solve Dy=c. 10. Explain why c=(6,10) is impossible. 11. What do zero diagonal entries mean in Smith form? 12. What does HNF preserve that two-sided Smith transformations do not?
13. Why are determinantal divisors useful certificates? 14. How do relation matrices lead to finite abelian group decompositions? 15. Why might LLL be used after HNF? 16. Which objects should accompany a fully verifiable Smith computation?
22. Answers
1. Swap rows, change a row sign and add an integer multiple of one row to another. 2. The inverse operation would require division by 2 and may not be integral. 3. R2←R2−3R1, change its sign, then R1←R1−R2. 4. Lattice/module normalisation, membership or ideal-basis representation.
5. Δ1=2 and Δ2=8. 6. d1=2,d2=4. 7. Z/2Z⊕Z/4Z. 8. Eight.
9. y=(3,3). 10. Four does not divide ten. 11. Free Z-components in the corresponding cokernel or nontrivial kernel directions, depending on orientation. 12. HNF changes only the generator basis on one side and keeps ambient coordinates fixed.
13. They are invariant under unimodular equivalence and determine products of Smith factors. 14. The relations present a quotient Z^m/R; Smith form diagonalises the relations into invariant factors. 15. HNF gives exact module structure while LLL can shorten the basis for geometric or numerical work. 16. The diagonal D and unimodular transformations P,Q, plus convention and exact input matrix.
Sources and further study
Chris Godsil’s University of Waterloo linear algebra notes include Hermite and Smith normal forms, with Euclidean-domain matrix operations and the invariant-factor theorem. For computational algebraic number theory, Henri Cohen’s A Course in Computational Algebraic Number Theory develops HNF, Smith form and integer modules throughout ideal and class-group computations.
Continue through Batch 05
Return to Guide 17: Binary Quadratic Forms. Continue to Guide 19: Dirichlet Unit Theorem, Regulators and Logarithmic Unit Lattices and Guide 20: Class Group Algorithms, Minkowski Bounds, Relation Matrices and Principal Ideal Tests.