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, ..., b_m } for M, as well as n integers x_i such that the n vectors s_i:= x_i ⋅ 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 immutable 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 × m integer input matrix A. Optionally, compute n × n and m × 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 × 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 overlineA, its entries are chosen in the interval [ -(p-1)/2, (p-1)/2 ]. If overlineA is regular over the field with p elements, we can form A' = overlineA^{-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') mod p, b_{i+1} = (b_i - x_i A) / p, i = 0, 1, 2, ... .

By induction, we get

p^{i+1} b_{i+1} + ( ∑_{j = 0}^i p^j x_j ) 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 = ∑_{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 × 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

, 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 ∑_{k = 0}^`B`[i]`depth` x_k p^k, with all x_k vectors of integers with entries bounded by ± (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

, 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, ..., x_l, b_{l+1} ] describing the `prime`-adic approximation of `b` (see above), where l = `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 [LLL82], [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 [LLL82], [Poh87]). The implementation follows the description in [Coh93, p. 94f.].

Let `G` the Gram matrix of the vectors (b_1, b_2, ..., 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, ..., 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, ..., x_n) such that ∑_{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 ⋅ `G` ⋅ 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 `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 ⋅ 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, ..., x_n ] of vectors that may be rows of a solution, up to sign; these are exactly the vectors with the property x_i ⋅

`gram`^{-1} ⋅ x_i^tr ≤ 1, see`ShortestVectors`

(25.6-2),`norms`

the list of values x_i ⋅

`gram`^{-1} ⋅ 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`= ∑_{j ∈ S[i]} x_j^tr ⋅ 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 ⋅ `G` ⋅ x^tr ≤ `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 ] ] )

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