compute the Hermite form of a Matrix - Maple Help

Online Help

All Products    Maple    MapleSim


Home : Support : Online Help : Mathematics : Linear Algebra : LinearAlgebra Package : Generic Subpackage : LinearAlgebra/Generic/HermiteForm

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

withLinearAlgebra&lsqb;Generic&rsqb;&colon;

Z`0`&comma;Z`1`&comma;Z`+`&comma;Z`-`&comma;Z`*`&comma;Z`=`:=0&comma;1&comma;`+`&comma;`-`&comma;`*`&comma;`=`&colon;

ZGcdex:=igcdex&colon;

ZQuo&comma;ZRem:=iquo&comma;irem&colon;

ZUnitPart:=sign&colon;

ZEuclideanNorm:=abs&colon;

A:=Matrix1&comma;2&comma;3&comma;4&comma;5&comma;2&comma;3&comma;4&comma;5&comma;6&comma;4&comma;1&comma;2&comma;5&comma;2&comma;1&comma;4&comma;2&comma;1&comma;2

A:=12345234564125214212

(1)

H:=HermiteFormZA

H:=101230123400511300006

(2)

H&comma;U:=HermiteFormZA&comma;output&equals;&apos;H&apos;&comma;&apos;U&apos;

H&comma;U:=101230123400511300006&comma;3200210015122110710

(3)

MatrixMatrixMultiplyZU&comma;A

101230123400511300006

(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:=HermiteFormZA

H:=104900123400511300006

(5)

U:=HermiteFormZA&comma;output&equals;&apos;U&apos;

U:=181421210015122110710

(6)

MatrixMatrixMultiplyZU&comma;A

104900123400511300006

(7)

See Also

Euclidean Norm , LinearAlgebra[Generic], LinearAlgebra[HermiteForm]


Download Help Document

Was this information helpful?



Please add your Comment (Optional)
E-mail Address (Optional)
What is ? This question helps us to combat spam