Hermite normal form
E502190
Hermite normal form is a canonical matrix form used in linear algebra and number theory to uniquely represent integer matrices and solve systems of linear Diophantine equations.
Statements (47)
| Predicate | Object |
|---|---|
| instanceOf |
concept in linear algebra
ⓘ
concept in number theory ⓘ matrix normal form ⓘ |
| algorithmicProperty |
can be computed in polynomial time in the size of the input matrix
ⓘ
can be computed using elementary integer column operations ⓘ can be computed using elementary integer row operations ⓘ |
| alsoKnownAs | HNF NERFINISHED ⓘ |
| application |
computing bases of solution spaces of homogeneous Diophantine systems
ⓘ
computing integer hulls in polyhedral theory ⓘ cryptographic lattice constructions ⓘ solving Ax = b over the integers ⓘ |
| belongsTo | theory of finitely generated abelian groups ⓘ |
| canonicalFormFor |
integer matrices under left multiplication by unimodular matrices (row HNF)
ⓘ
integer matrices under right multiplication by unimodular matrices (column HNF) ⓘ |
| definedOver | integers ⓘ |
| diagonalCondition | diagonal entries are positive ⓘ |
| entryCondition | all entries are integers ⓘ |
| equivalenceRelation | two integer matrices are equivalent if they have the same Hermite normal form ⓘ |
| fieldRestriction | not defined as a normal form over arbitrary fields ⓘ |
| generalizationOf | Gaussian elimination to integer matrices with remainder constraints ⓘ |
| guarantees |
existence of a basis of the integer column space in triangular form
ⓘ
existence of a basis of the integer row space in triangular form ⓘ |
| matrixType |
lower triangular matrix (row HNF convention)
ⓘ
upper triangular matrix (column HNF convention) ⓘ |
| namedAfter | Charles Hermite NERFINISHED ⓘ |
| normalizationDirection |
column Hermite normal form
ⓘ
row Hermite normal form ⓘ |
| offDiagonalCondition |
entries above the diagonal are nonnegative (column HNF)
ⓘ
entries below the diagonal are nonnegative (row HNF) ⓘ |
| relatedTo |
Smith normal form
NERFINISHED
ⓘ
integer kernel computation ⓘ lattice basis reduction ⓘ unimodular matrix ⓘ |
| remainderCondition | off-diagonal entries are strictly smaller than the corresponding diagonal entry ⓘ |
| stabilityProperty | invariant under multiplication by unimodular matrices on one side ⓘ |
| uniquenessProperty | each integer matrix has a unique Hermite normal form up to unimodular transformations ⓘ |
| usedFor |
canonical representation of integer matrices
ⓘ
computing a basis of the integer column space ⓘ computing a basis of the integer row space ⓘ computing determinant of an integer matrix (up to sign) ⓘ computing lattice bases ⓘ computing rank of an integer matrix ⓘ solving systems of linear Diophantine equations ⓘ testing integer matrix equivalence ⓘ |
| usedIn |
algorithmic number theory
ⓘ
computational geometry of numbers ⓘ integer linear algebra ⓘ |
Referenced by (2)
Full triples — surface form annotated when it differs from this entity's canonical label.