24 Integral matrices and lattices

  • IntegralizedMat( A ) F
  • IntegralizedMat( A, inforec ) F

    Sections

    1. Normal Forms over the Integers
    2. Decompositions
    3. Lattice Reduction
    4. Orthogonal Embeddings

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

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

    24.2 Decompositions

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

    24.3 Lattice Reduction

  • 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 LLL82Poh87). 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 ] )
    

    24.4 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 );
    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);
    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
    July 1999