This is a subset of the functions available in GAP4, ported to GAP3 to be used by CHEVIE.

- NullspaceIntMat
- SolutionIntMat
- SolutionNullspaceIntMat
- BaseIntMat
- BaseIntersectionIntMats
- ComplementIntMat
- TriangulizedIntegerMat
- TriangulizedIntegerMatTransform
- TriangulizeIntegerMat
- HermiteNormalFormIntegerMat
- HermiteNormalFormIntegerMatTransform
- SmithNormalFormIntegerMat
- SmithNormalFormIntegerMatTransforms
- DiagonalizeIntMat
- NormalFormIntMat
- AbelianInvariantsOfList
- Determinant of an integer matrix
- Diaconis-Graham normal form

`NullspaceIntMat( `

`mat` )

If `mat` is a matrix with integral entries, this function returns a list of
vectors that forms a basis of the integral nullspace of `mat`, i.e. of
those vectors in the nullspace of `mat` that have integral entries.

gap> mat:=[[1,2,7],[4,5,6],[7,8,9],[10,11,19],[5,7,12]];; gap> NullspaceMat(mat); [ [ 1, 0, 3/4, -1/4, -3/4 ], [ 0, 1, -13/24, 1/8, -7/24 ] ] gap> NullspaceIntMat(mat); [ [ 1, 18, -9, 2, -6 ], [ 0, 24, -13, 3, -7 ] ]

`SolutionIntMat( `

`mat`, `vec` )

If `mat` is a matrix with integral entries and `vec` a vector with integral
entries, this function returns a vector `x` with integer entries that is a
solution of the equation

. It returns `x`*`mat`=`vec``false`

if no such
vector exists.

gap> mat:=[[1,2,7],[4,5,6],[7,8,9],[10,11,19],[5,7,12]];; gap> SolutionMat(mat,[95,115,182]); [ 47/4, -17/2, 67/4, 0, 0 ] gap> SolutionIntMat(mat,[95,115,182]); [ 2285, -5854, 4888, -1299, 0 ]

`SolutionNullspaceIntMat( `

`mat`, `vec` )

This function returns a list of length two, its first entry being the
result of a call to `SolutionIntMat`

with same arguments, the second the
result of `NullspaceIntMat`

applied to the matrix `mat`. The calculation is
performed faster than if two separate calls would be used.

gap> mat:=[[1,2,7],[4,5,6],[7,8,9],[10,11,19],[5,7,12]];; gap> SolutionNullspaceIntMat(mat,[95,115,182]); [ [ 2285, -5854, 4888, -1299, 0 ], [ [ 1, 18, -9, 2, -6 ], [ 0, 24, -13, 3, -7 ] ] ]

`BaseIntMat( `

`mat` )

If `mat` is a matrix with integral entries, this function returns a list of
vectors that forms a basis of the integral row space of `mat`, i.e. of the
set of integral linear combinations of the rows of `mat`.

gap> mat:=[[1,2,7],[4,5,6],[10,11,19]];; gap> BaseIntMat(mat); [ [ 1, 2, 7 ], [ 0, 3, 7 ], [ 0, 0, 15 ] ]

`BaseIntersectionIntMats( `

`m`, `n` )

If `m` and `n` are matrices with integral entries, this function returns a
list of vectors that forms a basis of the intersection of the integral row
spaces of `m` and `n`.

gap> nat:=[[5,7,2],[4,2,5],[7,1,4]];; gap> BaseIntMat(nat); [ [ 1, 1, 15 ], [ 0, 2, 55 ], [ 0, 0, 64 ] ] gap> BaseIntersectionIntMats(mat,nat); [ [ 1, 5, 509 ], [ 0, 6, 869 ], [ 0, 0, 960 ] ]

`ComplementIntMat( `

`full`, `sub` )

Let `full` be a list of integer vectors generating an Integral module `M`
and `sub` a list of vectors defining a submodule `S`. This function
computes a free basis for `M` that extends `S`, that is, if the dimension
of `S` is `n` it determines a basis *{b _{1},...,b_{m}}* for

