In linear algebra, the Hermite normal form is an analogue of reduced echelon form for matrices over the integers Z {\displaystyle \mathbb {Z} } . Just as reduced echelon form can be used to solve problems about the solution to the linear system A x = b {\displaystyle Ax=b} where x ∈ R n {\displaystyle x\in \mathbb {R} ^{n}} , the Hermite normal form can solve problems about the solution to the linear system A x = b {\displaystyle Ax=b} where this time x {\displaystyle x} 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 A ∈ Z m × n {\displaystyle A\in \mathbb {Z} ^{m\times n}} has a (row) Hermite normal form H {\displaystyle H} if there is a square unimodular matrix U {\displaystyle U} such that H = U A {\displaystyle H=UA} and:
H {\displaystyle H} is upper triangular (that is, h i j = 0 {\displaystyle h_{ij}=0} for i > j {\displaystyle i>j} ), 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. 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 U {\displaystyle U} . A unimodular matrix is a square integer matrix whose determinant is 1 or −1 (and hence invertible). 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 A ∈ Z m × n {\displaystyle A\in \mathbb {Z} ^{m\times n}} has a (column) Hermite normal form H {\displaystyle H} if there is a square unimodular matrix U {\displaystyle U} where H = A U {\displaystyle H=AU} and H {\displaystyle H} has the following restrictions:
H {\displaystyle H} is lower triangular ( h i j = 0 {\displaystyle h_{ij}=0} for i < j {\displaystyle i<j} ) and any columns of zeros are located on the right. 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. 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 U {\displaystyle U} multiplying A {\displaystyle A} on the left (meaning U {\displaystyle U} is acting on the rows of A {\displaystyle A} ), while the column-style definition has the unimodular matrix action on the columns of A {\displaystyle A} . 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, H is the Hermite normal form of the matrix A, and U is a unimodular matrix such that UA = H.
… excerpt ends here. Continue reading the full article.
