Goto Chapter: Top 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 Bib Ind
 [Top of Book]  [Contents]   [Previous Chapter]   [Next Chapter] 

25 Integral matrices and lattices
 25.1 Linear equations over the integers and Integral Matrices
 25.2 Normal Forms over the Integers
 25.3 Determinant of an integer matrix
 25.4 Decompositions
 25.5 Lattice Reduction
 25.6 Orthogonal Embeddings

25 Integral matrices and lattices

25.1 Linear equations over the integers and Integral Matrices

25.1-1 NullspaceIntMat
‣ NullspaceIntMat( mat )( attribute )

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);
[ [ -7/4, 9/2, -15/4, 1, 0 ], [ -3/4, -3/2, 1/4, 0, 1 ] ]
gap> NullspaceIntMat(mat);
[ [ 1, 18, -9, 2, -6 ], [ 0, 24, -13, 3, -7 ] ]

25.1-2 SolutionIntMat
‣ SolutionIntMat( mat, vec )( operation )

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 \(x\) * mat = vec. It returns fail 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 ]

25.1-3 SolutionNullspaceIntMat
‣ SolutionNullspaceIntMat( mat, vec )( operation )

This function returns a list of length two, its first entry being the result of a call to SolutionIntMat (25.1-2) with same arguments, the second the result of NullspaceIntMat (25.1-1) 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 ] ] ]

25.1-4 BaseIntMat
‣ BaseIntMat( mat )( attribute )

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 ] ]

25.1-5 BaseIntersectionIntMats
‣ BaseIntersectionIntMats( m, n )( operation )

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 ] ]

25.1-6 ComplementIntMat
‣ ComplementIntMat( full, sub )( operation )

Let full be a list of integer vectors generating an integral row module \(M\) and sub a list of vectors defining a submodule \(S\) of \(M\). This function computes a free basis for \(M\) that extends \(S\). I.e., if the dimension of \(S\) is \(n\) it determines a basis \(B = \{ b_1, \ldots, b_m \}\) for \(M\), as well as \(n\) integers \(x_i\) such that the \(n\) vectors \(s_i:= x_i \cdot b_i\) form a basis for \(S\).

It returns a record with the following components:

complement

the vectors \(b_{{n+1}}\) up to \(b_m\) (they generate a complement to \(S\)).

sub

the vectors \(s_i\) (a basis for \(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 ] ], moduli := [ 1, 3 ],
  sub := [ [ 1, 2, 3 ], [ 0, 3, 6 ] ] )

25.2 Normal Forms over the Integers

This section describes the computation of the Hermite and Smith normal form of integer matrices.

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 \(Q A = H\).

The Smith Normal Form \(S\) of an integer matrix \(A\) is the unique equivalent diagonal form with \(S_i\) dividing \(S_j\) for \(i < j\). There exist unimodular integer matrices \(P, Q\) such that \(P A Q = S\).

All routines described in this section build on the workhorse routine NormalFormIntMat (25.2-9).

25.2-1 TriangulizedIntegerMat
‣ TriangulizedIntegerMat( mat )( operation )

Computes an upper triangular form of a matrix with integer entries. It returns a mutable matrix in upper triangular form.

25.2-2 TriangulizedIntegerMatTransform
‣ TriangulizedIntegerMatTransform( mat )( operation )

Computes an upper triangular form of a matrix with integer entries. It returns a record with a component normal (an immutable 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.

25.2-3 TriangulizeIntegerMat
‣ TriangulizeIntegerMat( mat )( operation )

Changes mat to be in upper triangular form. (The result is the same as that of TriangulizedIntegerMat (25.2-1), but mat will be modified, thus using less memory.) If mat is immutable an error will be triggered.

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

25.2-4 HermiteNormalFormIntegerMat
‣ HermiteNormalFormIntegerMat( mat )( operation )

This operation computes the Hermite normal form of a matrix mat with integer entries. It returns a immutable matrix in HNF.

25.2-5 HermiteNormalFormIntegerMatTransform
‣ HermiteNormalFormIntegerMatTransform( mat )( operation )

This operation computes the Hermite normal form of a matrix mat with integer entries. It returns a record with components normal (a matrix \(H\)) and rowtrans (a matrix \(Q\)) such that \(Q A = H\).

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

25.2-6 SmithNormalFormIntegerMat
‣ SmithNormalFormIntegerMat( mat )( operation )

This operation computes the Smith normal form of a matrix mat with integer entries. It returns a new immutable matrix in the Smith normal form.

25.2-7 SmithNormalFormIntegerMatTransforms
‣ SmithNormalFormIntegerMatTransforms( mat )( operation )

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 A Q = S\).

25.2-8 DiagonalizeIntMat
‣ DiagonalizeIntMat( mat )( function )