It returns a record with the following components:

`complement`

:

the vectors*b*up to_{n+1}*b*(they generate a complement to_{m}`S`).

`sub`

:

the vectors*s*(a basis for_{i}`S`).

`moduli`

:

the factors*x*._{i}

gap> m:=IdentityMat(3);; gap> n:=[[1,2,3],[4,5,6]];; gap> ComplementIntMat(m,n); rec( complement := [ [ 0, 0, 1 ] ], sub := [ [ 1, 2, 3 ], [ 0, 3, 6 ] ], moduli := [ 1, 3 ] )

`TriangulizedIntegerMat( `

`mat` )

Computes an integral upper triangular form of a matrix with integer entries.

gap> m:=[[1,15,28],[4,5,6],[7,8,9]];; gap> TriangulizedIntegerMat(m); [ [ 1, 15, 28 ], [ 0, 1, 1 ], [ 0, 0, 3 ] ]

`TriangulizedIntegerMatTransform( `

`mat` )

Computes an integral upper triangular form of a matrix with integer
entries. It returns a record with a component `normal`

(a matrix in upper
triangular form) and a component `rowtrans`

that gives the transformations
done to the original matrix to bring it into upper triangular form.

gap> m:=[[1,15,28],[4,5,6],[7,8,9]];; gap> n:=TriangulizedIntegerMatTransform(m); rec( normal := [ [ 1, 15, 28 ], [ 0, 1, 1 ], [ 0, 0, 3 ] ], rowC := [ [ 1, 0, 0 ], [ 0, 1, 0 ], [ 0, 0, 1 ] ], rowQ := [ [ 1, 0, 0 ], [ 1, -30, 17 ], [ -3, 97, -55 ] ], rank := 3, signdet := 1, rowtrans := [ [ 1, 0, 0 ], [ 1, -30, 17 ], [ -3, 97, -55 ] ] ) gap> n.rowtrans*m=n.normal; true

`TriangulizeIntegerMat( `

`mat` )

Changes `mat` to be in upper triangular form. (The result is the same as
that of `TriangulizedIntegerMat`

, but `mat` will be modified, thus using
less memory.)

gap> m:=[[1,15,28],[4,5,6],[7,8,9]];; gap> TriangulizeIntegerMat(m); m; [ [ 1, 15, 28 ], [ 0, 1, 1 ], [ 0, 0, 3 ] ]

`HermiteNormalFormIntegerMat( `

`mat` )

This operation computes the Hermite normal form of a matrix `mat` with
integer entries. The Hermite Normal Form (HNF), *H* of an integer matrix,
*A* is a row equivalent upper triangular form such that all off-diagonal
entries are reduced modulo the diagonal entry of the column they are in.
There exists a unique unimodular matrix *Q* such that *QA = H*.

gap> m:=[[1,15,28],[4,5,6],[7,8,9]];; gap> HermiteNormalFormIntegerMat(m); [ [ 1, 0, 1 ], [ 0, 1, 1 ], [ 0, 0, 3 ] ]

`HermiteNormalFormIntegerMatTransform( `

`mat` )

This operation computes the Hermite normal form of a matrix `mat` with
integer entries. It returns a record with components `normal`

(a matrix *H*
of the Hermite normal form) and `rowtrans`

(a unimodular matrix *Q*) such
that *Q*`mat`*=H*

gap> m:=[[1,15,28],[4,5,6],[7,8,9]];; gap> n:=HermiteNormalFormIntegerMatTransform(m); rec( normal := [ [ 1, 0, 1 ], [ 0, 1, 1 ], [ 0, 0, 3 ] ], rowC := [ [ 1, 0, 0 ], [ 0, 1, 0 ], [ 0, 0, 1 ] ], rowQ := [ [ -2, 62, -35 ], [ 1, -30, 17 ], [ -3, 97, -55 ] ], rank := 3, signdet := 1, rowtrans := [ [ -2, 62, -35 ], [ 1, -30, 17 ], [ -3, 97, -55 ] ] ) gap> n.rowtrans*m=n.normal; true

