TOPICS
Search

Hermite Normal Form


Given a square n×n nonsingular integer matrix A, there exists an n×n unimodular matrix U and an n×n matrix H (known as the Hermite normal form of A) such that

 AU=H.

Specifying a certain set of conditions on the elements of H makes it (and therefore U) unique. One possible set of conditions (corresponding to the "columns" version and making H lower triangular) is given by

1. h_(ij)=0 for j>i,

2. h_(ii)>0 for all i, and

3. h_(ij)<=0 and |h_(ij)|<h_(ii) for j<i

(Domich et al. 1987).

For a complexity analysis of Hermite normal form computation, see Storjohann and Labahn (1996).

The Hermite normal form for integer matrices is implemented in the Wolfram Language as HermiteDecomposition[A], which however uses the "rows" convention (thus making H upper triangular) and replaces condition (3) with balanced remainders (mod h_(ii)).


See also

Normal Form, Smith Normal Form

Explore with Wolfram|Alpha

References

Cohen, H. A Course in Computational Algebraic Number Theory. New York: Springer-Verlag, p. 67, 1993.Domich, P. D.; Kannan, R.; and Trotter, L. E. Jr. "Hermite Normal Form Computation Using Modulo Determinant Arithmetic." Math. Operations Res. 12, 50-59, 1987.Hafner, J. L.; and McCurley, K. S. "Asymptotically Fast Triangularization of Matrices Over Rings." SIAM J. Comput. 20, 1068-1083, 1991.Kaltofen, E. and Saunders, B. D. "Mr. Smith Goes to Las Vegas: Randomized Parallel Computation of the Smith Normal Form of Polynomial Matrices." In Proceedings of the Sixth European Conference on Computer Algebra held at Karl-Marx University, Leipzig, June 2-5, 1987: EUROCAL '87 (Ed. J. H. Davenport). Berlin: Springer-Verlag, pp. 317-322, 1989.Kannan, R. "Solving Systems of Linear Equations Over Polynomials." Theoret. Comput. Sci. 39, 69-88, 1985.Storjohann, A. and Labahn, G. "Asymptotically Fast Computation of Hermite Normal Forms of Integer Matrices." In Proc. Internat. Symp. on Symbolic and Algebraic Computation: ISSAC '96 (Ed. Y. N. Lakshman). New York: ACM Press, pp. 259-266, 1996.

Referenced on Wolfram|Alpha

Hermite Normal Form

Cite this as:

Weisstein, Eric W. "Hermite Normal Form." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/HermiteNormalForm.html

Subject classifications