This function changes mat to its SNF. (The result is the same as that of SmithNormalFormIntegerMat (25.2-6), but mat will be modified, thus using less memory.) If mat is immutable an error will be triggered.

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

25.2-9 NormalFormIntMat
‣ NormalFormIntMat( mat, options )( function )

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.

16

Destructive (the original matrix may be destroyed)

Compute a Triangular, Hermite or Smith form of the \(n \times m\) integer input matrix \(A\). Optionally, compute \(n \times n\) and \(m \times m\) unimodular transforming matrices \(Q, P\) which satisfy \(Q A = H\) or \(Q A P = S\).

Note option is a value ranging from 0 to 15 but not all options make sense (e.g., 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:=[[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 ] ], rank := 3,
  rowC := [ [ 1, 0, 0 ], [ 0, 1, 0 ], [ 0, 0, 1 ] ],
  rowQ := [ [ -2, 62, -35 ], [ 1, -30, 17 ], [ -3, 97, -55 ] ],
  rowtrans := [ [ -2, 62, -35 ], [ 1, -30, 17 ], [ -3, 97, -55 ] ],
  signdet := 1 )
gap> NormalFormIntMat(m,13); # Smith Normal Form with both transforms
rec( colC := [ [ 1, 0, 0 ], [ 0, 1, 0 ], [ 0, 0, 1 ] ],
  colQ := [ [ 1, 0, -1 ], [ 0, 1, -1 ], [ 0, 0, 1 ] ],
  coltrans := [ [ 1, 0, -1 ], [ 0, 1, -1 ], [ 0, 0, 1 ] ],
  normal := [ [ 1, 0, 0 ], [ 0, 1, 0 ], [ 0, 0, 3 ] ], rank := 3,
  rowC := [ [ 1, 0, 0 ], [ 0, 1, 0 ], [ 0, 0, 1 ] ],
  rowQ := [ [ -2, 62, -35 ], [ 1, -30, 17 ], [ -3, 97, -55 ] ],
  rowtrans := [ [ -2, 62, -35 ], [ 1, -30, 17 ], [ -3, 97, -55 ] ],
  signdet := 1 )
gap> last.rowtrans*m*last.coltrans;
[ [ 1, 0, 0 ], [ 0, 1, 0 ], [ 0, 0, 3 ] ]

25.2-10 AbelianInvariantsOfList
‣ AbelianInvariantsOfList( list )( attribute )

Given a list of nonnegative integers, this routine returns a sorted list containing the prime power factors of the positive entries in the original list, as well as all zeroes of the original list.

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

25.3 Determinant of an integer matrix

25.3-1 DeterminantIntMat
‣ DeterminantIntMat( mat )( function )

Computes the determinant of an integer matrix using the same strategy as NormalFormIntMat (25.2-9). This method is faster in general for matrices greater than \(20 \times 20\) but quite a lot slower for smaller matrices. It therefore passes the work to the more general DeterminantMat (24.4-4) for these smaller matrices.

