Hermite normal form

Remarks

The proof is integer Gaussian elimination. The Euclidean algorithm on a column, by unimodular row operations, leaves the gcd of the entries in the pivot position and zeros below it. Then the entries above each pivot are reduced modulo the pivot. Uniqueness holds because the rows of $H$ are a special basis of the lattice spanned by the rows of $A$, and this basis is determined by the lattice.

Example: for $A = \begin{pmatrix} 2 & 4 \\ 6 & 8 \end{pmatrix}$, subtract $3$ times row $1$ from row $2$ to get $\begin{pmatrix} 2 & 4 \\ 0 & -4 \end{pmatrix}$. Negate row $2$ and subtract it from row $1$ to get $H = \begin{pmatrix} 2 & 0 \\ 0 & 4 \end{pmatrix}$, which satisfies all four conditions.

Without condition 4 the form is not unique: $\begin{pmatrix} 2 & 4 \\ 0 & 4 \end{pmatrix}$ is also a row echelon form of $A$ reachable by unimodular operations. Some authors use the column version, $AU = H$ with $U$ unimodular of size $n \times n$ and $H$ lower triangular.

Going deeper

For a student

Two integer matrices have the same Hermite normal form exactly when their rows span the same lattice in $\Z^n$. So the form solves the membership problem for lattices and gives a canonical basis. It is used to solve linear Diophantine systems, to compute with ideals in number fields, and in integer programming. Unlike the Smith normal form, it uses only row operations, and it keeps the row space.