Calculation Results
Hermite Normal Form (HNF) — Definition, Examples & Practice
This article explains the Hermite Normal Form (HNF) for integer matrices, gives the definition, practical computation ideas, worked examples, a summary of common mistakes, and practice problems with collapsible answers. It is designed as companion content for a Matrix Hermite Normal Form Calculator.
What is Hermite Normal Form?
The Hermite Normal Form (HNF) is a canonical form for integer matrices under unimodular transformations (integer invertible operations). There are two standard conventions:
- Row-style HNF (common): for an integer m×n matrix \(A\), there exists a unimodular integer matrix \(U\) (i.e. \(\det U=\pm1\)) such that \[ U A = H, \] where \(H\) is in row Hermite normal form (rows in echelon-like form, special positivity and remainder conditions). The matrix \(H\) is unique for \(A\) under this convention.
- Column-style HNF: there exists unimodular \(V\) with \[ A V = H', \] where \(H'\) is in column Hermite normal form. This is the column-version and is also commonly used (the forms are closely related by transposition).
Below we use the row-style HNF convention for examples and exercises. Intuitively, computing HNF is like performing integer-preserving row operations (swap rows, add integer multiples of one row to another, multiply a row by -1) to reduce the matrix to a canonical echelon-like integer matrix.
Formal properties (row-style HNF)
- \(H\) is an integer matrix in row-echelon form: there are pivots moving strictly to the right as you go down rows.
- Each pivot (first nonzero entry in a non-zero row) is positive.
- Entries in the pivot column above the pivot are zero (because rows above have earlier pivots).
- Entries to the right of a pivot in the same row are reduced modulo the pivot into a standard range (convention-dependent). Combined with unimodular operations these conditions make \(H\) unique.
- There exists a unimodular \(U\) (integer inverse) such that \(U A = H\).
Note: In practice implementations (e.g. in CAS or numeric libraries) use Euclidean/Gaussian-like integer algorithms to find \(U\) and \(H\). Your calculator may present row- or column-style HNF — be consistent with the chosen convention.
How to compute (practical idea)
- Use integer row operations only: swap rows, replace a row by itself plus an integer multiple of another row, or multiply a row by -1. These operations are unimodular (they correspond to left-multiplying by unimodular matrices).
- Perform a column-reduction-like Euclidean algorithm to produce the smallest positive pivot in the first column (gcd-based), use it to clear other entries in that column, then move to the submatrix formed by remaining rows/columns.
- Reduce entries to the right of each pivot into a canonical remainder range (this ensures uniqueness).
- Stop when matrix is in echelon form with the Hermite conditions satisfied.
Worked Example 1 (2×2)
Given:
$$ A = \begin{pmatrix} 2 & 4 \\ 6 & 8 \end{pmatrix} $$Goal: find unimodular \(U\) and HNF \(H\) with \(U A = H\).
Key integer row steps (illustrative):
- Start with rows \(r_1=(2,4)\), \(r_2=(6,8)\).
- Replace \(r_2 \leftarrow r_2 - 3 r_1\) to clear first column below pivot: \(r_2 = (6,8) - 3(2,4) = (0,-4)\).
- Make pivot entries positive: multiply second row by -1: \(r_2 \leftarrow -r_2 = (0,4)\).
- Reduce the entry to the right of the pivot in row 1 by subtracting an integer multiple of row 2: \(r_1 \leftarrow r_1 - 1\cdot r_2 = (2,0)\).
Now the matrix is in row Hermite normal form:
$$ H = \begin{pmatrix} 2 & 0 \\ 0 & 4 \end{pmatrix} $$Thus there exists unimodular integer \(U\) (product of the performed row-operations) such that \(U A = H\).
Worked Example 2 (2×2)
Given:
$$ A = \begin{pmatrix} 1 & 2 \\ 3 & 4 \end{pmatrix} $$Key integer row steps:
- Swap rows to bring a small pivot (if needed). Here pivot 1 is already small.
- Eliminate below pivot: \(r_2 \leftarrow r_2 - 3 r_1 = (0,-2)\).
- Make the second pivot positive: multiply second row by -1: \(r_2 \leftarrow -r_2 = (0,2)\).
- Reduce the entry in row 1, column 2 modulo the pivot in row 2 (here subtract \(1\cdot r_2\) from \(r_1\)): \(r_1 \leftarrow r_1 - 1\cdot r_2 = (1,0)\).
Resulting row-style HNF:
$$ H = \begin{pmatrix} 1 & 0 \\ 0 & 2 \end{pmatrix} $$Common Mistakes (and tips)
| Common mistake | Tip / correct approach |
|---|---|
| Using arbitrary rational row operations (fractions) | Only allow integer unimodular row operations (swap rows, add integer multiple of a row, multiply a row by -1). |
| Confusing HNF with Smith Normal Form (SNF) | HNF is upper (or lower) triangular canonical under unimodular left (or right) transformations; SNF is diagonal under both left and right unimodular transforms. |
| Forgetting uniqueness convention (row vs column) | Decide whether your calculator uses row-style (U A = H) or column-style (A V = H) and be consistent. |
| Stopping before reducing remainders into canonical range | After clearing columns, reduce the entries to the right of each pivot modulo the pivot to enforce the canonical constraints that guarantee uniqueness. |
Practice Problems (compute row-style HNF)
Each exercise asks you to compute the row Hermite Normal Form \(H\) of the given integer matrix \(A\) (i.e. find integer unimodular operations so that \(U A = H\)). Click "Show Answer" to reveal a worked result.
Exercise 1
$$ A = \begin{pmatrix} 2 & 4 \\[4pt] 6 & 8 \end{pmatrix} $$Show Answer
Exercise 2
$$ A = \begin{pmatrix} 1 & 2 \\[4pt] 3 & 4 \end{pmatrix} $$Show Answer
Exercise 3
$$ A = \begin{pmatrix} 2 & 4 & 6 \\ 0 & 2 & 8 \\ 0 & 0 & 4 \end{pmatrix} $$Show Answer
Exercise 4
$$ A = \begin{pmatrix} 3 & 6 & 9 \\ 6 & 15 & 12 \\ 0 & 3 & 6 \end{pmatrix} $$Show Answer
Hermite normal form can be studied together with matrix multiplication, matrix inverse, and LU decomposition.
Learn matrix multiplication more easily in just 2 minutes with this free game.