25.4 Decompositions

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 \(\overline{A}\), its entries are chosen in the interval \([ -(p-1)/2, (p-1)/2 ]\). If \(\overline{A}\) is regular over the field with \(p\) elements, we can form \(A' = \overline{A}^{{-1}}\). Now we consider the integral linear equation system \(x A = b\), i.e., we look for an integral solution \(x\). Define \(b_0 = b\), and then iteratively compute

\[ x_i = (b_i A') \bmod p, b_{{i+1}} = (b_i - x_i A) / p, i = 0, 1, 2, \ldots . \]

By induction, we get

\[ p^{{i+1}} b_{{i+1}} + \left( \sum_{{j = 0}}^i p^j x_j \right) A = b. \]

If there is an integral solution \(x\) then it is unique, and there is an index \(l\) such that \(b_{{l+1}}\) is zero and \(x = \sum_{{j = 0}}^l p^j x_j\).

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 (24.15-1)).

25.4-1 Decomposition
‣ Decomposition( A, B, depth )( operation )

For a \(m \times n\) matrix A of cyclotomics that has rank \(m \leq 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 \(\sum_{{k = 0}}^{\textit{depth}} x_k p^k\), with all \(x_k\) vectors of integers with entries bounded by \(\pm (p-1)/2\). The prime \(p\) is set to 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.

If depth is not an integer then it must be the string "nonnegative". 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.

25.4-2 LinearIndependentColumns
‣ LinearIndependentColumns( mat )( function )

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.

25.4-3 PadicCoefficients
‣ PadicCoefficients( A, Amodpinv, b, prime, depth )( function )

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 \([ x_0, x_1, \ldots, x_l, b_{{l+1}} ]\) describing the prime-adic approximation of b (see above), where \(l = \textit{depth}\) or \(l\) is minimal with the property that \(b_{{l+1}} = 0\).

25.4-4 IntegralizedMat
‣ IntegralizedMat( A[, inforec] )( function )

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.

25.4-5 DecompositionInt
‣ DecompositionInt( A, B, depth )( function )

DecompositionInt does the same as Decomposition (25.4-1), except that A and B must be integral matrices, and depth must be a nonnegative integer.

25.5 Lattice Reduction

25.5-1 LLLReducedBasis
‣ LLLReducedBasis( [L, ]vectors[, y][, "linearcomb"][, lllout] )( function )

provides an implementation of the LLL algorithm by Lenstra, Lenstra and Lovász (see [LLJL82], [Poh87]). The implementation follows the description in [Coh93, p. 94f.].

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 (25.5-2) 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( B := [ 5, 36/5, 12, 50/3 ],
  basis := [ [ 1, 1, 1, 1, 1 ], [ 1, 1, -2, 1, 1 ],
      [ -1, 3, -1, -1, -1 ], [ -3, 1, 0, 2, 2 ] ],
  mue := [ [  ], [ 2/5 ], [ -1/5, 1/3 ], [ 2/5, 1/6, 1/6 ] ],
  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 ] ] )

25.5-2 LLLReducedGramMat
‣ LLLReducedGramMat( G[, y] )( function )

LLLReducedGramMat provides an implementation of the LLL algorithm by Lenstra, Lenstra and Lovász (see [LLJL82][Poh87]). The implementation follows the description in [Coh93, p. 94f.].

Let G the Gram matrix of the vectors \((b_1, b_2, \ldots, b_n)\); 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 \((b_1, b_2, \ldots, b_n)\). 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 \((x_1, x_2, \ldots, x_n)\) such that \(\sum_{{i = 1}}^n x_i b_i\) 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 \cdot \textit{G} \cdot T^{tr}\) 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 \(\textit{y} = 3/4\).

The function LLLReducedBasis (25.5-1) 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( B := [ 4, 4, 75/16, 168/25, 32/7 ],
  mue := [ [  ], [ 1/2 ], [ 1/4, -1/8 ], [ 1/2, 1/4, -2/25 ],
      [ -1/4, 1/8, 37/75, 8/21 ] ], relations := [  ],
  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 ] ],
  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 ] ] )

25.6 Orthogonal Embeddings

25.6-1 OrthogonalEmbeddings
‣ OrthogonalEmbeddings( gram[, "positive"][, maxdim] )( function )

computes all possible orthogonal embeddings of a lattice given by its Gram matrix gram, which must be a regular symmetric matrix of integers. In other words, all integral solutions \(X\) of the equation \(X^{tr} \cdot X = \)gram are calculated. The implementation follows the description in [Ple95].

Usually there are many solutions \(X\) but all their rows belong to a small set of vectors, so OrthogonalEmbeddings returns the solutions encoded by a record with the following components.

vectors

the list \(L = [ x_1, x_2, \ldots, x_n ]\) of vectors that may be rows of a solution, up to sign; these are exactly the vectors with the property \(x_i \cdot \)gram\(^{{-1}} \cdot x_i^{tr} \leq 1\), see ShortestVectors (25.6-2),

norms

the list of values \(x_i \cdot \)gram\(^{{-1}} \cdot x_i^{tr}\), and

solutions

a list \(S\) of index lists; the \(i\)-th solution matrix is \(L\){ \(S[i]\) }, so the dimension of the i-th solution is the length of \(S[i]\), and we have gram\( = \sum_{{j \in S[i]}} x_j^{tr} \cdot x_j\),

The optional argument "positive" will cause OrthogonalEmbeddings to compute only vectors \(x_i\) 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 may accelerate the algorithm.

gap> b:= [ [ 3, -1, -1 ], [ -1, 3, -1 ], [ -1, -1, 3 ] ];;
gap> c:=OrthogonalEmbeddings( b );
rec( 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 ] ],
  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 ] ] )
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 (72.10-7) may be able to compute irreducibles.

25.6-2 ShortestVectors
‣ ShortestVectors( G, m[, "positive"] )( function )

Let G be a regular matrix of a symmetric bilinear form, and m a nonnegative integer. ShortestVectors computes the vectors \(x\) that satisfy \(x \cdot \textit{G} \cdot x^{tr} \leq \textit{m}\), and returns a record describing these vectors. The result record has the components

vectors

list of the nonzero vectors \(x\), but only one of each pair \((x,-x)\),

norms

list of norms of the vectors according to the Gram matrix G.

If the optional argument "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( norms := [ 4, 2, 2, 4, 2, 4, 2, 2, 2 ],
  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 ] ] )
 [Top of Book]  [Contents]   [Previous Chapter]   [Next Chapter] 
Goto Chapter: Top 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 Bib Ind

generated by GAPDoc2HTML