[Top] [Up] [Previous] [Next] [Index]

# 25 Integral matrices and lattices

### Sections

1. Linear equations over the integers and Integral Matrices
2. Normal Forms over the Integers
3. Determinant of an integer matrix
4. Decompositions
5. Lattice Reduction
6. Orthogonal Embeddings

## 25.1 Linear equations over the integers and Integral Matrices

- `NullspaceIntMat(` mat`) A`

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

- `SolutionIntMat(` mat`,` vec`) O`

  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 ]

- `SolutionNullspaceIntMat(` mat`,` vec`) O`

  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`) A`

  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`) A`

  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`) A`

  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. I.e., if the dimension of S is n it determines a basis B={b1,…,bm} for M, as well as n integers xi such that the n vectors si:=xi·bi} form a basis for S.

  It returns a record with the following components:

  `complement`
    the vectors bn+1 up to bm (they generate a complement to S).

  `sub`
    the vectors si (a basis for S).

  `moduli`
    the factors xi.

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

  ## 25.2 Normal Forms over the Integers

- `TriangulizedIntegerMat(` mat`) O`

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

- `TriangulizedIntegerMatTransform(` mat`) O`

  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.

- `TriangulizeIntegerMat(` mat`) O`

  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.) 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 ] ],
        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
      gap> TriangulizeIntegerMat(m); m;
      [ [ 1, 15, 28 ], [ 0, 1, 1 ], [ 0, 0, 3 ] ]

  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.

- `HermiteNormalFormIntegerMat(` mat`) O`

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

- `HermiteNormalFormIntegerMatTransform(` mat`) O`

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

  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·

- `SmithNormalFormIntegerMat(` mat`) O`

  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.

- `SmithNormalFormIntegerMatTransforms(` mat`) O`

  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 PAQ=S.

- `DiagonalizeIntMat(` mat`) O`

  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.) 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( 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
      gap> DiagonalizeIntMat(m);m;
      [ [ 1, 0, 0 ], [ 0, 1, 0 ], [ 0, 0, 3 ] ]

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

- `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.

  16
    Destructive (the original matrix may be destroyed)

  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.

  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:=[[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`) A`

  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 ]

  ## 25.3 Determinant of an integer matrix

- `DeterminantIntMat(` mat`) O`

  Computes the determinant of an integer matrix using the same strategy as `NormalFormIntMat` (see 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.

  ## 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 [(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

  xi = (bi A′) mod p, bi+1 =

  1

  p

  (bi − xi A), i = 0, 1, 2, ….

  By induction, we get

  pi+1 bi+1 + |   | i ∑ j=0 | pj xj |   | A = b.

  If there is an integral solution x then it is unique, and there is an index l such that bl+1 is zero and x = ∑j=0l pj xj.

  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.

  ## 25.5 Lattice Reduction

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

  ## 25.6 Orthogonal Embeddings

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

  Xtr ·X = gram

  are calculated (see Ple90). Usually there are many solutions X but all their rows are chosen from a small set of vectors, so `OrthogonalEmbeddings` returns the solutions in an encoded form, namely as a record with components

  `vectors`
    the list L = [ x1, x2, …, xn ] of vectors that may be rows of a solution; these are exactly those vectors that fulfill the condition xi ·gram −1 ·xitr ≤ 1 (see ShortestVectors), and we have gram = ∑ni=1 xitr ·xi,

  `norms`
    the list of values xi ·gram −1 ·xitr, and

  `solutions`
    a list S of lists; the i-th solution matrix is ``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 );; 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`
    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);; 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
  August 2005