IntegralizedMat(
A ) F
IntegralizedMat(
A,
inforec ) F
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..]
.
It is based upon ideas by George Havas and code by Bohdan Majewski. G. Havas and B. Majewski, Integer Matrix Diagonalization, JSC.
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 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:
1 - Row transformations.
2 - Inverse row transformations.
4 - Column transformations.
8 - Inverse column transformations.
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 form. Caveat - No testing is done to ensure that mat is in REF.
HNFNormDriven(
mat[,
trans[,
reduction]] ) O
HNFChouCollins(
mat[,
trans[,
reduction]] ) O
HNFLLLDriven(
mat[,
trans[,
reduction]] ) O
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û If r 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
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
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û If it 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:
0/1 - Triangular Form / Smith Normal Form.
2 - Reduce off diagonal entries.
4 - Row Transformations.
8 - Col Transformations.
Compute a Triangular, Hermite or Smith form of the n x m integer input matrix A. Optionally, compute n x n / m x m unimodular transforming matrices Q,P which satisfy QA = H or QAP = S. The routines used are based on work by Arne Storjohahn and were implemented in GAP4 by A. Storjohahn 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 ] ]
DecompositionInt(
A,
B,
depth ) F
returns the decomposition matrix X with X
*
A =
B,
for A and B integral matrices.
If A is not square, it must have full rank, and Length( A ) £ Length( A [1] ).
For an odd prime p, each integer x has a unique representation x = åi = 0n xi pi where |xi| £ [(p-1)/2] . Let x be a solution of the equation xA = b where A is a square integral matrix and b an integral vector, [`(A)] = A mod p and [`(b)] = b mod p; then [`(x)][`(A)] º [`(b)] mod p for [`(x)] = x mod p. Assume [`(A)] is regular over the field with p elements; then [`(x)] is uniquely determined mod p. Define x¢ = [(x -[`(x)])/(p)] and b¢ = [(b -[`(x)] A )/(p)]. If y is a solution of the equation x¢ A = b¢ we have ([`(x)] + p y ) A = b and thus x = [`(x)] + p y is the solution of our problem. Note that the process must terminate if an integral solution x exists, since the p--adic series for y has one term less than that for x.
Decomposition(
A,
B,
depth ) F
Decomposition(
A,
B, "nonnegative" ) F
For a matrix A of cyclotomics and a list B of cyclotomic vectors,
Decomposition
tries to find integral solutions of the linear equation
systems x
*
A =
B[i]
.
A must have full rank, i.e., there must be a linear independent set of columns of same length as A.
Decomposition(
A,
B,
depth )
, where depth is a nonnegative
integer, computes for every B
[i]
the initial part
åk = 0depth xk pk (all xk integer vectors with entries
bounded by ±[(p-1)/2]) of the p-adic series of a hypothetical
solution. 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] = false
.
Decomposition(
A,
B, "nonnegative" )
assumes that the solutions
have only nonnegative entries.
This is, e.g., satisfied for the decomposition of ordinary characters into
Brauer characters.
If the first column of A consists of positive integers,
the necessary number depth of iterations can be computed. In that case
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.
LLLReducedBasis( [
L, ]
vectors[,
y][, "linearcomb"][,
lllout] ) F
LLLReducedBasis
provides an implementation of the LLL algorithm by
Lenstra, Lenstra and Lovaccent19 asz (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" ); 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 Lovaccent19 asz (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 ); 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
L
S[
i]
,
so the dimension of the i--th solution is the length of
S[
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 ); 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); 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] [Previous] [Up] [Next] [Index]
GAP 4 manual