Hermite normal form

In

${\displaystyle \mathbb {Z} }$. Just as

reduced echelon form

can be used to solve problems about the solution to the linear system ${\displaystyle Ax=b}$ where ${\displaystyle x\in \mathbb {R} ^{n}}$, the Hermite normal form can solve problems about the solution to the linear system ${\displaystyle Ax=b}$ where this time ${\displaystyle x}$ is restricted to have integer coordinates only. Other applications of the Hermite normal form include

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.

A matrix ${\displaystyle A\in \mathbb {Z} ^{m\times n}}$ has a (row) Hermite normal form ${\displaystyle H}$ if there is a square unimodular matrix ${\displaystyle U}$ where ${\displaystyle H=UA}$.

${\displaystyle H}$ has the following restrictions:^[4][5][6]

1. ${\displaystyle H}$ is upper triangular (that is, ${\displaystyle h_{ij}=0}$ for ${\displaystyle i>j}$), and any rows of zeros are located below any other row.
2. 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.
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[7]^[8] or place no sign restriction on them.^[9] However, these definitions are equivalent by using a different unimodular matrix ${\displaystyle U}$. A unimodular matrix is a square integer matrix whose

A matrix ${\displaystyle A\in \mathbb {Z} ^{m\times n}}$ has a (column) Hermite normal form ${\displaystyle H}$ if there is a square unimodular matrix ${\displaystyle U}$ where ${\displaystyle H=AU}$ and ${\displaystyle H}$ has the following restrictions:^[8][10]

1. ${\displaystyle H}$ is lower triangular (${\displaystyle h_{ij}=0}$ for ${\displaystyle i<j}$) and any columns of zeros are located on the right.
2. The
   leading coefficient (the first nonzero entry from the top, also called the pivot
   ) of a nonzero column is always strictly below of the leading coefficient of the column before it; moreover, it is positive.d
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.

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.[5]^[11][12]

In the examples below, H is the Hermite normal form of the matrix A, and U is a unimodular matrix such that UA = H. $${\displaystyle A={\begin{pmatrix}3&3&1&4\\0&1&0&0\\0&0&19&16\\0&0&0&3\end{pmatrix}}\qquad H={\begin{pmatrix}3&0&1&1\\0&1&0&0\\0&0&19&1\\0&0&0&3\end{pmatrix}}\qquad U=\left({\begin{array}{rrrr}1&-3&0&-1\\0&1&0&0\\0&0&1&-5\\0&0&0&1\end{array}}\right)}$$

$${\displaystyle A={\begin{pmatrix}2&3&6&2\\5&6&1&6\\8&3&1&1\end{pmatrix}}\qquad H=\left({\begin{array}{rrrr}1&0&50&-11\\0&3&28&-2\\0&0&61&-13\end{array}}\right)\qquad U=\left({\begin{array}{rrr}9&-5&1\\5&-2&0\\11&-6&1\end{array}}\right)}$$

If A has only one row then either H = A or H = −A, depending on whether the single row of A has a positive or negative leading coefficient.

There are many algorithms for computing the Hermite normal form, dating back to 1851. One such algorithm is described in.

One class of algorithms is based on Gaussian elimination in that special elementary matrices are repeatedly used.^[11][15][16] The LLL algorithm can also be used to efficiently compute the Hermite normal form.^[17][18]

A typical lattice in Rⁿ has the form ${\textstyle L=\left\{\left.\sum _{i=1}^{n}\alpha _{i}\mathbf {a} _{i}\;\right\vert \;\alpha _{i}\in {\textbf {Z}}\right\}}$ where the a_i are in Rⁿ. If the columns of a matrix A are the a_i, 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, ${\displaystyle L_{A}}$ 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 ${\displaystyle L_{A}=L_{A'}.}$ 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 (${\displaystyle L_{A}\subseteq L_{A'}}$ if and only if ${\displaystyle L_{[A\mid A']}=L_{A'}}$), deciding if a vector v is in a lattice (${\displaystyle v\in L_{A}}$ if and only if ${\displaystyle L_{[v\mid A]}=L_{A}}$), and for other calculations.^[19]

The linear system Ax = b has an integer solution x if and only if the system Hy = b has an integer solution y where y = U⁻¹x and H is the column-style Hermite normal form of A. Checking that Hy = b has an integer solution is easier than Ax = b because the matrix H is triangular.^[11]: 55

Many mathematical software packages can compute the Hermite normal form:

• Maple with HermiteForm
• MATLAB with hermiteForm
• NTL with HNF
• PARI/GP with mathnf
• SageMath with hermite_form
• "HermiteDecomposition".
  Wolfram Alpha Site.^[20]

Hermite normal form can be defined when we replace Z by an arbitrary Dedekind domain.^[21] (for instance, any principal-ideal domain). For instance, in control theory it can be useful to consider Hermite normal form for the polynomials F[x] over a given field F.

• Hermite ring
• Smith normal form
• Howell normal form
• Diophantine equation