% This file was created automatically from matint.msk. % DO NOT EDIT! %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %% %A matint.msk GAP documentation Alexander Hulpke %A Thomas Breuer %A Rob Wainwright %% %A @(#)$Id: matint.msk,v 1.18.2.1 2004/01/19 10:01:15 gap Exp $ %% %Y (C) 1998 School Math and Comp. Sci., University of St. Andrews, Scotland %Y Copyright (C) 2002 The GAP Group %% \Chapter{Integral matrices and lattices} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{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. \beginexample 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 ] ] \endexample \>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. \beginexample 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 ] \endexample \>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. \beginexample 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 ] ] ] \endexample \>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>. \beginexample gap> mat:=[[1,2,7],[4,5,6],[10,11,19]];; gap> BaseIntMat(mat); [ [ 1, 2, 7 ], [ 0, 3, 7 ], [ 0, 0, 15 ] ] \endexample \>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>. \beginexample 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 ] ] \endexample \>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=\{\underline{b}_1,\ldots,\underline{b}_m\}$ for <M>, as well as <n> integers $x_i$ such that the <n> vectors $\underline{s}_i:=x_i\cdot \underline{b}_i\}$ form a basis for <S>. It returns a record with the following components: \beginitems `complement' & the vectors $\underline{b}_{n+1}$ up to $\underline{b}_m$ (they generate a complement to <S>). `sub' & the vectors $s_i$ (a basis for <S>). `moduli' & the factors $x_i$. \enditems \beginexample 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 ] ) \endexample %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{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. \beginexample 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 ] ] \endexample 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$ \beginexample 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 \endexample 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 $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. \beginexample 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 ] ] \endexample 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: \beginlist \item{0/1} Triangular Form / Smith Normal Form. \item{2} Reduce off diagonal entries. \item{4} Row Transformations. \item{8} Col Transformations. \item{16} Destructive (the original matrix may be destroyed) \endlist 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 $QA = H$ or $QAP = S$. %The routines used are based on work by Arne Storjohann %and were implemented in {\GAP}~4 by A.~Storjohann 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. \beginexample 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 ] ] \endexample \>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. \beginexample gap> AbelianInvariantsOfList([4,6,2,12]); [ 2, 2, 3, 3, 4, 4 ] \endexample %\ Declaration{DiagonalizeIntMatNormDriven} %\ Declaration{SNFNormDriven} %\ Declaration{SNFofREF} %\ Declaration{HNFNormDriven} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{Determinant of an integer matrix} \index{determinant!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 \times 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. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{Decompositions} \index{decomposition matrix} \atindex{DEC}{@DEC} 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 $[-\frac{p-1}{2}, \frac{p-1}{2}]$. If $\overline{A}$ is regular over the field with $p$ elements, we can form $A^{\prime} = \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^{\prime}) \bmod p,\ \ b_{i+1} = \frac{1}{p} (b_i - x_i A), 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"). \>Decomposition( <A>, <B>, <depth> ) F \>Decomposition( <A>, <B>, \"nonnegative\" ) F 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}^{<depth>} x_k p^k$, with all $x_k$ vectors of integers with entries bounded by $\pm\frac{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 $[ x_0, x_1, \ldots, 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> ) 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. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{Lattice Reduction} \atindex{LLL algorithm!for vectors}{@LLL algorithm!for vectors} \index{short vectors spanning a lattice} \index{lattice base reduction} \>LLLReducedBasis( [<L>, ]<vectors>[, <y>][, \"linearcomb\"][, <lllout>] ) F provides an implementation of the LLL algorithm by Lenstra, Lenstra and Lov{\accent19 a}sz (see~\cite{LLL82}, \cite{Poh87}). The implementation follows the description on pages 94f. in~\cite{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 $\frac{1}{4}$ and $1$ (the default value is $\frac{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. \beginexample 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 ] ) \endexample \atindex{LLL algorithm!for Gram matrices}{@LLL algorithm!for Gram matrices} \index{lattice base reduction} \>LLLReducedGramMat( <G> ) F \>LLLReducedGramMat( <G>, <y> ) F `LLLReducedGramMat' provides an implementation of the LLL algorithm by Lenstra, Lenstra and Lov{\accent19 a}sz (see~\cite{LLL82},~\cite{Poh87}). The implementation follows the description on pages 94f. in~\cite{Coh93}. 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 . <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 $\frac{1}{4}$ and $1$; the default value is $<y> = \frac{3}{4}$. The function `LLLReducedBasis' (see~"LLLReducedBasis") computes an LLL reduced basis. \beginexample 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 ] ) \endexample %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{Orthogonal Embeddings}\nolabel \>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 $$ X^{tr} . X = <gram> $$ are calculated (see~\cite{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 \beginitems `vectors' & the list $L = [ x_1, x_2, \ldots, x_n ]$ of vectors that may be rows of a solution; these are exactly those vectors that fulfill the condition $x_i . <gram>^{-1} . x_i^{tr} \leq 1$ (see~"ShortestVectors"), and we have $<gram> = \sum^n_{i=1} x_i^{tr} . x_i$, `norms' & the list of values $x_i . <gram>^{-1} . x_i^{tr}$, 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>]'. \enditems 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 will accelerate the algorithm in some cases. \beginexample 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 ] ] \endexample <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> . x^{tr} \leq <m>$, and returns a record describing these vectors. The result record has the components \beginitems `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>. \enditems If the optional argument `\"positive\"' is entered, only those vectors $x$ with nonnegative entries are computed. \beginexample 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 ] ) \endexample %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %% %E