LinearAlgebra - Maple Programming Help

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

LinearAlgebra

 HermiteForm
 compute the Hermite normal form of a Matrix

 Calling Sequence HermiteForm(A, x, m, out, options, outopts)

Parameters

 A - Matrix x - (optional) name; specify the variable in which the entries of A are rational polynomials over Q m - (optional) equation of the form method = name where name is one of 'integer' or 'rational'; specify the method to use out - (optional) equation of the form output = obj where obj is one of 'H' or 'U', or a list containing one or more of these names; select result objects to compute options - (optional); constructor options for the result object(s) outopts - (optional) equation(s) of the form outputoptions[o] = list where o is one of 'H' or 'U'; constructor options for the specified result object

Description

 • The HermiteForm(A) function computes the Hermite normal form (row reduced echelon form) of an m x n rectangular Matrix of univariate polynomials in x over the field of rational numbers Q, or rational expressions over Q.
 The Hermite normal form H is obtained by doing elementary row operations on A. This includes interchanging rows, multiplying through a row by a unit, and subtracting a polynomial multiple of one row from another.
 The number of nonzero rows of H is Rank(A). If n = m, $\prod _{i=1}^{n}\phantom{\rule[-0.0ex]{5.0px}{0.0ex}}{H}_{i,i}=\mathrm{normal}\left(\mathrm{Determinant}\left(A\right)\right)$ where normal means unit normal, that is, monic.
 • If the variable x is specified, or if the option method='rational' is specified, or if the Matrix A is not of type 'Matrix(integer)', computation takes place over the field of rational polynomials. If the option method='integer' is specified, or if an optional variable name is not specified and the Matrix A is of type 'Matrix(integer)', the computation takes place over the integers to supply the integer-only Hermite normal form.
 If the variable name x is not specified and the Matrix is not of type 'Matrix(integer)', the routine selects the indeterminate if indets(A) has a single member, and returns an error if indets(A) has more than a single member. If indets(A) has no members and A is not of type 'Matrix(integer)', the computation takes place over the field of rational polynomials using a dummy variable.
 • The output option (out) determines the content of the returned expression sequence.
 Depending on what is included in the output option, an expression sequence containing one or more of the factors H (the Hermite normal form) or U (the transformation Matrix) are returned. If output is a list, the objects are returned in the same order as specified in the list.
 The returned Matrix objects have the property that $H=U\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}.\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}A$.
 • Specifying the option method='integer[reduced]' causes the integer transformation matrix U to be reduced using lattice basis reduction.  This can result in substantially smaller entries if the input matrix A does not have full row rank, but at an increased running time.
 • The constructor options provide additional information (readonly, shape, storage, order, datatype, and attributes) to the Matrix constructor that builds the result. These options may also be provided in the form outputoptions[o]=[...], where [...] represents a Maple list.  If a constructor option is provided in both the calling sequence directly and in an outputoptions[o] option, the latter takes precedence (regardless of the order).
 The following list indicates permissible values for the index [o] of outputoptions with their corresponding meaning.

 H Hermite form U transformation Matrix

 • This function is part of the LinearAlgebra package, and so it can be used in the form HermiteForm(..) only after executing the command with(LinearAlgebra). However, it can always be accessed through the long form of the command by using LinearAlgebra[HermiteForm](..).

