% 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.14 2002/04/15 10:02:30 sal 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{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..]}'.

The original idea is explained in ~\cite{HM97}.

\beginexample
gap> m:=[[14,20],[6,9]];;
gap> DiagonalizeIntMatNormDriven(m);
gap> m;
[ [ 2, 0 ], [ 0, 3 ] ]
\endexample


\>SNFNormDriven( <mat>[, <trans>] ) O
\>SNFChouCollins( <mat>[, <trans>] ) O
\>SNFLLLDriven( <mat>[, <trans>] ) O

These operations have been superceded for most purposes by
`NormalFormIntMat' (see~"NormalFormIntMat") which should in most cases
be faster than any
of them, and produce smaller transforming matrix entries.

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:
\beginlist
\item{1} Row transformations.

\item{2} Inverse row transformations.

\item{4} Column transformations.

\item{8} Inverse column transformations.
\endlist

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 
(RE) form.
Caveat -- No testing is done to ensure that <mat> is in RE form.  



\>HNFNormDriven( <mat>[, <trans>[, <reduction>]] ) O
\>HNFChouCollins( <mat>[, <trans>[, <reduction>]] ) O
\>HNFLLLDriven( <mat>[, <trans>[, <reduction>]] ) O

These operations have been superceded for most purposes by
`NormalFormIntMat' (see~"NormalFormIntMat")
which should in most cases be faster than any
of them, and produce smaller transforming matrix entries.

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
\quad$\lfloor c(r-1)\rfloor\ldots \lfloor cr\rfloor$,
where $r$ is the value of <reduction>.
If <reduction> is not given, a value of 1 is assumed.
Note, if <trans> is given the operation does not change <mat>.

\beginexample
gap> m:=[ [ 14, 20 ], [ 6, 9 ] ];;
gap> HNFNormDriven(m);
[ [ 2, 2 ], [ 0, 3 ] ]
gap> m;
[ [ 2, 2 ], [ 0, 3 ] ]
\endexample

\beginexample
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 ] ]
\endexample



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

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

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.

\beginexample
gap> m:=[[14,20],[6,9]];
[ [ 14, 20 ], [ 6, 9 ] ]
gap> SmithNormalFormIntegerMat(m);
[ [ 1, 0 ], [ 0, 6 ] ]
\endexample



\>HermiteNormalFormIntegerMat( <mat>[, <reduction>] ) O
\>HermiteNormalFormIntegerMatTransforms( <mat>[, <reduction>] ) O
\>HermiteNormalFormIntegerMatInverseTransforms( <mat>[, <reduction>] ) O

The Hermite Normal Form, $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$. 

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
\quad$\lfloor c(r-1)\rfloor\ldots \lfloor cr\rfloor$
where $r$ is the value of <reduction>.
If <reduction> is not given, a value of 1 is assumed.

\beginexample
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 ] ] )
\endexample



\>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:
\beginlist
\item{0/1} Triangular Form / Smith Normal Form.

\item{2}   Reduce off diagonal entries.

\item{4}   Row Transformations.

\item{8}   Col Transformations.
\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:=[[14,20],[6,9]];;
gap> NormalFormIntMat(m,0);  # Triangular, no transforms
rec( normal := [ [ 2, 2 ], [ 0, 3 ] ], rank := 2, signdet := 1 )
\endexample

\beginexample
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 ] ] )
\endexample

\beginexample
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 ] ]
\endexample




%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\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

