<html><head><title>[ref] 25 Integral matrices and lattices</title></head>
<body text="#000000" bgcolor="#ffffff">
[<a href="../index.htm">Top</a>] [<a href = "chapters.htm">Up</a>] [<a href ="CHAP024.htm">Previous</a>] [<a href ="CHAP026.htm">Next</a>] [<a href = "theindex.htm">Index</a>]
<h1>25 Integral matrices and lattices</h1><p>
<P>
<H3>Sections</H3>
<oL>
<li> <A HREF="CHAP025.htm#SECT001">Linear equations over the integers and Integral Matrices</a>
<li> <A HREF="CHAP025.htm#SECT002">Normal Forms over the Integers</a>
<li> <A HREF="CHAP025.htm#SECT003">Determinant of an integer matrix</a>
<li> <A HREF="CHAP025.htm#SECT004">Decompositions</a>
<li> <A HREF="CHAP025.htm#SECT005">Lattice Reduction</a>
<li> <A HREF="CHAP025.htm#SECT006">Orthogonal Embeddings</a>
</ol><p>
<p>
<p>
<h2><a name="SECT001">25.1 Linear equations over the integers and Integral Matrices</a></h2>
<p><p>
<a name = "SSEC001.1"></a>
<li><code>NullspaceIntMat( </code><var>mat</var><code> ) A</code>
<p>
If <var>mat</var> is a matrix with integral entries, this function returns a
list of vectors that forms a basis of the integral nullspace of <var>mat</var>, i.e.
of those vectors in the nullspace of <var>mat</var> that have integral entries.
<p>
<pre>
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 ] ]
</pre>
<p>
<a name = "SSEC001.2"></a>
<li><code>SolutionIntMat( </code><var>mat</var><code>, </code><var>vec</var><code> ) O</code>
<p>
If <var>mat</var> is a matrix with integral entries and <var>vec</var> a vector with
integral entries, this function returns a vector <var>x</var> with integer entries
that is a solution of the equation <code></code><var>x</var><code> * </code><var>mat</var><code> = </code><var>vec</var><code></code>. It returns <code>fail</code>
if no such vector exists.
<p>
<pre>
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 ]
</pre>
<p>
<a name = "SSEC001.3"></a>
<li><code>SolutionNullspaceIntMat( </code><var>mat</var><code>, </code><var>vec</var><code> ) O</code>
<p>
This function returns a list of length two, its first entry being the
result of a call to <code>SolutionIntMat</code> with same arguments, the second the
result of <code>NullspaceIntMat</code> applied to the matrix <var>mat</var>.
The calculation is performed faster than if two separate calls would be
used.
<p>
<pre>
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 ] ] ]
</pre>
<p>
<a name = "SSEC001.4"></a>
<li><code>BaseIntMat( </code><var>mat</var><code> ) A</code>
<p>
If <var>mat</var> is a matrix with integral entries, this function returns a
list of vectors that forms a basis of the integral row space of <var>mat</var>,
i.e. of the set of integral linear combinations of the rows of <var>mat</var>.
<p>
<pre>
gap> mat:=[[1,2,7],[4,5,6],[10,11,19]];;
gap> BaseIntMat(mat);
[ [ 1, 2, 7 ], [ 0, 3, 7 ], [ 0, 0, 15 ] ]
</pre>
<p>
<a name = "SSEC001.5"></a>
<li><code>BaseIntersectionIntMats( </code><var>m</var><code>, </code><var>n</var><code> ) A</code>
<p>
If <var>m</var> and <var>n</var> 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 <var>m</var> and <var>n</var>.
<p>
<pre>
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 ] ]
</pre>
<p>
<a name = "SSEC001.6"></a>
<li><code>ComplementIntMat( </code><var>full</var><code>, </code><var>sub</var><code> ) A</code>
<p>
Let <var>full</var> be a list of integer vectors generating an Integral
module <var>M</var> and <var>sub</var> a list of vectors defining a submodule <var>S</var>.
This function computes a free basis for <var>M</var> that extends <var>S</var>.
I.e., if the dimension of <var>S</var> is <var>n</var> it
determines a basis <i>B</i>={<i><u>b</i></u><sub>1</sub>,…,<i><u>b</i></u><sub><i>m</i></sub>} for <var>M</var>,
as well as <var>n</var> integers <i>x</i><sub><i>i</i></sub> such that the <var>n</var> vectors
<i><u>s</i></u><sub><i>i</i></sub>:=<i>x</i><sub><i>i</i></sub>·<i><u>b</i></u><sub><i>i</i></sub>} form a basis for <var>S</var>.
<p>
It returns a record with the following
components:
<p>
<dl compact>
<dt><code>complement</code> <dd>
the vectors <i><u>b</i></u><sub><i>n</i>+1</sub> up to <i><u>b</i></u><sub><i>m</i></sub> (they
generate a complement to <var>S</var>).
<p>
<dt><code>sub</code> <dd>
the vectors <i>s</i><sub><i>i</i></sub> (a basis for <var>S</var>).
<p>
<dt><code>moduli</code> <dd>
the factors <i>x</i><sub><i>i</i></sub>.
<p>
</dl>
<p>
<pre>
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 ] )
</pre>
<p>
<p>
<h2><a name="SECT002">25.2 Normal Forms over the Integers</a></h2>
<p><p>
<a name = "SSEC002.1"></a>
<li><code>TriangulizedIntegerMat( </code><var>mat</var><code> ) O</code>
<p>
Computes an upper triangular form of a matrix with integer entries.
It returns a immutable matrix in upper triangular form.
<p>
<a name = "SSEC002.2"></a>
<li><code>TriangulizedIntegerMatTransform( </code><var>mat</var><code> ) O</code>
<p>
Computes an upper triangular form of a matrix with integer entries.
It returns a record with a component <code>normal</code> (an immutable matrix in
upper triangular form) and a component <code>rowtrans</code> that gives the
transformations done to the original matrix to bring it into upper
triangular form.
<p>
<a name = "SSEC002.3"></a>
<li><code>TriangulizeIntegerMat( </code><var>mat</var><code> ) O</code>
<p>
Changes <var>mat</var> to be in upper triangular form. (The result is the same as
that of <code>TriangulizedIntegerMat</code>, but <var>mat</var> will be modified, thus using
less memory.)
If <var>mat</var> is immutable an error will be triggered.
<p>
<pre>
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 ] ]
</pre>
<p>
The Hermite Normal Form (HNF), <i>H</i> of an integer matrix, <i>A</i> 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 <i>Q</i> such that <i>QA</i> = <i>H</i>.
<a name = "SSEC002.4"></a>
<li><code>HermiteNormalFormIntegerMat( </code><var>mat</var><code> ) O</code>
<p>
This operation computes the Hermite normal form of a matrix <var>mat</var> with
integer entries. It returns a immutable matrix in HNF.
<p>
<a name = "SSEC002.5"></a>
<li><code>HermiteNormalFormIntegerMatTransform( </code><var>mat</var><code> ) O</code>
<p>
This operation computes the Hermite normal form of a matrix <var>mat</var> with
integer entries. It returns a record with components <code>normal</code> (a matrix
<i>H</i>) and <code>rowtrans</code> (a matrix <i>Q</i>) such that <i>QA</i>=<i>H</i>
<p>
<pre>
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
</pre>
<p>
The Smith Normal Form,<i>S</i>, of an integer matrix <i>A</i> is the unique
equivalent diagonal form with <i>S</i><sub><i>i</i></sub> dividing <i>S</i><sub><i>j</i></sub> for <i>i</i> < <i>j</i>. There
exist unimodular integer matrices <i>P</i>, <i>Q</i> such that <i>PAQ</i> = <i>S</i>·
<a name = "SSEC002.6"></a>
<li><code>SmithNormalFormIntegerMat( </code><var>mat</var><code> ) O</code>
<p>
This operation computes the Smith normal form of a matrix <var>mat</var> with
integer entries. It returns a new immutable matrix in the Smith normal
form.
<p>
<a name = "SSEC002.7"></a>
<li><code>SmithNormalFormIntegerMatTransforms( </code><var>mat</var><code> ) O</code>
<p>
This operation computes the Smith normal form of a matrix <var>mat</var> with
integer entries. It returns a record with components <code>normal</code> (a matrix
<i>S</i>), <code>rowtrans</code> (a matrix <i>P</i>), and <code>coltrans</code> (a matrix <i>Q</i>) such that
<i>PAQ</i>=<i>S</i>.
<p>
<a name = "SSEC002.8"></a>
<li><code>DiagonalizeIntMat( </code><var>mat</var><code> ) O</code>
<p>
This function changes <var>mat</var> to its SNF.
(The result is the same as
that of <code>SmithNormalFormIntegerMat</code>, but <var>mat</var> will be modified, thus using
less memory.)
If <var>mat</var> is immutable an error will be triggered.
<p>
<pre>
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 ] ]
</pre>
<p>
All these routines build on the following ``workhorse'' routine:
<a name = "SSEC002.9"></a>
<li><code>NormalFormIntMat( </code><var>mat</var><code>, </code><var>options</var><code> ) O</code>
<p>
This general operation for computation of various Normal Forms
is probably the most efficient.
<p>
Options bit values:
<dl compact>
<dt>0/1<dd>Triangular Form / Smith Normal Form.
<p>
<dt>2<dd>Reduce off diagonal entries.
<p>
<dt>4<dd>Row Transformations.
<p>
<dt>8<dd>Col Transformations.
<p>
<dt>16<dd>Destructive (the original matrix may be destroyed)
</dl>
<p>
Compute a Triangular, Hermite or Smith form of the <i>n</i> ×<i>m</i>
integer input matrix <i>A</i>. Optionally, compute <i>n</i> ×<i>n</i> and
<i>m</i> ×<i>m</i> unimodular transforming matrices <i>Q</i>, <i>P</i> which satisfy
<i>QA</i> = <i>H</i> or <i>QAP</i> = <i>S</i>.
<p>
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.
<p>
Returns a record with component <code>normal</code> containing the
computed normal form and optional components <code>rowtrans</code>
and/or <code>coltrans</code> 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.
<p>
<pre>
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 ] ]
</pre>
<p>
<a name = "SSEC002.10"></a>
<li><code>AbelianInvariantsOfList( </code><var>list</var><code> ) A</code>
<p>
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.
<p>
<pre>
gap> AbelianInvariantsOfList([4,6,2,12]);
[ 2, 2, 3, 3, 4, 4 ]
</pre>
<p>
<p>
<h2><a name="SECT003">25.3 Determinant of an integer matrix</a></h2>
<p><a name = "I0"></a>
<p>
<a name = "SSEC003.1"></a>
<li><code>DeterminantIntMat( </code><var>mat</var><code> ) O</code>
<p>
Computes the determinant of an integer matrix using the
same strategy as <code>NormalFormIntMat</code> (see <a href="CHAP025.htm#SSEC002.9">NormalFormIntMat</a>).
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 <code>DeterminantMat</code> (see <a href="CHAP024.htm#SSEC003.4">DeterminantMat</a>)
for these smaller matrices.
<p>
<p>
<h2><a name="SECT004">25.4 Decompositions</a></h2>
<p><p>
<a name = "I1"></a>
<a name = "I2"></a>
For computing the decomposition of a vector of integers into the rows of
a matrix of integers, with integral coefficients,
one can use <i>p</i>-adic approximations, as follows.
<p>
Let <i>A</i> be a square integral matrix, and <i>p</i> an odd prime.
The reduction of <i>A</i> modulo <i>p</i> is [(<i>A</i>)],
its entries are chosen in the interval
[−[(<i>p</i>−1)/2], [(<i>p</i>−1)/2]].
If [(<i>A</i>)] is regular over the field with <i>p</i> elements,
we can form <i>A</i><sup>′</sup> = [(<i>A</i>)]<sup>−1</sup>.
Now we consider the integral linear equation system <i>x</i> <i>A</i> = <i>b</i>,
i.e., we look for an integral solution <i>x</i>.
Define <i>b</i><sub>0</sub> = <i>b</i>, and then iteratively compute
<br clear="all" /><table border="0" width="100%"><tr><td><table align="center" cellspacing="0" cellpadding="2"><tr><td nowrap="nowrap" align="center"> <i>x</i><sub><i>i</i></sub> = (<i>b</i><sub><i>i</i></sub> <i>A</i><sup>′</sup>) mod <i>p</i>, <i>b</i><sub><i>i</i>+1</sub> = </td><td nowrap="nowrap" align="center">1<div class="hrcomp"><hr noshade="noshade" size="1"/></div><i>p</i><br /></td><td nowrap="nowrap" align="center">(<i>b</i><sub><i>i</i></sub> − <i>x</i><sub><i>i</i></sub> <i>A</i>), <i>i</i> = 0, 1, 2, …. </td></tr></table></td></tr></table>
By induction, we get
<br clear="all" /><table border="0" width="100%"><tr><td><table align="center" cellspacing="0" cellpadding="2"><tr><td nowrap="nowrap" align="center"> <i>p</i><sup><i>i</i>+1</sup> <i>b</i><sub><i>i</i>+1</sub> + </td><td align="left" class="cl"><br /> </td><td nowrap="nowrap" align="center"><small><i>i</i></small><!--sup--><br /><font size="+3">∑<br /></font><small><i>j</i>=0</small> <br /></td><td nowrap="nowrap" align="center"><i>p</i><sup><i>j</i></sup> <i>x</i><sub><i>j</i></sub> </td><td align="left" class="cl"><br /></td><td nowrap="nowrap" align="center"><i>A</i> = <i>b</i>. </td></tr></table></td></tr></table>
If there is an integral solution <i>x</i> then it is unique,
and there is an index <i>l</i> such that <i>b</i><sub><i>l</i>+1</sub> is zero
and <i>x</i> = ∑<sub><i>j</i>=0</sub><sup><i>l</i></sup> <i>p</i><sup><i>j</i></sup> <i>x</i><sub><i>j</i></sub>.
<p>
There are two useful generalizations of this idea.
First, <i>A</i> need not be square; it is only necessary that there is
a square regular matrix formed by a subset of columns of <i>A</i>.
Second, <i>A</i> does not need to be integral;
the entries may be cyclotomic integers as well,
in this case one can replace each column of <var>A</var> 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
<var>A</var> and <var>b</var>.
<p>
<font face="Gill Sans,Helvetica,Arial">GAP</font> provides the following functions for this purpose
(see also <a href="CHAP024.htm#SSEC013.5">InverseMatMod</a>).
<p>
<a name = "SSEC004.1"></a>
<li><code>Decomposition( </code><var>A</var><code>, </code><var>B</var><code>, </code><var>depth</var><code> ) F</code>
<li><code>Decomposition( </code><var>A</var><code>, </code><var>B</var><code>, "nonnegative" ) F</code>
<p>
For a <i>m</i> ×<i>n</i> matrix <var>A</var> of cyclotomics that has rank <i>m</i> ≤ <i>n</i>,
and a list <var>B</var> of cyclotomic vectors, each of length <i>n</i>,
<code>Decomposition</code> tries to find integral solutions of the linear equation
systems <code></code><var>x</var><code> * </code><var>A</var><code> = </code><var>B</var><code>[i]</code>,
by computing the <i>p</i>-adic series of hypothetical solutions.
<p>
<code>Decomposition( </code><var>A</var><code>, </code><var>B</var><code>, </code><var>depth</var><code> )</code>, where <var>depth</var> is a nonnegative
integer, computes for each vector <code></code><var>B</var><code>[i]</code> the initial part
∑<sub><i>k</i>=0</sub><sup><i>depth</i> </sup> <i>x</i><sub><i>k</i></sub> <i>p</i><sup><i>k</i></sup>,
with all <i>x</i><sub><i>k</i></sub> vectors of integers with entries bounded by
±[(<i>p</i>−1)/2].
The prime <i>p</i> is 83 first; if the reduction of <var>A</var>
modulo <i>p</i> is singular, the next prime is chosen automatically.
<p>
A list <var>X</var> is returned.
If the computed initial part for <code></code><var>x</var><code> * </code><var>A</var><code> = </code><var>B</var><code>[i]</code> <strong>is</strong> a solution,
we have <code></code><var>X</var><code>[i] = </code><var>x</var><code></code>, otherwise <code></code><var>X</var><code>[i] = fail</code>.
<p>
<code>Decomposition( </code><var>A</var><code>, </code><var>B</var><code>, "nonnegative" )</code> assumes that the solutions
have only nonnegative entries,
and that the first column of <var>A</var> consists of positive integers.
This is satisfied, e.g., for the decomposition of ordinary characters
into Brauer characters.
In this case the necessary number <var>depth</var> of iterations can be computed;
the <code>i</code>-th entry of the returned list is <code>fail</code> if there <strong>exists</strong> no
nonnegative integral solution of the system <code></code><var>x</var><code> * </code><var>A</var><code> = </code><var>B</var><code>[i]</code>, and it
is the solution otherwise.
<p>
<strong>Note</strong> that the result is a list of <code>fail</code> if <var>A</var> has not full rank,
even if there might be a unique integral solution for some equation
system.
<p>
<a name = "SSEC004.2"></a>
<li><code>LinearIndependentColumns( </code><var>mat</var><code> ) F</code>
<p>
Called with a matrix <var>mat</var>, <code>LinearIndependentColumns</code> returns a maximal
list of column positions such that the restriction of <var>mat</var> to these
columns has the same rank as <var>mat</var>.
<p>
<a name = "SSEC004.3"></a>
<li><code>PadicCoefficients( </code><var>A</var><code>, </code><var>Amodpinv</var><code>, </code><var>b</var><code>, </code><var>prime</var><code>, </code><var>depth</var><code> ) F</code>
<p>
Let <var>A</var> be an integral matrix,
<var>prime</var> a prime integer,
<var>Amodpinv</var> an inverse of <var>A</var> modulo <var>prime</var>,
<var>b</var> an integral vector,
and <var>depth</var> a nonnegative integer.
<code>PadicCoefficients</code> returns the list [ <i>x</i><sub>0</sub>, <i>x</i><sub>1</sub>, …, <i>x</i><sub><i>l</i></sub>, <i>b</i><sub><i>l</i>+1</sub> ]
describing the <var>prime</var>-adic approximation of <var>b</var> (see above),
where <i>l</i> = <i>depth</i>
or <i>l</i> is minimal with the property that <i>b</i><sub><i>l</i>+1</sub> = 0.
<p>
<a name = "SSEC004.4"></a>
<li><code>IntegralizedMat( </code><var>A</var><code> ) F</code>
<li><code>IntegralizedMat( </code><var>A</var><code>, </code><var>inforec</var><code> ) F</code>
<p>
<code>IntegralizedMat</code> returns for a matrix <var>A</var> of cyclotomics
a record <var>intmat</var> with components <code>mat</code> and <code>inforec</code>.
Each family of algebraic conjugate columns of <var>A</var> is encoded in a set of
columns of the rational matrix <code></code><var>intmat</var><code>.mat</code> by replacing cyclotomics
in <var>A</var> by their coefficients w.r.t. an integral basis.
<code></code><var>intmat</var><code>.inforec</code> is a record containing the information how to encode
the columns.
<p>
If the only argument is <var>A</var>, the value of the component <code>inforec</code> is
computed that can be entered as second argument <var>inforec</var> in a later call
of <code>IntegralizedMat</code> with a matrix <var>B</var> that shall be encoded compatibly
with <var>A</var>.
<p>
<a name = "SSEC004.5"></a>
<li><code>DecompositionInt( </code><var>A</var><code>, </code><var>B</var><code>, </code><var>depth</var><code> ) F</code>
<p>
<code>DecompositionInt</code> does the same as <code>Decomposition</code>
(see <a href="CHAP025.htm#SSEC004.1">Decomposition</a>),
except that <var>A</var> and <var>B</var> must be integral matrices, and <var>depth</var> must be
a nonnegative integer.
<p>
<p>
<h2><a name="SECT005">25.5 Lattice Reduction</a></h2>
<p><p>
<a name = "I3"></a>
<a name = "I4"></a>
<a name = "I5"></a>
<a name = "SSEC005.1"></a>
<li><code>LLLReducedBasis( [</code><var>L</var><code>, ]</code><var>vectors</var><code>[, </code><var>y</var><code>][, "linearcomb"][, </code><var>lllout</var><code>] ) F</code>
<p>
provides an implementation of the LLL algorithm by
Lenstra, Lenstra and Lovász (see <a href="biblio.htm#LLL82"><cite>LLL82</cite></a>, <a href="biblio.htm#Poh87"><cite>Poh87</cite></a>).
The implementation follows the description on pages 94f. in <a href="biblio.htm#Coh93"><cite>Coh93</cite></a>.
<p>
<code>LLLReducedBasis</code> returns a record whose component <code>basis</code> is a list of
LLL reduced linearly independent vectors spanning the same lattice as
the list <var>vectors</var>.
<var>L</var> must be a lattice, with scalar product of the vectors <var>v</var> and <var>w</var>
given by <code>ScalarProduct( </code><var>L</var><code>, </code><var>v</var><code>, </code><var>w</var><code> )</code>.
If no lattice is specified then the scalar product of vectors given by
<code>ScalarProduct( </code><var>v</var><code>, </code><var>w</var><code> )</code> is used.
<p>
In the case of the option <code>"linearcomb"</code>, the result record contains
also the components <code>relations</code> and <code>transformation</code>, with the following
meaning.
<code>relations</code> is a basis of the relation space of <var>vectors</var>, i.e., of
vectors <var>x</var> such that <code></code><var>x</var><code> * </code><var>vectors</var><code></code> is zero.
<code>transformation</code> gives the expression of the new lattice basis in
terms of the old, i.e.,
<code>transformation * </code><var>vectors</var><code></code> equals the <code>basis</code> component of the result.
<p>
Another optional argument is <var>y</var>, the ``sensitivity'' of the algorithm,
a rational number between [1/4] and 1 (the default value is
[3/4]).
<p>
The optional argument <var>lllout</var> is a record with the components <code>mue</code>
and <code>B</code>, both lists of length <i>k</i>, with the meaning that
if <var>lllout</var> is present then the first <i>k</i> vectors in <var>vectors</var> form
an LLL reduced basis of the lattice they generate,
and <code></code><var>lllout</var><code>.mue</code> and <code></code><var>lllout</var><code>.B</code> contain their scalar products and
norms used internally in the algorithm, which are also present in the
output of <code>LLLReducedBasis</code>.
So <var>lllout</var> can be used for ``incremental'' calls of <code>LLLReducedBasis</code>.
<p>
The function <code>LLLReducedGramMat</code> (see <a href="CHAP025.htm#SSEC005.2">LLLReducedGramMat</a>)
computes an LLL reduced Gram matrix.
<p>
<pre>
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 ] )
</pre>
<p>
<a name = "I6"></a>
<a name = "SSEC005.2"></a>
<li><code>LLLReducedGramMat( </code><var>G</var><code> ) F</code>
<li><code>LLLReducedGramMat( </code><var>G</var><code>, </code><var>y</var><code> ) F</code>
<p>
<code>LLLReducedGramMat</code> provides an implementation of the LLL algorithm by
Lenstra, Lenstra and Lovász (see <a href="biblio.htm#LLL82"><cite>LLL82</cite></a>, <a href="biblio.htm#Poh87"><cite>Poh87</cite></a>).
The implementation follows the description on pages 94f. in <a href="biblio.htm#Coh93"><cite>Coh93</cite></a>.
<p>
Let <var>G</var> the Gram matrix of the vectors (<i>b</i><sub>1</sub>, <i>b</i><sub>2</sub>, …, <i>b</i><sub><i>n</i></sub>);
this means <var>G</var> is either a square symmetric matrix or lower triangular
matrix (only the entries in the lower triangular half are used by the
program).
<p>
<code>LLLReducedGramMat</code> returns a record whose component <code>remainder</code> is the
Gram matrix of the LLL reduced basis corresponding to (<i>b</i><sub>1</sub>, <i>b</i><sub>2</sub>, …, <i>b</i><sub><i>n</i></sub>).
If <var>G</var> is a lower triangular matrix then also the <code>remainder</code> component
of the result record is a lower triangular matrix.
<p>
The result record contains also the components <code>relations</code> and
<code>transformation</code>, which have the following meaning.
<p>
<code>relations</code> is a basis of the space of vectors (<i>x</i><sub>1</sub>,<i>x</i><sub>2</sub>,…,<i>x</i><sub><i>n</i></sub>)
such that ∑<sub><i>i</i>=1</sub><sup><i>n</i></sup> <i>x</i><sub><i>i</i></sub> <i>b</i><sub><i>i</i></sub> is zero,
and <code>transformation</code> gives the expression of the new lattice basis in
terms of the old, i.e., <code>transformation</code> is the matrix <i>T</i> such that
<i>T</i> ·<i>G</i> ·<i>T</i><sup><i>tr</i></sup> is the <code>remainder</code> component of the result.
<p>
The optional argument <var>y</var> denotes the ``sensitivity'' of the algorithm,
it must be a rational number between [1/4] and 1; the default
value is <i>y</i> = [3/4].
<p>
The function <code>LLLReducedBasis</code> (see <a href="CHAP025.htm#SSEC005.1">LLLReducedBasis</a>)
computes an LLL reduced basis.
<p>
<pre>
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 ] )
</pre>
<p>
<p>
<h2><a name="SECT006">25.6 Orthogonal Embeddings</a></h2>
<p><p>
<a name = "SSEC006.1"></a>
<li><code>OrthogonalEmbeddings( </code><var>gram</var><code>[, "positive"][, </code><var>maxdim</var><code>] ) F</code>
<p>
computes all possible orthogonal embeddings of a lattice given by its
Gram matrix <var>gram</var>, which must be a regular matrix.
In other words, all solutions <i>X</i> of the problem
<br clear="all" /><table border="0" width="100%"><tr><td><table align="center" cellspacing="0" cellpadding="2"><tr><td nowrap="nowrap" align="center"> <i>X</i><sup><i>tr</i></sup> ·<i>X</i> = <i>gram</i> </td></tr></table></td></tr></table>
are calculated (see <a href="biblio.htm#Ple90"><cite>Ple90</cite></a>).
Usually there are many solutions <i>X</i>
but all their rows are chosen from a small set of vectors,
so <code>OrthogonalEmbeddings</code> returns the solutions in an encoded form,
namely as a record with components
<p>
<dl compact>
<dt><code>vectors</code> <dd>
the list <i>L</i> = [ <i>x</i><sub>1</sub>, <i>x</i><sub>2</sub>, …, <i>x</i><sub><i>n</i></sub> ] of vectors
that may be rows of a solution;
these are exactly those vectors that fulfill the condition
<i>x</i><sub><i>i</i></sub> ·<i>gram</i> <sup>−1</sup> ·<i>x</i><sub><i>i</i></sub><sup><i>tr</i></sup> ≤ 1
(see <a href="CHAP025.htm#SSEC006.2">ShortestVectors</a>),
and we have <i>gram</i> = ∑<sup><i>n</i></sup><sub><i>i</i>=1</sub> <i>x</i><sub><i>i</i></sub><sup><i>tr</i></sup> ·<i>x</i><sub><i>i</i></sub>,
<p>
<dt><code>norms</code> <dd>
the list of values <i>x</i><sub><i>i</i></sub> ·<i>gram</i> <sup>−1</sup> ·<i>x</i><sub><i>i</i></sub><sup><i>tr</i></sup>, and
<p>
<dt><code>solutions</code> <dd>
a list <var>S</var> of lists; the <var>i</var>-th solution matrix is
<code></code><var>L</var><code> </code><var>S</var><code>[</code><var>i</var><code>] </code>,
so the dimension of the <var>i</var>-th solution is the length of
<code></code><var>S</var><code>[</code><var>i</var><code>]</code>.
</dl>
<p>
The optional argument <code>"positive"</code> will cause <code>OrthogonalEmbeddings</code>
to compute only vectors <i>x</i><sub><i>i</i></sub> with nonnegative entries.
In the context of characters this is allowed (and useful)
if <var>gram</var> is the matrix of scalar products of ordinary characters.
<p>
When <code>OrthogonalEmbeddings</code> is called with the optional argument
<var>maxdim</var> (a positive integer),
only solutions up to dimension <var>maxdim</var> are computed;
this will accelerate the algorithm in some cases.
<pre>
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 ] ]
</pre>
<p>
<var>gram</var> may be the matrix of scalar products of some virtual characters.
From the characters and the embedding given by the matrix <i>X</i>,
<code>Decreased</code> (see <a href="CHAP070.htm#SSEC010.7">Decreased</a>) may be able to compute irreducibles,
see <a href="CHAP070.htm#SECT010">Reducing Virtual Characters</a>.
<p>
<a name = "SSEC006.2"></a>
<li><code>ShortestVectors( </code><var>G</var><code>, </code><var>m</var><code>[, "positive"] ) F</code>
<p>
Let <var>G</var> be a regular matrix of a symmetric bilinear form,
and <var>m</var> a nonnegative integer.
<code>ShortestVectors</code> computes the vectors <i>x</i> that satisfy
<i>x</i> ·<i>G</i> ·<i>x</i><sup><i>tr</i></sup> ≤ <i>m</i> ,
and returns a record describing these vectors.
The result record has the components
<p>
<dl compact>
<dt><code>vectors</code> <dd>
list of the nonzero vectors <i>x</i>, but only one of each pair (<i>x</i>,−<i>x</i>),
<p>
<dt><code>norms</code> <dd>
list of norms of the vectors according to the Gram matrix <var>G</var>.
</dl>
If the optional argument <code>"positive"</code> is entered,
only those vectors <i>x</i> with nonnegative entries are computed.
<pre>
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 ] )
</pre>
<p>
<p>
[<a href="../index.htm">Top</a>] [<a href = "chapters.htm">Up</a>] [<a href ="CHAP024.htm">Previous</a>] [<a href ="CHAP026.htm">Next</a>] [<a href = "theindex.htm">Index</a>]
<P>
<font face="Gill Sans,Helvetica,Arial">GAP 4 manual<br>December 2008
</font></body></html>
distrib
>
Mandriva
>
2010.0
>
i586
>
media
>
contrib-release
>
by-pkgid
>
5e1854624d3bc613bdd0dd13d1ef9ac7
>
files
>
167
