Hermite normal form

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

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.

An m by 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:

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. A unimodular matrix is a square invertible integer matrix whose determinant is 1 or -1.

A m by n matrix A with integer entries has a (column) Hermite normal form H if there is a square unimodular matrix U where H=AU and H has the following restrictions:

Note that the row-style definition has a unimodular matrix U multiplying A on the left (meaning U is acting on the rows of A), while the column-style definition has the unimodular matrix action on the columns of A. The two definitions of Hermite normal forms are simply transposes of each other.

This page was last edited on 8 April 2018, at 06:22.
Reference: https://en.wikipedia.org/wiki/Hermite_normal_form under CC BY-SA license.

Related Topics

Recently Viewed