HermiteDecomposition

$\{u, h\}$ with $u$ unimodular and $u \cdot m = h$ upper triangular in Hermite normal form.

✓ checked against that system · ! checked, with disagreements (hover a chip)Wolfram LanguageHermiteDecomposition✓↗

HermiteDecomposition(m)a unimodular $u$ and $h = u \cdot m$ in Hermite normal form

Typed signatures

Type	Package	Applies
(list<list<integer>>) -> list	number-theory	always

Domain: Number theory

Details

• $h$ is upper triangular with positive pivots, and every entry above a pivot is reduced into $[0, \text{pivot})$ — the row-reduced convention that makes $h$ unique for a given $m$.
• $u \in GL_n(\mathbb{Z})$: $\det u = \pm 1$, so $u$ is invertible over $\mathbb{Z}$, not merely over $\mathbb{Q}$.
• Used by ProfiniteDecomposition to put a matrix over $\hat{\mathbb{Q}}$ into strong-approximation form (Hertogh's Algorithm 8.4).

Examples

1 more kept as data, checked against the oracles

Basic #

live ↗

In$\mathrm{HermiteDecomposition}(\bigl\lbrack\bigl\lbrack0, -3\bigr\rbrack, \bigl\lbrack2, 0\bigr\rbrack\bigr\rbrack)$Out$\bigl\lbrack\bigl\lbrack\bigl\lbrack0, 1\bigr\rbrack, \bigl\lbrack-1, 0\bigr\rbrack\bigr\rbrack, \bigl\lbrack\bigl\lbrack2, 0\bigr\rbrack, \bigl\lbrack0, 3\bigr\rbrack\bigr\rbrack\bigr\rbrack$

live ↗

In$\mathrm{HermiteDecomposition}(\bigl\lbrack\bigl\lbrack1, 2\bigr\rbrack, \bigl\lbrack3, 4\bigr\rbrack\bigr\rbrack)$Out$\bigl\lbrack\bigl\lbrack\bigl\lbrack-2, 1\bigr\rbrack, \bigl\lbrack3, -1\bigr\rbrack\bigr\rbrack, \bigl\lbrack\bigl\lbrack1, 0\bigr\rbrack, \bigl\lbrack0, 2\bigr\rbrack\bigr\rbrack\bigr\rbrack$

Scope #

$3\times3$, $\det u=-1$

live ↗

In$\mathrm{HermiteDecomposition}(\bigl\lbrack\bigl\lbrack1, 2, 3\bigr\rbrack, \bigl\lbrack4, 5, 6\bigr\rbrack, \bigl\lbrack7, 8, 10\bigr\rbrack\bigr\rbrack)$Out$\bigl\lbrack\bigl\lbrack\bigl\lbrack-2, 6, -3\bigr\rbrack, \bigl\lbrack-2, 11, -6\bigr\rbrack, \bigl\lbrack1, -2, 1\bigr\rbrack\bigr\rbrack, \bigl\lbrack\bigl\lbrack1, 2, 0\bigr\rbrack, \bigl\lbrack0, 3, 0\bigr\rbrack, \bigl\lbrack0, 0, 1\bigr\rbrack\bigr\rbrack\bigr\rbrack$

Rectangular: the column without a pivot is left unreduced

live ↗

In$\mathrm{HermiteDecomposition}(\bigl\lbrack\bigl\lbrack2, 3, 5\bigr\rbrack, \bigl\lbrack7, 11, 13\bigr\rbrack\bigr\rbrack)$Out$\bigl\lbrack\bigl\lbrack\bigl\lbrack11, -3\bigr\rbrack, \bigl\lbrack-7, 2\bigr\rbrack\bigr\rbrack, \bigl\lbrack\bigl\lbrack1, 0, 16\bigr\rbrack, \bigl\lbrack0, 1, -9\bigr\rbrack\bigr\rbrack\bigr\rbrack$

Returns a unimodular matrix and the upper-triangular Hermite form

live ↗

In$\mathrm{HermiteDecomposition}(\bigl\lbrack\bigl\lbrack0, 5, 4\bigr\rbrack, \bigl\lbrack3, 1, 2\bigr\rbrack, \bigl\lbrack3, 5, 4\bigr\rbrack\bigr\rbrack)$Out$\bigl\lbrack\bigl\lbrack\bigl\lbrack-1, 0, 1\bigr\rbrack, \bigl\lbrack1, 1, -1\bigr\rbrack, \bigl\lbrack4, 5, -5\bigr\rbrack\bigr\rbrack, \bigl\lbrack\bigl\lbrack3, 0, 0\bigr\rbrack, \bigl\lbrack0, 1, 2\bigr\rbrack, \bigl\lbrack0, 0, 6\bigr\rbrack\bigr\rbrack\bigr\rbrack$

Possible issues #

Singular: $h$ gains a zero row, and $u$ is no longer unique

live ↗

In$\mathrm{HermiteDecomposition}(\bigl\lbrack\bigl\lbrack1, 2\bigr\rbrack, \bigl\lbrack2, 4\bigr\rbrack\bigr\rbrack)$Out$\bigl\lbrack\bigl\lbrack\bigl\lbrack1, 0\bigr\rbrack, \bigl\lbrack-2, 1\bigr\rbrack\bigr\rbrack, \bigl\lbrack\bigl\lbrack1, 2\bigr\rbrack, \bigl\lbrack0, 0\bigr\rbrack\bigr\rbrack\bigr\rbrack$

About

Examples	7
Checked against	Wolfram Language 7 agree
Crosswalk	Wolfram Language

Implementation

mappedwolframpackages/oracle/src/mappings.ts

See also: ProfiniteDecomposition, ExtendedGCD