`SmithNormalFormIntegerMat( `

`mat` )

This operation computes the Smith normal form of a matrix `mat` with
integer entries. The Smith Normal Form,*S*, of an integer matrix *A* is the
unique equivalent diagonal form with *S _{i}* dividing

gap> m:=[[1,15,28],[4,5,6],[7,8,9]];; gap> SmithNormalFormIntegerMat(m); [ [ 1, 0, 0 ], [ 0, 1, 0 ], [ 0, 0, 3 ] ]

`SmithNormalFormIntegerMatTransforms( `

`mat` )

This operation computes the Smith normal form of a matrix `mat` with
integer entries. It returns a record with components `normal`

(a matrix
*S*), `rowtrans`

(a matrix *P*), and `coltrans`

(a matrix *Q*) such that
*P*`mat`*Q=S*.

gap> m:=[[1,15,28],[4,5,6],[7,8,9]];; gap> n:=SmithNormalFormIntegerMatTransforms(m); rec( normal := [ [ 1, 0, 0 ], [ 0, 1, 0 ], [ 0, 0, 3 ] ], rowC := [ [ 1, 0, 0 ], [ 0, 1, 0 ], [ 0, 0, 1 ] ], rowQ := [ [ -2, 62, -35 ], [ 1, -30, 17 ], [ -3, 97, -55 ] ], colC := [ [ 1, 0, 0 ], [ 0, 1, 0 ], [ 0, 0, 1 ] ], colQ := [ [ 1, 0, -1 ], [ 0, 1, -1 ], [ 0, 0, 1 ] ], rank := 3, signdet := 1, rowtrans := [ [ -2, 62, -35 ], [ 1, -30, 17 ], [ -3, 97, -55 ] ], coltrans := [ [ 1, 0, -1 ], [ 0, 1, -1 ], [ 0, 0, 1 ] ] ) gap> n.rowtrans*m*n.coltrans=n.normal; true

`DiagonalizeIntMat( `

`mat` )

This function changes `mat` to its SNF. (The result is the same as that of
`SmithNormalFormIntegerMat`

, but `mat` will be modified, thus using less
memory.)

gap> m:=[[1,15,28],[4,5,6],[7,8,9]];; gap> DiagonalizeIntMat(m);m; [ [ 1, 0, 0 ], [ 0, 1, 0 ], [ 0, 0, 3 ] ]

