Given an m x n Matrix B of values in E, HermiteForm[E](B) returns the Hermite form H of B, an m x n Matrix of values in E.

The Hermite normal form Matrix H satisfies:

The uniqueness of H depends on the uniqueness of the remainder operation in E. For example, if E is the ring of integers, and a and b are integers, and the remainder of a / b is in the positive range 0..abs(b)-1, then H is unique. If Maple's irem function is used, as in the example below, because the remainder is in the range 1-abs(b)..abs(b)-1, H is not unique.

The (indexed) parameter E, which specifies the domain of computation, a Euclidean domain, must be a Maple table/module which has the following values/exports:

E[`0`]: a constant for the zero of the ring E

E[`1`]: a constant for the (multiplicative) identity of E

E[`+`]: a procedure for adding elements of E (nary)

E[`-`]: a procedure for negating and subtracting elements of E (unary and binary)

E[`*`]: a procedure for multiplying two elements of E (commutative)

E[`=`]: a boolean procedure for testing if two elements in F are equal

E[Quo]: a procedure which computes the quotient of a / b. E[Quo](a,b,'r') computes the quotient q of a / b and optionally assigns r the remainder satisfying a = b q + r.

E[Rem]: a procedure for finding the remainder of a / b. E[Rem(a,b,'q') computes the remainder r of a / b and optionally assigns q the quotient satisfying a = b q + r.

E[Gcdex]: a procedure for finding the gcd g of a and b, an element of E. E[Gcdex](a,b,'s','t') computes the gcd of a and b and optionally assigns s and t elements of E satisfying s a + t b = g.

E[UnitPart]: a procedure for returning the unit part of an element in E

E[EuclideanNorm]: a procedure for computing the Euclidean norm of an element in E, a non-negative integer.

For a,b in E, b non-zero, the remainder r and quotient q satisfy a = b q + r and r = 0 or EuclideanNorm(r) < EuclideanNorm(b).

For non-zero a,b in E, units u,v in E, the Euclidean norm satisfies:

EuclideanNorm(a b) >= EuclideanNorm(a)

EuclideanNorm(u) = EuclideanNorm(v)

EuclideanNorm(u a) = EuclideanNorm(a)

The Hermite form is computed by putting the principal block H[1..i,1..i] into Hermite form using elementary Row operations. This algorithm does at most O(n^4) operations in E.

$\mathrm{with}\left(\mathrm{LinearAlgebra}\left[\mathrm{Generic}\right]\right)\&colon;$

$Z\left[\mathrm{`0`}\right],Z\left[\mathrm{`1`}\right],Z\left[\mathrm{`+`}\right],Z\left[\mathrm{`-`}\right],Z\left[\mathrm{`*`}\right],Z\left[\mathrm{`=`}\right]≔0,1,\mathrm{`+`},\mathrm{`-`},\mathrm{`*`},\mathrm{`=`}\&colon;$

$Z\left[\mathrm{Gcdex}\right]≔\mathrm{igcdex}\&colon;$

$Z\left[\mathrm{Quo}\right],Z\left[\mathrm{Rem}\right]≔\mathrm{iquo},\mathrm{irem}\&colon;$

$Z\left[\mathrm{UnitPart}\right]≔\mathrm{sign}\&colon;$

$Z\left[\mathrm{EuclideanNorm}\right]≔\mathrm{abs}\&colon;$

$A≔\mathrm{Matrix}\left(\left[\left[1\&comma;2\&comma;3\&comma;4\&comma;5\right]\&comma;\left[2\&comma;3\&comma;4\&comma;5\&comma;6\right]\&comma;\left[4\&comma;1\&comma;-2\&comma;-5\&comma;-2\right]\&comma;\left[-1\&comma;-4\&comma;-2\&comma;1\&comma;2\right]\right]\right)$

$A≔\left[\begin{array}{ccccc}1& 2& 3& 4& 5\\ 2& 3& 4& 5& 6\\ 4& 1& \mathrm{-2}& \mathrm{-5}& \mathrm{-2}\\ \mathrm{-1}& \mathrm{-4}& \mathrm{-2}& 1& 2\end{array}\right]$

$H≔\mathrm{HermiteForm}\left[Z\right]\left(A\right)$

$H≔\left[\begin{array}{ccccc}1& 0& \mathrm{-1}& \mathrm{-2}& \mathrm{-3}\\ 0& 1& 2& 3& 4\\ 0& 0& 5& 11& 3\\ 0& 0& 0& 0& 6\end{array}\right]$

$H,U≔\mathrm{HermiteForm}\left[Z\right]\left(A\&comma;\mathrm{output}=\left['H'\&comma;'U'\right]\right)$

$H,U≔\left[\begin{array}{ccccc}1& 0& \mathrm{-1}& \mathrm{-2}& \mathrm{-3}\\ 0& 1& 2& 3& 4\\ 0& 0& 5& 11& 3\\ 0& 0& 0& 0& 6\end{array}\right],\left[\begin{array}{cccc}\mathrm{-3}& 2& 0& 0\\ 2& \mathrm{-1}& 0& 0\\ \mathrm{-15}& 12& \mathrm{-2}& 1\\ 10& \mathrm{-7}& 1& 0\end{array}\right]$

$\mathrm{MatrixMatrixMultiply}\left[Z\right]\left(U\&comma;A\right)$

$\left[\begin{array}{ccccc}1& 0& \mathrm{-1}& \mathrm{-2}& \mathrm{-3}\\ 0& 1& 2& 3& 4\\ 0& 0& 5& 11& 3\\ 0& 0& 0& 0& 6\end{array}\right]$

Z[Quo] := proc(a,b,r) local q,rr; rr := Z[Rem](a,b,'q'); if nargs=3 then r := rr; end if; q; end proc:

Z[Rem] := proc(a,b,q) local r,qq; r := modp(a,b); if nargs=3 then q := iquo(a-r,b); end if; r; end proc:

$H≔\mathrm{HermiteForm}\left[Z\right]\left(A\right)$

$H≔\left[\begin{array}{ccccc}1& 0& 4& 9& 0\\ 0& 1& 2& 3& 4\\ 0& 0& 5& 11& 3\\ 0& 0& 0& 0& 6\end{array}\right]$

$U≔\mathrm{HermiteForm}\left[Z\right]\left(A\&comma;\mathrm{output}='U'\right)$

$U≔\left[\begin{array}{cccc}\mathrm{-18}& 14& \mathrm{-2}& 1\\ 2& \mathrm{-1}& 0& 0\\ \mathrm{-15}& 12& \mathrm{-2}& 1\\ 10& \mathrm{-7}& 1& 0\end{array}\right]$

$\mathrm{MatrixMatrixMultiply}\left[Z\right]\left(U\&comma;A\right)$

$\left[\begin{array}{ccccc}1& 0& 4& 9& 0\\ 0& 1& 2& 3& 4\\ 0& 0& 5& 11& 3\\ 0& 0& 0& 0& 6\end{array}\right]$