Examples

 > $\mathrm{with}\left(\mathrm{LinearAlgebra}\right):$
 > $A≔⟨⟨3+z,4,{z}^{2}-1⟩|⟨1,z,4⟩|⟨-4,2,-1⟩⟩$
 ${A}{:=}\left[\begin{array}{ccc}{3}{+}{z}& {1}& {-}{4}\\ {4}& {z}& {2}\\ {{z}}^{{2}}{-}{1}& {4}& {-}{1}\end{array}\right]$ (1)
 > $H,U≔\mathrm{HermiteForm}\left(A,\mathrm{output}=\left['H','U'\right]\right)$
 ${H}{,}{U}{:=}\left[\begin{array}{ccc}{1}& {0}& {-}\frac{{7}}{{76}}{}{{z}}^{{2}}{+}\frac{{29}}{{304}}{}{z}{-}\frac{{53}}{{152}}\\ {0}& {1}& \frac{{3}}{{19}}{}{{z}}^{{2}}{+}\frac{{31}}{{76}}{}{z}{-}\frac{{37}}{{38}}\\ {0}& {0}& {{z}}^{{3}}{+}\frac{{1}}{{4}}{}{{z}}^{{2}}{-}\frac{{15}}{{4}}{}{z}{-}\frac{{43}}{{2}}\end{array}\right]{,}\left[\begin{array}{ccc}\frac{{7}}{{304}}{}{{z}}^{{2}}{-}\frac{{9}}{{304}}{}{z}{+}\frac{{3}}{{19}}& {-}\frac{{7}}{{304}}{}{z}{+}\frac{{37}}{{304}}& {-}\frac{{7}}{{304}}{}{z}{-}\frac{{3}}{{76}}\\ {-}\frac{{3}}{{76}}{}{{z}}^{{2}}{-}\frac{{7}}{{76}}{}{z}{+}\frac{{3}}{{19}}& \frac{{3}}{{76}}{}{z}{-}\frac{{5}}{{76}}& \frac{{3}}{{76}}{}{z}{+}\frac{{4}}{{19}}\\ {-}\frac{{1}}{{4}}{}{{z}}^{{3}}{+}\frac{{1}}{{4}}{}{z}{+}{4}& \frac{{1}}{{4}}{}{{z}}^{{2}}{-}{z}{-}\frac{{13}}{{4}}& \frac{{1}}{{4}}{}{{z}}^{{2}}{+}\frac{{3}}{{4}}{}{z}{-}{1}\end{array}\right]$ (2)
 > $\mathrm{map}\left(\mathrm{expand},U\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}.\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}A\right)$
 $\left[\begin{array}{ccc}{1}& {0}& {-}\frac{{7}}{{76}}{}{{z}}^{{2}}{+}\frac{{29}}{{304}}{}{z}{-}\frac{{53}}{{152}}\\ {0}& {1}& \frac{{3}}{{19}}{}{{z}}^{{2}}{+}\frac{{31}}{{76}}{}{z}{-}\frac{{37}}{{38}}\\ {0}& {0}& {{z}}^{{3}}{+}\frac{{1}}{{4}}{}{{z}}^{{2}}{-}\frac{{15}}{{4}}{}{z}{-}\frac{{43}}{{2}}\end{array}\right]$ (3)
 > $\mathrm{mul}\left({H}_{i,i},i=1..3\right)$
 ${{z}}^{{3}}{+}\frac{{1}}{{4}}{}{{z}}^{{2}}{-}\frac{{15}}{{4}}{}{z}{-}\frac{{43}}{{2}}$ (4)
 > $\mathrm{Determinant}\left(A\right)$
 ${4}{}{{z}}^{{3}}{+}{{z}}^{{2}}{-}{15}{}{z}{-}{86}$ (5)
 > $\frac{}{\mathrm{lcoeff}\left(\right)}$
 ${{z}}^{{3}}{+}\frac{{1}}{{4}}{}{{z}}^{{2}}{-}\frac{{15}}{{4}}{}{z}{-}\frac{{43}}{{2}}$ (6)
 > $\mathrm{HermiteForm}\left(⟨⟨0,2,x⟩|⟨0,2y,xy⟩⟩,x\right)$
 $\left[\begin{array}{cc}{1}& {y}\\ {0}& {0}\\ {0}& {0}\end{array}\right]$ (7)
 > $A≔\mathrm{RandomMatrix}\left(5,3\right)$
 ${A}{:=}\left[\begin{array}{rrr}{-}{76}& {-}{4}& {29}\\ {-}{72}& {27}& {44}\\ {-}{2}& {8}& {92}\\ {-}{32}& {69}& {-}{31}\\ {-}{74}& {99}& {67}\end{array}\right]$ (8)
 > $\mathrm{HermiteForm}\left(A,\mathrm{output}=\left['U'\right]\right)$
 $\left[\begin{array}{rrrrr}{69344}& {-}{89820}& {33007}& {35340}& {0}\\ {177773}& {-}{230266}& {84618}& {90599}& {0}\\ {115385}& {-}{149456}& {54922}& {58804}& {0}\\ {199471}& {-}{258371}& {94946}& {101657}& {0}\\ {174571}& {-}{226119}& {83093}& {88966}& {1}\end{array}\right]$ (9)
 > $\mathrm{HermiteForm}\left(A,\mathrm{output}=\left['U'\right],\mathrm{method}='\mathrm{integer}[\mathrm{reduced}]'\right)$
 $\left[\begin{array}{rrrrr}{64}& {-}{164}& {-}{112}& {-}{153}& {163}\\ {-}{50}& {113}& {61}& {85}& {-}{97}\\ {99}& {-}{266}& {-}{195}& {-}{265}& {277}\\ {271}& {-}{355}& {122}& {129}& {8}\\ {32}& {-}{408}& {-}{629}& {-}{823}& {737}\end{array}\right]$ (10)