% 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