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

25 Integral matrices and lattices

25.2 Normal Forms over the Integers

25.2-1 TriangulizedIntegerMat

25.2-2 TriangulizedIntegerMatTransform

25.2-3 TriangulizeIntegerMat

25.2-4 HermiteNormalFormIntegerMat

25.2-5 HermiteNormalFormIntegerMatTransform

25.2-6 SmithNormalFormIntegerMat

25.2-7 SmithNormalFormIntegerMatTransforms

25.2-8 DiagonalizeIntMat

25.2-9 NormalFormIntMat

25.2-10 AbelianInvariantsOfList

25.2-1 TriangulizedIntegerMat

25.2-2 TriangulizedIntegerMatTransform

25.2-3 TriangulizeIntegerMat

25.2-4 HermiteNormalFormIntegerMat

25.2-5 HermiteNormalFormIntegerMatTransform

25.2-6 SmithNormalFormIntegerMat

25.2-7 SmithNormalFormIntegerMatTransforms

25.2-8 DiagonalizeIntMat

25.2-9 NormalFormIntMat

25.2-10 AbelianInvariantsOfList

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

`‣ 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\) `* `

. It returns `mat` = `vec``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 ) | ( 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 ] ] ]

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

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

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

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

`‣ TriangulizedIntegerMat` ( mat ) | ( operation ) |

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

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

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

`‣ HermiteNormalFormIntegerMat` ( mat ) | ( operation ) |

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

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

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

`‣ 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\).

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

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

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

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

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

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

, by computing the \(p\)-adic series of hypothetical solutions.`x` * `A` = `B`[i]

`Decomposition( `

, where `A`, `B`, `depth` )`depth` is a nonnegative integer, computes for each vector

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 `B`[i]`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

, otherwise `X`[i] = `x`

.`X`[i] = fail

If `depth` is not an integer then it must be the string `"nonnegative"`

. `Decomposition( `

assumes that the solutions have only nonnegative entries, and that the first column of `A`, `B`, "nonnegative" )`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

, and it is the solution otherwise.`x` * `A` = `B`[i]

*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 ) | ( 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`.

`‣ 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\).

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

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

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

. If no lattice is specified then the scalar product of vectors given by `L`, `v`, `w` )`ScalarProduct( `

is used.`v`, `w` )

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

is zero. `x` * `vectors``transformation`

gives the expression of the new lattice basis in terms of the old, i.e., `transformation * `

equals the `vectors``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

and `lllout`.mue

contain their scalar products and norms used internally in the algorithm, which are also present in the output of `lllout`.B`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 ] ] )

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

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

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

generated by GAPDoc2HTML