Hermite normal form

It turns out that the Hermite normal form can be used to quickly solve problems such as solving the linear system $Ax = b$, where $x$ is restricted to have integer coordinates, or answering the question of whether two lattices are equivalent.

In what follows, I will describe the row-style Hermite normal form.

Definition: An $m \times n$ matrix $A$ with integer entries has a (row) Hermite normal form $H$ if there is a square unimodular matrix $U$ where $H = UA$ and $H$ has the following restrictions:

• It is upper triangular, and any rows of zeros are located below any other row.
• The leading coefficient (the first nonzero entry from the left, also called the pivot) of a nonzero row is always strictly to the right of the leading coefficient of the row above it; moreover, it is positive.
• The elements below pivots are zero and elements above pivots are nonnegative and strictly smaller than the pivot.

What’s important is that the Hermite normal form is unique. It is unique in the sense that if you modify the matrix using elementary row operations (in the row-style Hermite normal form), it will remain unchanged.

Let us consider the following example in Sage:

sage: A = matrix([[1, 2, 2, 0], [0, 4, 3, 1], [-3, -8, 0, -2], [0, -1, -2, 0]])
sage: H = A.echelon_form(); H
[ 1  0  3 -1]
[ 0  1  2  0]
[ 0  0  5 -1]
[ 0  0  0  0]

Or you can also call:

sage: A.hermite_form(transformation=True)
(
[ 1  0  3 -1]  [ 1 -1  0 -2]
[ 0  1  2  0]  [ 0  0  0 -1]
[ 0  0  5 -1]  [ 0 -1  0 -4]
[ 0  0  0  0], [ 3  2  1  6]
)

Now, let’s perform an elementary operation on the matrix: add the first two rows and replace the first row with the result.

sage: A2 = matrix([[1, 6, 5, 1], [0, 4, 3, 1], [-3, -8, 0, -2], [0, -1, -2, 0]])
sage: A2.echelon_form()
[ 1  0  3 -1]
[ 0  1  2  0]
[ 0  0  5 -1]
[ 0  0  0  0]

The Hermite normal form remains unchanged. This allows us to easily check whether two lattices (generated by the matrix rows) are equivalent—simply by verifying whether their Hermite normal forms are identical.

To check whether a vector belongs to a lattice, we add the vector (as a row) to the matrix and compute its Hermite normal form. If the Hermite normal form remains the same, except for an additional zero row, the vector is part of the lattice. For example, let’s double the last row of $A$ and add it to the matrix:

A1 = matrix([[1, 2, 2, 0], [0, 4, 3, 1], [-3, -8, 0, -2], [0, -1, -2, 0], [0, -2, -4, 0]])
sage: m2.echelon_form()
[ 1  0  3 -1]
[ 0  1  2  0]
[ 0  0  5 -1]
[ 0  0  0  0]
[ 0  0  0  0]

To compute the union of two lattices, we start with two matrices representing the two lattices. To find their union, we stack one matrix on top of the other to create a new matrix and then compute its Hermite normal form. The resulting Hermite normal form represents the union of the two lattices.