All the previous routines build on the following ``workhorse'```
routine:
```

NormalFormIntMat( `mat`, `options` )```
This general operation for computation of various Normal Forms is probably
the most efficient.
Options bit values:
\begin{itemize}
\item{0/1} Triangular Form / Smith Normal Form.
\item{2} Reduce off diagonal entries.
\item{4} Row Transformations.
\item{8} Col Transformations.
\item{16} Destructive (the original matrix may be destroyed)
\end{itemize}
Compute a Triangular, Hermite or Smith form of the
```

normal*n × m* integer
input matrix *A*. Optionally, compute *n × n* and *m × m*
unimodular transforming matrices *Q, P* which satisfy *QA = H* or *QAP =
S*.
Note option is a value ranging from 0 - 15 but not all options make sense
(eg reducing off diagonal entries with SNF option selected already). If an
option makes no sense it is ignored.
Returns a record with component ```
containing the computed normal
form and optional components
```

rowtrans` and/or `

coltrans' which hold the
respective transformation matrix. Also in the record are components holding
the sign of the determinant, signdet, and the Rank of the matrix, rank.

gap> m:=[[1,15,28],[4,5,6],[7,8,9]];; gap> NormalFormIntMat(m,0); # Triangular, no transforms rec( normal := [ [ 1, 15, 28 ], [ 0, 1, 1 ], [ 0, 0, 3 ] ], rank := 3, signdet := 1 ) gap> NormalFormIntMat(m,6); # Hermite Normal Form with row transforms rec( normal := [ [ 1, 0, 1 ], [ 0, 1, 1 ], [ 0, 0, 3 ] ], rowC := [ [ 1, 0, 0 ], [ 0, 1, 0 ], [ 0, 0, 1 ] ], rowQ := [ [ -2, 62, -35 ], [ 1, -30, 17 ], [ -3, 97, -55 ] ], rank := 3, signdet := 1, rowtrans := [ [ -2, 62, -35 ], [ 1, -30, 17 ], [ -3, 97, -55 ] ] ) gap> NormalFormIntMat(m,13); # Smith Normal Form with both transforms rec( normal := [ [ 1, 0, 0 ], [ 0, 1, 0 ], [ 0, 0, 3 ] ], rowC := [ [ 1, 0, 0 ], [ 0, 1, 0 ], [ 0, 0, 1 ] ], rowQ := [ [ -2, 62, -35 ], [ 1, -30, 17 ], [ -3, 97, -55 ] ], colC := [ [ 1, 0, 0 ], [ 0, 1, 0 ], [ 0, 0, 1 ] ], colQ := [ [ 1, 0, -1 ], [ 0, 1, -1 ], [ 0, 0, 1 ] ], rank := 3, signdet := 1, rowtrans := [ [ -2, 62, -35 ], [ 1, -30, 17 ], [ -3, 97, -55 ] ], coltrans := [ [ 1, 0, -1 ], [ 0, 1, -1 ], [ 0, 0, 1 ] ] ) gap> last.rowtrans*m*last.coltrans; [ [ 1, 0, 0 ], [ 0, 1, 0 ], [ 0, 0, 3 ] ]

`AbelianInvariantsOfList( `

`list` )

Given a list of positive integers, this routine returns a list of prime powers, such that the prime power factors of the entries in the list are returned in sorted form.

gap> AbelianInvariantsOfList([4,6,2,12]); [ 2, 2, 3, 3, 4, 4 ]

`DeterminantIntMat( `

`mat` )

Computes the determinant of an integer matrix using the same strategy as
`NormalFormIntMat`

. This method is faster in general for matrices greater
than *20 × 20* but quite a lot slower for smaller matrices. It
therefore passes the work to the more general `DeterminantMat`

(see DeterminantMat) for these smaller matrices.

`DiaconisGraham( `

`mat`, `moduli`)

Diaconis and Graham (see dg99) defined a normal form for generating
sets of abelian groups. Here `moduli` should be a list of positive integers
such that `moduli[i+1]`

divides `moduli[i]`

for all `i`

, representing the
abelian group *A=ℤ/moduli[1]×...×ℤ/moduli[n]*. The integral
matrix `m` should have `n` columns where `n=Length(moduli)`

, and each line
(with the `i`-th element taken `mod moduli[i]`

) represents an element of
the group *A*.

The function returns `false`

if the set of elements of *A* represented by
the lines of *m* does not generate *A*. Otherwise it returns a record `r`

with fields

`r.normal`

:- the Diaconis-Graham normal form, a matrix of same shape
as
`m`

where either the first`n`

lines are the identity matrix and the remaining lines are`0`

, or`Length(m)=n`

and`.normal`

differs from the identity matrix only in the entry`.normal[n][n]`

, which is prime to`moduli[n]`

.

`r.rowtrans`

:- a unimodular matrix such that
`r.normal=List(r.rowtrans*m,v->Zip(v,moduli, function(x,y)return x mod y;end))`

Here is an example:

gap> DiaconisGraham([[3,0],[4,1]],[10,5]); rec( rowtrans := [ [ -13, 10 ], [ 4, -3 ] ], normal := [ [ 1, 0 ], [ 0, 2 ] ] )Previous Up Next

Index

gap3-jm

24 Apr 2021