Hermite normal form

From Wikipedia, the free encyclopedia
Jump to: navigation, search

In linear algebra, the Hermite normal form is an analogue of reduced echelon form for matrices over the integers Z.

Definition[edit]

A matrix with integer entries is in Hermite normal form (HNF) if

  • All nonzero rows (rows with at least one nonzero element) are above any rows of all zeroes (all zero rows, if any, are at the bottom of the matrix).
  • 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.
  • All entries in a column above a leading entry are nonnegative and strictly smaller than the leading entry.
  • All entries in a column below a leading entry are zeroes (implied by the first two criteria).

Nonsingular square matrices[edit]

In particular, a nonsingular square matrix with integer entries is in Hermite normal form (HNF) if

  • it is upper triangular,
  • its diagonal entries are positive,
  • in every column, the entries above the diagonal are non-negative and smaller than the entry on the diagonal.

Existence and uniqueness of the Hermite normal form[edit]

For every m×n matrix A with integer entries there is a unique m×n matrix H, in (HNF), with integer entries such that

H=UA with U ∈ GLn(Z)

(i.e. U is unimodular).

Equivalently, H is the unique matrix in (HNF) with integer entries that can be obtained from A by means of a finite sequence of elementary row operations over Z (the only admissible row multiplications are by ±1).

Examples[edit]

The Hermite normal form of matrix A (on the left) is matrix H (on the right):


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}


A=
\begin{pmatrix}
0&0&5 & 0 & 1 & 4 \\
0&0&0 & -1 & -4 & 99 \\
0&0&0 & 20 & 19 & 16 \\
0&0&0 & 0 & 2 & 1\\
0&0&0 & 0 & 0 & 3\\
0&0&0 & 0 & 0 & 0
\end{pmatrix}
\qquad H=
\begin{pmatrix}
0& 0& 5& 0& 0& 2\\
0& 0& 0& 1& 0& 1\\
0& 0& 0& 0& 1& 2\\
0& 0& 0& 0& 0& 3\\
0& 0& 0& 0& 0& 0\\
0& 0& 0& 0& 0& 0\\
\end{pmatrix}

If A has only one row then H = A.

Alternative definitions[edit]

There are various versions of Hermite normal form in the literature, not equivalent to the above one. For instance —to distinguish this definition from the above one, we call this form (HNF')— an m×n matrix M = (mij) with integer entries is in (HNF') if there exists

such that the first r columns of M are zero, and for r + 1 ≤ jn

  • mf(j)j > 0,
  • mij = 0 when i > f(j),
  • mf(i)i > mf(i)j ≥ 0 when i < f(j).

With this definition, for every m×n matrix B with integer entries there is a unique m×n matrix M, in (HNF'), with integer entries such that

M=BU with U ∈ GLn(Z).

Some authors prefer using lower triangular matrices; suitable adjustments must be made to the rest of the definition.

See also[edit]

References[edit]