Hermite normal form


In linear algebra, the Hermite normal form is an analogue of reduced echelon form for matrices over the integers. Just as reduced echelon form can be used to solve problems about the solution to the linear system where, the Hermite normal form can solve problems about the solution to the linear system where this time is restricted to have integer coordinates only. Other applications of the Hermite normal form include integer programming, cryptography, and abstract algebra.

Definition

Various authors may prefer to talk about Hermite normal form in either row-style or column-style. They are essentially the same up to transposition.

Row-style Hermite normal form

A matrix has a Hermite normal form if there is a square unimodular matrix such that and:
  1. is upper triangular, and any rows of zeros are located below any other row.
  2. The leading coefficient of a nonzero row is always strictly to the right of the leading coefficient of the row above it; moreover, it is positive.
  3. The elements below pivots are zero and elements above pivots are nonnegative and strictly smaller than the pivot.
The third condition is not standard among authors, for example some sources force non-pivots to be nonpositive or place no sign restriction on them. However, these definitions are equivalent by using a different unimodular matrix. A unimodular matrix is a square integer matrix whose determinant is 1 or −1. In fact, a unimodular matrix is invertible over the integers, as can be seen, for example, from Cramer's Rule.

Column-style Hermite normal form

A matrix has a Hermite normal form if there is a square unimodular matrix where and has the following restrictions:
  1. is lower triangular and any columns of zeros are located on the right.
  2. The leading coefficient of a nonzero column is always strictly below of the leading coefficient of the column before it; moreover, it is positive.
  3. The elements to the right of pivots are zero and elements to the left of pivots are nonnegative and strictly smaller than the pivot.
Note that the row-style definition has a unimodular matrix multiplying on the left, while the column-style definition has the unimodular matrix action on the columns of. The two definitions of Hermite normal forms are simply transposes of each other.

Existence and uniqueness of the Hermite normal form

Every full row rank m-by-n matrix A with integer entries has a unique m-by-n matrix H in Hermite normal form, such that H='UA for some square unimodular matrix U'.

Examples

In the examples below, is the Hermite normal form of the matrix, and is a unimodular matrix such that.
If has only one row then either or, depending on whether the single row of has a positive or negative leading coefficient.

Algorithms

There are many algorithms for computing the Hermite normal form, dating back to 1851. One such algorithm is described in. But only in 1979 an algorithm for computing the Hermite normal form that ran in strongly polynomial time was first developed; that is, the number of steps to compute the Hermite normal form is bounded above by a polynomial in the dimensions of the input matrix, and the space used by the algorithm is bounded by a polynomial in the binary encoding size of the numbers in the input matrix.
One class of algorithms is based on Gaussian elimination in that special elementary matrices are repeatedly used. The lattice basis reduction algorithm|LLL] algorithm can also be used to efficiently compute the Hermite normal form.

Applications

Lattice calculations

A typical lattice in Rn has the form where the ai are in Rn. If the columns of a matrix A are the ai, the lattice can be associated with the columns of a matrix, and A is said to be a basis of L. Because the Hermite normal form is unique, it can be used to answer many questions about two lattice descriptions. For what follows, denotes the lattice generated by the columns of A. Because the basis is in the columns of the matrix A, the column-style Hermite normal form must be used. Given two bases for a lattice, A and A', the equivalence problem is to decide if This can be done by checking if the column-style Hermite normal form of A and A' are the same up to the addition of zero columns. This strategy is also useful for deciding if a lattice is a subset, deciding if a vector v is in a lattice, and for other calculations.

Integer solutions to linear systems

The linear system has an integer solution if and only if the system has an integer solution where and is the column-style Hermite normal form of. Checking that has an integer solution is easier than because the matrix is triangular.

Implementations

Many mathematical software packages can compute the Hermite normal form:
*

Over an arbitrary Dedekind domain

Hermite normal form can be defined when we replace Z by an arbitrary Dedekind domain.. For instance, in control theory it can be useful to consider Hermite normal form for the polynomials over a given field.