25.1 Normal Forms over the Integers
DiagonalizeIntMatNormDriven( mat ) F
DiagonalizeIntMatNormDriven diagonalizes the integer matrix mat.
It tries to keep the entries small through careful selection of pivots.
First it selects a nonzero entry for which the product of row and column norm is minimal (this need not be the entry with minimal absolute value). Then it brings this pivot to the upper left corner and makes it positive.
Next it subtracts multiples of the first row from the other rows, so that the new entries in the first column have absolute value at most pivot/2. Likewise it subtracts multiples of the 1st column from the other columns.
If afterwards not all new entries in the first column and row are zero, then it selects a new pivot from those entries (again driven by product of norms) and reduces the first column and row again.
If finally all offdiagonal entries in the first column and row are zero,
then it starts all over again with the submatrix mat[2..][2..].
The original idea is explained in HM97.
gap> m:=[[14,20],[6,9]];; gap> DiagonalizeIntMatNormDriven(m); gap> m; [ [ 2, 0 ], [ 0, 3 ] ]
SNFNormDriven( mat[, trans] ) O
SNFChouCollins( mat[, trans] ) O
SNFLLLDriven( mat[, trans] ) O
These operations have been superceded for most purposes by
NormalFormIntMat (see NormalFormIntMat) which should in most cases
be faster than any
of them, and produce smaller transforming matrix entries.
These operations compute the Smith normal form of a matrix with integer entries, using the strategy specified in the name. If no optional argument trans is given mat must be a mutable matrix which will be changed by the algorithm.
If the optional integer argument trans is given, it determines which transformation matrices will be computed. It is interpreted binary as:
The operation then returns a record with the component normal containing
the computed normal form and optional components rowtrans, rowinverse,
coltrans, and invcoltrans which hold the computed transformation
matrices. Note, if trans is given the operation does not change mat.
This functionality is still to be fully implemented for SNF with transforms.
However, NormalFormIntMat performs this calculation.
SNFofREF( mat ) O
Computes the Smith Normal Form of an integer matrix in row echelon (RE) form. Caveat -- No testing is done to ensure that mat is in RE form.
HNFNormDriven( mat[, trans[, reduction]] ) O
HNFChouCollins( mat[, trans[, reduction]] ) O
HNFLLLDriven( mat[, trans[, reduction]] ) O
These operations have been superceded for most purposes by
NormalFormIntMat (see NormalFormIntMat)
which should in most cases be faster than any
of them, and produce smaller transforming matrix entries.
These operations compute the Hermite normal form of a matrix with integer entries, using the strategy specified in the name. If no optional argument trans is given mat must be a mutable matrix which will be changed by the algorithm.
If the optional integer argument trans is given, it determines which transformation matrices will be computed. It is interpreted binary as for the Smith normal form (see SNFNormDriven) but note that only row operations are performed. The function then returns a record with components as specified for the Smith normal form.
If the further optional argument reduction (a rational in the range
[0..1])
is given, it specifies which representatives
are used for entries modulo c when cleaning column entries to the top.
Off-diagonal entries are reduced to the range
ëc(r-1)û¼ëcrû,
where r is the value of reduction.
If reduction is not given, a value of 1 is assumed.
Note, if trans is given the operation does not change mat.
gap> m:=[ [ 14, 20 ], [ 6, 9 ] ];; gap> HNFNormDriven(m); [ [ 2, 2 ], [ 0, 3 ] ] gap> m; [ [ 2, 2 ], [ 0, 3 ] ]
gap> m:=[[14,20],[6,9]];; gap> HNFNormDriven(m,1); rec( normal := [ [ 2, 2 ], [ 0, 3 ] ], rowtrans := [ [ 1, -2 ], [ -3, 7 ] ] ) gap> m; [ [ 14, 20 ], [ 6, 9 ] ] gap> last2.rowtrans*m; [ [ 2, 2 ], [ 0, 3 ] ]
TriangulizeIntegerMat( mat[, trans] ) O
Computes an upper triangular form of a matrix with integer entries. If no optional argument trans is given mat must be a mutable matrix which will be changed by the algorithm.
If the optional integer argument trans is given, it determines which transformation matrices will be computed. It is interpreted binary as for the Smith normal form (see SNFNormDriven) but note that only row operations are performed. The function then returns a record with components as specified for the Smith normal form. Note, if trans is given the operation does not change mat.
SmithNormalFormIntegerMat( mat ) O
SmithNormalFormIntegerMatTransforms( mat ) O
SmithNormalFormIntegerMatInverseTransforms( mat ) O
The Smith Normal Form,S, of an integer matrix A is the unique equivalent diagonal form with Si dividing Sj for i < j. There exist unimodular integer matrices P, Q such that PAQ = S·
These operations compute the Smith normal form of a matrix mat with
integer entries. The operations will try to select a suitable strategy.
The first operation returns a new immutable matrix in the Smith normal
form. The other operations also compute matrices for the row and
column transformations or inverses thereof respectively.
They return a record with the component normal containing the
computed normal form and optional components rowtrans and coltrans, or
invrowtrans and invcoltrans which hold the computed transformation
matrices.
gap> m:=[[14,20],[6,9]]; [ [ 14, 20 ], [ 6, 9 ] ] gap> SmithNormalFormIntegerMat(m); [ [ 1, 0 ], [ 0, 6 ] ]
HermiteNormalFormIntegerMat( mat[, reduction] ) O
HermiteNormalFormIntegerMatTransforms( mat[, reduction] ) O
HermiteNormalFormIntegerMatInverseTransforms( mat[, reduction] ) O
The Hermite Normal Form, 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.
These operations compute the Hermite normal form of a matrix mat with integer entries. The operations will try to select a suitable strategy. The first operation returns a immutable matrix which is the Hermite normal form of mat.
The other two operations also compute matrices for the row
transformations or inverses respectively.
They return a record with the component normal containing the
computed normal form and optional components rowtrans or 'invrowtrans'
which hold the computed transformation matrix.
If the optional argument reduction (a rational in the range [0..1])
is given, it specifies which representatives are used for entries modulo c
when cleaning column entries to the top.
Off-diagonal entries are reduced to the range
ëc(r-1)û¼ëcrû
where r is the value of reduction.
If reduction is not given, a value of 1 is assumed.
gap> m; [ [ 14, 20 ], [ 6, 9 ] ] gap> HermiteNormalFormIntegerMat(m); [ [ 2, 2 ], [ 0, 3 ] ] gap> HermiteNormalFormIntegerMatTransforms(m); rec( normal := [ [ 2, 2 ], [ 0, 3 ] ], rowtrans := [ [ 1, -2 ], [ -3, 7 ] ] )
TriangulizedIntegerMat( mat[, trans] ) O
TriangulizedIntegerMatTransform( mat[, trans] ) O
TriangulizedIntegerMatInverseTransform( mat[, trans] ) O
The first operation computes a row equivalent upper triangular form of a matrix mat with integer entries. It returns an immutable matrix in upper triangular form.
The other two operations also compute matrices for the row
transformations or inverses respectively.
They return a record with the component normal containing the
computed normal form and optional components rowtrans or invrowtrans
which hold the computed transformation matrix.
NormalFormIntMat( mat, options ) O
This general operation for computation of various Normal Forms is probably the most efficient.
Options bit values:
Compute a Triangular, Hermite or Smith form of the 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. The routines used are based on work by Arne Storjohann and were implemented in GAP 4 by A. Storjohann and R. Wainwright.
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 normal 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:=[[14,20],[6,9]];; gap> NormalFormIntMat(m,0); # Triangular, no transforms rec( normal := [ [ 2, 2 ], [ 0, 3 ] ], rank := 2, signdet := 1 )
gap> NormalFormIntMat(m,6); # Hermite Normal Form with row transforms rec( normal := [ [ 2, 2 ], [ 0, 3 ] ], rank := 2, signdet := 1, rowtrans := [ [ 1, -2 ], [ -3, 7 ] ] )
gap> NormalFormIntMat(m,13); # Smith Normal Form with both transforming matrices rec( normal := [ [ 1, 0 ], [ 0, 6 ] ], rank := 2, signdet := 1, rowtrans := [ [ -11, 25 ], [ -15, 34 ] ], coltrans := [ [ 1, -5 ], [ 1, -4 ] ] ) gap> last.rowtrans*m*last.coltrans; [ [ 1, 0 ], [ 0, 6 ] ]
For computing the decomposition of a vector of integers into the rows of a matrix of integers, with integral coefficients, one can use p-adic approximations, as follows.
Let A be a square integral matrix, and p an odd prime.
The reduction of A modulo p is [`(A)],
its entries are chosen in the interval
[-[(p-1)/2], [(p-1)/2]].
If [`(A)] is regular over the field with p elements,
we can form A¢ = [`(A)]-1.
Now we consider the integral linear equation system x A = b,
i.e., we look for an integral solution x.
Define b0 = b, and then iteratively compute
|
|
There are two useful generalizations of this idea. First, A need not be square; it is only necessary that there is a square regular matrix formed by a subset of columns of A. Second, A does not need to be integral; the entries may be cyclotomic integers as well, in this case one can replace each column of A by the columns formed by the coefficients w.r.t. an integral basis (which are integers). Note that this preprocessing must be performed compatibly for A and b.
GAP provides the following functions for this purpose (see also InverseMatMod).
Decomposition( A, B, depth ) F
Decomposition( A, B, "nonnegative" ) F
For a m ×n matrix A of cyclotomics that has rank m £ n,
and a list B of cyclotomic vectors, each of length n,
Decomposition tries to find integral solutions of the linear equation
systems x * A = B[i],
by computing the p-adic series of hypothetical solutions.
Decomposition( A, B, depth ), where depth is a nonnegative
integer, computes for each vector B[i] the initial part
åk=0depth xk pk,
with all xk vectors of integers with entries bounded by
±[(p-1)/2].
The prime p is 83 first; if the reduction of A
modulo p is singular, the next prime is chosen automatically.
A list X is returned.
If the computed initial part for x * A = B[i] is a solution,
we have X[i] = x, otherwise X[i] = fail.
Decomposition( A, B, "nonnegative" ) assumes that the solutions
have only nonnegative entries,
and that the first column of A consists of positive integers.
This is satisfied, e.g., for the decomposition of ordinary characters
into Brauer characters.
In this case the necessary number depth of iterations can be computed;
the i-th entry of the returned list is fail if there exists no
nonnegative integral solution of the system x * A = B[i], and it
is the solution otherwise.
Note that the result is a list of fail if A has not full rank,
even if there might be a unique integral solution for some equation
system.
LinearIndependentColumns( mat ) F
Called with a matrix mat, LinearIndependentColumns returns a maximal
list of column positions such that the restriction of mat to these
columns has the same rank as mat.
PadicCoefficients( A, Amodpinv, b, prime, depth ) F
Let A be an integral matrix,
prime a prime integer,
Amodpinv an inverse of A modulo prime,
b an integral vector,
and depth a nonnegative integer.
PadicCoefficients returns the list [ x0, x1, ¼, xl, bl+1 ]
describing the prime-adic approximation of b (see above),
where l = depth
or l is minimal with the property that bl+1 = 0.
IntegralizedMat( A ) F
IntegralizedMat( A, inforec ) F
IntegralizedMat returns for a matrix A of cyclotomics
a record intmat with components mat and inforec.
Each family of algebraic conjugate columns of A is encoded in a set of
columns of the rational matrix intmat.mat by replacing cyclotomics
in A by their coefficients w.r.t. an integral basis.
intmat.inforec is a record containing the information how to encode
the columns.
If the only argument is A, the value of the component inforec is
computed that can be entered as second argument inforec in a later call
of IntegralizedMat with a matrix B that shall be encoded compatibly
with A.
DecompositionInt( A, B, depth ) F
DecompositionInt does the same as Decomposition
(see Decomposition),
except that A and B must be integral matrices, and depth must be
a nonnegative integer.
LLLReducedBasis( [L, ]vectors[, y][, "linearcomb"][, lllout] ) F
provides an implementation of the LLL algorithm by Lenstra, Lenstra and Lovász (see LLL82, Poh87). The implementation follows the description on pages 94f. in Coh93.
LLLReducedBasis returns a record whose component basis is a list of
LLL reduced linearly independent vectors spanning the same lattice as
the list vectors.
L must be a lattice, with scalar product of the vectors v and w
given by ScalarProduct( L, v, w ).
If no lattice is specified then the scalar product of vectors given by
ScalarProduct( v, w ) is used.
In the case of the option "linearcomb", the result record contains
also the components relations and transformation, with the following
meaning.
relations is a basis of the relation space of vectors, i.e., of
vectors x such that x * vectors is zero.
transformation gives the expression of the new lattice basis in
terms of the old, i.e.,
transformation * vectors equals the basis component of the result.
Another optional argument is y, the ``sensitivity'' of the algorithm, a rational number between [ 1/4] and 1 (the default value is [ 3/4]).
The optional argument lllout is a record with the components mue
and B, both lists of length k, with the meaning that
if lllout is present then the first k vectors in vectors form
an LLL reduced basis of the lattice they generate,
and lllout.mue and lllout.B contain their scalar products and
norms used internally in the algorithm, which are also present in the
output of LLLReducedBasis.
So lllout can be used for ``incremental'' calls of LLLReducedBasis.
The function LLLReducedGramMat (see LLLReducedGramMat)
computes an LLL reduced Gram matrix.
gap> vectors:= [ [ 9, 1, 0, -1, -1 ], [ 15, -1, 0, 0, 0 ],
> [ 16, 0, 1, 1, 1 ], [ 20, 0, -1, 0, 0 ],
> [ 25, 1, 1, 0, 0 ] ];;
gap> LLLReducedBasis( vectors, "linearcomb" );; Display( last );
rec(
basis := [ [ 1, 1, 1, 1, 1 ], [ 1, 1, -2, 1, 1 ], [ -1, 3, -1, -1, -1 ],
[ -3, 1, 0, 2, 2 ] ],
relations := [ [ -1, 0, -1, 0, 1 ] ],
transformation :=
[ [ 0, -1, 1, 0, 0 ], [ -1, -2, 0, 2, 0 ], [ 1, -2, 0, 1, 0 ],
[ -1, -2, 1, 1, 0 ] ],
mue := [ [ ], [ 2/5 ], [ -1/5, 1/3 ], [ 2/5, 1/6, 1/6 ] ],
B := [ 5, 36/5, 12, 50/3 ] )
LLLReducedGramMat( G ) F
LLLReducedGramMat( G, y ) F
LLLReducedGramMat provides an implementation of the LLL algorithm by
Lenstra, Lenstra and Lovász (see LLL82, Poh87).
The implementation follows the description on pages 94f. in Coh93.
Let G the Gram matrix of the vectors (b1, b2, ¼, bn); this means G is either a square symmetric matrix or lower triangular matrix (only the entries in the lower triangular half are used by the program).
LLLReducedGramMat returns a record whose component remainder is the
Gram matrix of the LLL reduced basis corresponding to (b1, b2, ¼, bn).
If G is a lower triangular matrix then also the remainder component
of the result record is a lower triangular matrix.
The result record contains also the components relations and
transformation, which have the following meaning.
relations is a basis of the space of vectors (x1,x2,¼,xn)
such that åi=1n xi bi is zero,
and transformation gives the expression of the new lattice basis in
terms of the old, i.e., transformation is the matrix T such that
T ·G ·Ttr is the remainder component of the result.
The optional argument y denotes the ``sensitivity'' of the algorithm, it must be a rational number between [ 1/4] and 1; the default value is y = [ 3/4].
The function LLLReducedBasis (see LLLReducedBasis)
computes an LLL reduced basis.
gap> g:= [ [ 4, 6, 5, 2, 2 ], [ 6, 13, 7, 4, 4 ],
> [ 5, 7, 11, 2, 0 ], [ 2, 4, 2, 8, 4 ], [ 2, 4, 0, 4, 8 ] ];;
gap> LLLReducedGramMat( g );; Display( last );
rec(
remainder := [ [ 4, 2, 1, 2, -1 ], [ 2, 5, 0, 2, 0 ], [ 1, 0, 5, 0, 2 ],
[ 2, 2, 0, 8, 2 ], [ -1, 0, 2, 2, 7 ] ],
relations := [ ],
transformation :=
[ [ 1, 0, 0, 0, 0 ], [ -1, 1, 0, 0, 0 ], [ -1, 0, 1, 0, 0 ],
[ 0, 0, 0, 1, 0 ], [ -2, 0, 1, 0, 1 ] ],
mue := [ [ ], [ 1/2 ], [ 1/4, -1/8 ], [ 1/2, 1/4, -2/25 ],
[ -1/4, 1/8, 37/75, 8/21 ] ],
B := [ 4, 4, 75/16, 168/25, 32/7 ] )
OrthogonalEmbeddings( gram[, "positive"][, maxdim] ) F
computes all possible orthogonal embeddings of a lattice given by its
Gram matrix gram, which must be a regular matrix.
In other words, all solutions X of the problem
|
OrthogonalEmbeddings returns the solutions in an encoded form,
namely as a record with components
vectors
norms
solutions S[i] ,
so the dimension of the i-th solution is the length of
[i].
The optional argument "positive" will cause OrthogonalEmbeddings
to compute only vectors xi with nonnegative entries.
In the context of characters this is allowed (and useful)
if gram is the matrix of scalar products of ordinary characters.
When OrthogonalEmbeddings is called with the optional argument
maxdim (a positive integer),
only solutions up to dimension maxdim are computed;
this will accelerate the algorithm in some cases.
gap> b:= [ [ 3, -1, -1 ], [ -1, 3, -1 ], [ -1, -1, 3 ] ];;
gap> c:=OrthogonalEmbeddings( b );; Display( c );
rec(
vectors := [ [ -1, 1, 1 ], [ 1, -1, 1 ], [ -1, -1, 1 ], [ -1, 1, 0 ],
[ -1, 0, 1 ], [ 1, 0, 0 ], [ 0, -1, 1 ], [ 0, 1, 0 ], [ 0, 0, 1 ] ],
norms := [ 1, 1, 1, 1/2, 1/2, 1/2, 1/2, 1/2, 1/2 ],
solutions := [ [ 1, 2, 3 ], [ 1, 6, 6, 7, 7 ], [ 2, 5, 5, 8, 8 ],
[ 3, 4, 4, 9, 9 ], [ 4, 5, 6, 7, 8, 9 ] ] )
gap> c.vectors{ c.solutions[1] };
[ [ -1, 1, 1 ], [ 1, -1, 1 ], [ -1, -1, 1 ] ]
gram may be the matrix of scalar products of some virtual characters.
From the characters and the embedding given by the matrix X,
Decreased (see Decreased) may be able to compute irreducibles,
see Reducing Virtual Characters.
ShortestVectors( G, m[, "positive"] ) F
Let G be a regular matrix of a symmetric bilinear form,
and m a nonnegative integer.
ShortestVectors computes the vectors x that satisfy
x ·G ·xtr £ m ,
and returns a record describing these vectors.
The result record has the components
vectors
norms "positive" is entered,
only those vectors x with nonnegative entries are computed.
gap> g:= [ [ 2, 1, 1 ], [ 1, 2, 1 ], [ 1, 1, 2 ] ];;
gap> ShortestVectors(g,4);; Display( last );
rec(
vectors := [ [ -1, 1, 1 ], [ 0, 0, 1 ], [ -1, 0, 1 ], [ 1, -1, 1 ],
[ 0, -1, 1 ], [ -1, -1, 1 ], [ 0, 1, 0 ], [ -1, 1, 0 ], [ 1, 0, 0 ] ],
norms := [ 4, 2, 2, 4, 2, 4, 2, 2, 2 ] )
[Top] [Up] [Previous] [Next] [Index]
GAP 4 manual
May 2002