Contents

# Contents

## Definition

###### Definition

(Hermite normal form)

$H \in Mat_{n \times m}(\mathbb{Z})$

with integer entries ($n$ rows, $m$ columns) is said to be in Hermite normal form if the following conditions hold:

1. All entries are non-negative numbers $\in \mathbb{N} \subset \mathbb{Z}$:

$H_{i j} \geq 0 \,.$
2. The first non-vanishing entry $p_{i} \coloneqq H_{i,j_{i}}$ in each row is strictly to the right of the first non-vanishing entry $p_{i-1} = H_{i,j_{i-1}}$ of the previous row (if any):

$j_{ i} \gt j_{i - 1}$

These entries are called the pivots of $H$.

3. Each pivot $p_i$ is strictly larger than all entries above it in the same row:

For $1 \leq i' \lt i$ we have $H_{i', j_i} \lt p_i = H_{i, j_i}$.

###### Remark

There are slightly different conventions in use for Def. , e.g. some authors require the non-vanishing non-pivotal entries to be negative instead of positive. These conventions are equivalent, in that the uniqueness of Hermite normal form, Theorem below applies with respect to each of them.

## Properties

### Uniqueness

###### Theorem

(uniqueness of Hermite normal form)

For

$M \in Mat_{n \times m}(\mathbb{Z})$

a matrix with integer entries, there exists a unique invertible matrix with integer coefficients

$U \;\in\; GL(n, \mathbb{Z}) \subset Mat_{n \times n}(\mathbb{Z})$

such that the matrix product

$H \;\coloneqq\; U \cdot M$

has Hermite normal form (Def. ).

Existence follows by integer row reduction of integer matrices, see e.g. Gilbert-Pathria 90, p. 3/4. Uniqueness requires more work (see e.g. Mader 00, theorem 1.5.2).

## References

Integer row reduction for integer matrices via greatest common divisors is explained for instance in

• William Gilbert, Anu Pathria, Linear Diophantine Equations, Dept. Pure Math. Univ. Waterloo, Ontario, Canada, 1990 (pdf, pdf)

Discussion of the general theory of integer matrices includes

• A. Mader, section 1.5 of Almost completely decomposable groups, CRC Press 2000

Computational implementation is discussed in

• George Labahn, Vincent Neiger, Wei Zhou, Fast, deterministic computation of the Hermite normal form and determinant of a polynomial matrix (arXiv:1607.04176)