In
linear algebra
Linear algebra is the branch of mathematics concerning linear equations such as:
:a_1x_1+\cdots +a_nx_n=b,
linear maps such as:
:(x_1, \ldots, x_n) \mapsto a_1x_1+\cdots +a_nx_n,
and their representations in vector spaces and through matrices.
...
, the Hermite normal form is an analogue of
reduced echelon form
In linear algebra, a matrix is in echelon form if it has the shape resulting from a Gaussian elimination.
A matrix being in row echelon form means that Gaussian elimination has operated on the rows, and
column echelon form means that Gaussian el ...
for
matrices
Matrix most commonly refers to:
* ''The Matrix'' (franchise), an American media franchise
** ''The Matrix'', a 1999 science-fiction action film
** "The Matrix", a fictional setting, a virtual reality environment, within ''The Matrix'' (franchis ...
over the
integer
An integer is the number zero (), a positive natural number (, , , etc.) or a negative integer with a minus sign (−1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the language ...
s Z. Just as
reduced echelon form
In linear algebra, a matrix is in echelon form if it has the shape resulting from a Gaussian elimination.
A matrix being in row echelon form means that Gaussian elimination has operated on the rows, and
column echelon form means that Gaussian el ...
can be used to solve problems about the solution to the linear system Ax=b where x is in R
''n'', 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
An integer programming problem is a mathematical optimization or Constraint satisfaction problem, feasibility program in which some or all of the variables are restricted to be integers. In many settings the term refers to integer linear programmin ...
,
cryptography
Cryptography, or cryptology (from grc, , translit=kryptós "hidden, secret"; and ''graphein'', "to write", or ''-logia'', "study", respectively), is the practice and study of techniques for secure communication in the presence of adver ...
, and
abstract algebra
In mathematics, more specifically algebra, abstract algebra or modern algebra is the study of algebraic structures. Algebraic structures include groups, rings, fields, modules, vector spaces, lattices, and algebras over a field. The term ''a ...
.
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
An m by n matrix A with integer entries has a (row) Hermite normal form H if there is a square
unimodular matrix
In mathematics, a unimodular matrix ''M'' is a square integer matrix having determinant +1 or −1. Equivalently, it is an integer matrix that is invertible over the integers: there is an integer matrix ''N'' that is its inverse (these are equiv ...
U where H=UA and H has the following restrictions:
# H is upper triangular (that is, h
''ij'' = 0 for ''i'' > ''j''), and any rows of zeros are located below any other row.
# The
leading coefficient
In mathematics, a coefficient is a multiplicative factor in some term of a polynomial, a series, or an expression; it is usually a number, but may be any expression (including variables such as , and ). When the coefficients are themselves var ...
(the first nonzero entry from the left, also called the
pivot
Pivot may refer to:
*Pivot, the point of rotation in a lever system
*More generally, the center point of any rotational system
*Pivot joint, a kind of joint between bones in the body
*Pivot turn, a dance move
Companies
*Incitec Pivot, an Austra ...
) 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. A unimodular matrix is a square
invertible
In mathematics, the concept of an inverse element generalises the concepts of opposite () and reciprocal () of numbers.
Given an operation denoted here , and an identity element denoted , if , one says that is a left inverse of , and that is ...
integer matrix whose
determinant
In mathematics, the determinant is a scalar value that is a function of the entries of a square matrix. It characterizes some properties of the matrix and the linear map represented by the matrix. In particular, the determinant is nonzero if and ...
is 1 or −1.
Column-style Hermite normal form
A ''m''-by-''n'' matrix A with integer entries has a (column) Hermite normal form H if there is a square
unimodular matrix
In mathematics, a unimodular matrix ''M'' is a square integer matrix having determinant +1 or −1. Equivalently, it is an integer matrix that is invertible over the integers: there is an integer matrix ''N'' that is its inverse (these are equiv ...
U where H=AU and H has the following restrictions:
# H is lower triangular, ''h''
''ij'' = 0 for ''i'' < ''j'', and any columns of zeros are located on the right.
# The
leading coefficient
In mathematics, a coefficient is a multiplicative factor in some term of a polynomial, a series, or an expression; it is usually a number, but may be any expression (including variables such as , and ). When the coefficients are themselves var ...
(the first nonzero entry from the top, also called the
pivot
Pivot may refer to:
*Pivot, the point of rotation in a lever system
*More generally, the center point of any rotational system
*Pivot joint, a kind of joint between bones in the body
*Pivot turn, a dance move
Companies
*Incitec Pivot, an Austra ...
) 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 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.
Existence and uniqueness of the Hermite normal form
Every ''m''-by-''n'' matrix A with integer entries has a unique ''m''-by-''n'' matrix H, 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. It was not until 1979 when an algorithm for computing the Hermite normal form that ran in
strongly polynomial time
In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by ...
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 (intermediate numbers) 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 mathematics, Gaussian elimination, also known as row reduction, is an algorithm for solving systems of linear equations. It consists of a sequence of operations performed on the corresponding matrix of coefficients. This method can also be used ...
in that special elementary matrices are repeatedly used.
The
LLL algorithm can also be used to efficiently compute the Hermite normal form.
Applications
Lattice calculations
A typical
lattice
Lattice may refer to:
Arts and design
* Latticework, an ornamental criss-crossed framework, an arrangement of crossing laths or other thin strips of material
* Lattice (music), an organized grid model of pitch ratios
* Lattice (pastry), an orna ...
in R
''n'' has the form
where the a
''i'' are in R
''n''. 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,
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 (
if and only if
), deciding if a vector v is in a lattice (
if and only if
), 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:
*
Maple
''Acer'' () is a genus of trees and shrubs commonly known as maples. The genus is placed in the family Sapindaceae.Stevens, P. F. (2001 onwards). Angiosperm Phylogeny Website. Version 9, June 2008 nd more or less continuously updated since http ...
wit
HermiteForm*
Mathematica
Wolfram Mathematica is a software system with built-in libraries for several areas of technical computing that allow machine learning, statistics, symbolic computation, data manipulation, network analysis, time series analysis, NLP, optimizat ...
wit
HermiteDecomposition*
MATLAB
MATLAB (an abbreviation of "MATrix LABoratory") is a proprietary multi-paradigm programming language and numeric computing environment developed by MathWorks. MATLAB allows matrix manipulations, plotting of functions and data, implementation ...
wit
hermiteForm*
NTL
NTL may refer to:
Companies
* NTL Incorporated and NTL Internet, later Virgin Media, communications media company
** NTL Ireland, later Virgin Media Ireland
* Arqiva, UK company formerly ''NTL Broadcast'' and ''National Transcommunications L ...
wit
HNF*
PARI/GP
PARI/GP is a computer algebra system with the main aim of facilitating number theory computations. Versions 2.1.0 and higher are distributed under the GNU General Public License. It runs on most common operating systems.
System overview
The ...
wit
mathnf*
SageMath
SageMath (previously Sage or SAGE, "System for Algebra and Geometry Experimentation") is a computer algebra system (CAS) with features covering many aspects of mathematics, including algebra, combinatorics, graph theory, numerical analysis, numbe ...
wit
hermite_form
Over an arbitrary Dedekind domain
Hermite normal form can be defined when we replace Z by an arbitrary
Dedekind domain
In abstract algebra, a Dedekind domain or Dedekind ring, named after Richard Dedekind, is an integral domain in which every nonzero proper ideal factors into a product of prime ideals. It can be shown that such a factorization is then necessarily ...
.
(for instance, any
principal-ideal domain). For instance, in
control theory
Control theory is a field of mathematics that deals with the control of dynamical systems in engineered processes and machines. The objective is to develop a model or algorithm governing the application of system inputs to drive the system to a ...
it can be useful to consider Hermite normal form for the polynomials F