Hermite Form - Maple Help

LinearAlgebra[Generic]

 HermiteForm
 compute the Hermite form of a Matrix

 Calling Sequence HermiteForm[E](B) HermiteForm[E](B,output=out)

Parameters

 E - the domain of computation, a Euclidean domain B - m x n Matrix of values in E out - one of H, U or a list containing one or more of these names

Description

 • 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:

(1) H is row-equivalent to B and H is in row echelon form

(2) The bottom-most nonzero entry p[j] = H[b,j] in each column j is unit normal, and either H[i,j]=0 or the Euclidean norm of H[i,j] where i<b is less than Euclidean norm of p[j]

(3) If B is n x n square Matrix, then prod(H[i,i],i=1..n) = u*det(B) where u is a unit in E

 • 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.

Examples

 > $\mathrm{with}\left(\mathrm{LinearAlgebra}\left[\mathrm{Generic}\right]\right):$
 > $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{=}:$
 > $Z\left[\mathrm{Gcdex}\right]≔\mathrm{igcdex}:$
 > $Z\left[\mathrm{Quo}\right],Z\left[\mathrm{Rem}\right]≔\mathrm{iquo},\mathrm{irem}:$
 > $Z\left[\mathrm{UnitPart}\right]≔\mathrm{sign}:$
 > $Z\left[\mathrm{EuclideanNorm}\right]≔\mathrm{abs}:$
 > $A≔\mathrm{Matrix}\left(\left[\left[1,2,3,4,5\right],\left[2,3,4,5,6\right],\left[4,1,-2,-5,-2\right],\left[-1,-4,-2,1,2\right]\right]\right)$
 ${A}{≔}\left[\begin{array}{ccccc}{1}& {2}& {3}& {4}& {5}\\ {2}& {3}& {4}& {5}& {6}\\ {4}& {1}& {-2}& {-5}& {-2}\\ {-1}& {-4}& {-2}& {1}& {2}\end{array}\right]$ (1)
 > $H≔\mathrm{HermiteForm}\left[Z\right]\left(A\right)$
 ${H}{≔}\left[\begin{array}{ccccc}{1}& {0}& {-1}& {-2}& {-3}\\ {0}& {1}& {2}& {3}& {4}\\ {0}& {0}& {5}& {11}& {3}\\ {0}& {0}& {0}& {0}& {6}\end{array}\right]$ (2)
 > $H,U≔\mathrm{HermiteForm}\left[Z\right]\left(A,\mathrm{output}=\left['H','U'\right]\right)$
 ${H}{,}{U}{≔}\left[\begin{array}{ccccc}{1}& {0}& {-1}& {-2}& {-3}\\ {0}& {1}& {2}& {3}& {4}\\ {0}& {0}& {5}& {11}& {3}\\ {0}& {0}& {0}& {0}& {6}\end{array}\right]{,}\left[\begin{array}{cccc}{-3}& {2}& {0}& {0}\\ {2}& {-1}& {0}& {0}\\ {-15}& {12}& {-2}& {1}\\ {10}& {-7}& {1}& {0}\end{array}\right]$ (3)
 > $\mathrm{MatrixMatrixMultiply}\left[Z\right]\left(U,A\right)$
 $\left[\begin{array}{ccccc}{1}& {0}& {-1}& {-2}& {-3}\\ {0}& {1}& {2}& {3}& {4}\\ {0}& {0}& {5}& {11}& {3}\\ {0}& {0}& {0}& {0}& {6}\end{array}\right]$ (4)

Using positive range for the remainder, given by modp(a,b).

 > 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]$ (5)
 > $U≔\mathrm{HermiteForm}\left[Z\right]\left(A,\mathrm{output}='U'\right)$
 ${U}{≔}\left[\begin{array}{cccc}{-18}& {14}& {-2}& {1}\\ {2}& {-1}& {0}& {0}\\ {-15}& {12}& {-2}& {1}\\ {10}& {-7}& {1}& {0}\end{array}\right]$ (6)
 > $\mathrm{MatrixMatrixMultiply}\left[Z\right]\left(U,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]$ (7)