Quelle chap25_mj.html
Sprache: HTML
|
|
| products/sources/formale Sprachen/GAP/doc/ref/chap25_mj.html |
 |
<?xml version= "1.0" encoding= "UTF-8"?>
<! DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN"
"http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
< html xmlns= "http://www.w3.org/1999/xhtml" xml:lang= "en">
< head>
< script type= "text/javascript"
src= "https://cdn.jsdelivr.net/npm/mathjax@2/MathJax.js?config=TeX-AMS-MML_HTMLorMML">
</ script>
< title>GAP (ref) - Chapter 25: Integral matrices and lattices</ title>
< meta http-equiv= "content-type" content= "text/html; charset=UTF-8" />
< meta name= "generator" content= "GAPDoc2HTML" />
< link rel= "stylesheet" type= "text/css" href= "manual.css" />
< script src= "manual.js" type= "text/javascript"></ script>
< script type= "text/javascript">overwriteStyle();</ script>
</ head>
< body class= "chap25" onload= "jscontent()">
< div class= "chlinktop">< span class= "chlink1">Goto Chapter: </ span><a href= "chap0_mj.html">Top< /a> <a href="chap1_mj.html">1</a> <a href="chap2_mj.html">2</a> <a href="chap3_mj.html">3</a> <a href="chap4_mj.html">4</a> <a href="chap5_mj.html">5</a> <a href="chap6_mj.html">6</a> <a href="chap7_mj.html">7</a> <a href="chap8_mj.html">8</a> <a href="chap9_mj.html">9</a> <a href="chap10_mj.html">10</a> <a href="chap11_mj.html">11</a> <a href="chap12_mj.html">12</a> <a href="chap13_mj.html">13</a> <a href="chap14_mj.html">14</a> <a href="chap15_mj.html">15</a> <a href="chap16_mj.html">16</a> <a href="chap17_mj.html">17</a> <a href="chap18_mj.html">18</a> <a href="chap19_mj.html">19</a> <a href="chap20_mj.html">20</a> <a href="chap21_mj.html">21</a> <a href="chap22_mj.html">22</a> <a href="chap23_mj.html">23</a> <a href="chap24_mj.html">24</a> <a href="chap25_mj.html">25</a> <a href="chap26_mj.html">26</a> <a href="chap27_mj.html">27</a> <a href="chap28_mj.html">28</a> <a href="chap29_mj.html">29</a> <a href="chap30_mj.html">30</a> <a href="chap31_mj.html">31</a> <a href="chap32_mj.html">32</a> <a href="chap33_mj.html">33</a> <a href="chap34_mj.html">34</a> <a href="chap35_mj.html">35</a> <a href="chap36_mj.html">36</a> <a href="chap37_mj.html">37</a> <a href="chap38_mj.html">38</a> <a href="chap39_mj.html">39</a> <a href="chap40_mj.html">40</a> <a href="chap41_mj.html">41</a> <a href="chap42_mj.html">42</a> <a href="chap43_mj.html">43</a> <a href="chap44_mj.html">44</a> <a href="chap45_mj.html">45</a> <a href="chap46_mj.html">46</a> <a href="chap47_mj.html">47</a> <a href="chap48_mj.html">48</a> <a href="chap49_mj.html">49</a> <a href="chap50_mj.html">50</a> <a href="chap51_mj.html">51</a> <a href="chap52_mj.html">52</a> <a href="chap53_mj.html">53</a> <a href="chap54_mj.html">54</a> <a href="chap55_mj.html">55</a> <a href="chap56_mj.html">56</a> <a href="chap57_mj.html">57</a> <a href="chap58_mj.html">58</a> <a href="chap59_mj.html">59</a> <a href="chap60_mj.html">60</a> <a href="chap61_mj.html">61</a> <a href="chap62_mj.html">62</a> <a href="chap63_mj.html">63</a> <a href="chap64_mj.html">64</a> <a href="chap65_mj.html">65</a> <a href="chap66_mj.html">66</a> <a href="chap67_mj.html">67</a> <a href="chap68_mj.html">68</a> <a href="chap69_mj.html">69</a> <a href="chap70_mj.html">70</a> <a href="chap71_mj.html">71</a> <a href="chap72_mj.html">72</a> <a href="chap73_mj.html">73</a> <a href="chap74_mj.html">74</a> <a href="chap75_mj.html">75</a> <a href="chap76_mj.html">76</a> <a href="chap77_mj.html">77</a> <a href="chap78_mj.html">78</a> <a href="chap79_mj.html">79</a> <a href="chap80_mj.html">80</a> <a href="chap81_mj.html">81</a> <a href="chap82_mj.html">82</a> <a href="chap83_mj.html">83</a> <a href="chap84_mj.html">84</a> <a href="chap85_mj.html">85</a> <a href="chap86_mj.html">86</a> <a href="chap87_mj.html">87</a> <a href="chapBib_mj.html">Bib</a> <a href="chapInd_mj.html">Ind</a> </div>
<div class="chlinkprevnexttop"> <a href="chap0_mj.html">[Top of Book]</a> <a href="chap0_mj.html#contents">[Contents]</a> <a href="chap24_mj.html">[Previous Chapter]</a> <a href="chap26_mj.html">[Next Chapter]</a> </div>
<p id="mathjaxlink" class="pcenter"><a href="chap25.html">[MathJax off]</a></p>
<p><a id="X8414F20D8412DDA4" name="X8414F20D8412DDA4"></a></p>
<div class="ChapSects"><a href="chap25_mj.html#X8414F20D8412DDA4">25 <span class="Heading">Integral matrices and lattices</span></a>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap25_mj.html#X786A64B983339767">25.1 <span class="Heading">Linear equations over the integers and Integral Matrices</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap25_mj.html#X792315717F5B0294">25.1-1 NullspaceIntMat</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap25_mj.html#X7D749F317DBD1E69">25.1-2 SolutionIntMat</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap25_mj.html#X82CECB6E7D515CD2">25.1-3 SolutionNullspaceIntMat</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap25_mj.html#X7F66E8EA7D1AA2C1">25.1-4 BaseIntMat</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap25_mj.html#X8771349D865C9179">25.1-5 BaseIntersectionIntMats</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap25_mj.html#X7848EF9F83D491C1">25.1-6 ComplementIntMat</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap25_mj.html#X8143C1448069D846">25.2 <span class="Heading">Normal Forms over the Integers</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap25_mj.html#X783CEC847D81F22A">25.2-1 TriangulizedIntegerMat</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap25_mj.html#X7DBE174E8625AFA5">25.2-2 TriangulizedIntegerMatTransform</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap25_mj.html#X78CD40A687FE2311">25.2-3 TriangulizeIntegerMat</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap25_mj.html#X8535AC327932B89F">25.2-4 HermiteNormalFormIntegerMat</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap25_mj.html#X7FDA78F979574ACC">25.2-5 HermiteNormalFormIntegerMatTransform</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap25_mj.html#X87089FEC7FBEEA8F">25.2-6 SmithNormalFormIntegerMat</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap25_mj.html#X839C1F9E87273A93">25.2-7 SmithNormalFormIntegerMatTransforms</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap25_mj.html#X80EF38737F6D61DB">25.2-8 DiagonalizeIntMat</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap25_mj.html#X81FB746E82BE6CDA">25.2-9 NormalFormIntMat</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap25_mj.html#X8221694D7C99197A">25.2-10 AbelianInvariantsOfList</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap25_mj.html#X80F6990983C979FB">25.3 <span class="Heading">Determinant of an integer matrix</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap25_mj.html#X787599E087F4C0BA">25.3-1 DeterminantIntMat</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap25_mj.html#X79F2EFEC7C3EA80C">25.4 <span class="Heading">Decompositions</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap25_mj.html#X7911A60384C511AB">25.4-1 Decomposition</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap25_mj.html#X843A976787600F13">25.4-2 LinearIndependentColumns</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap25_mj.html#X8285776B7DD86925">25.4-3 PadicCoefficients</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap25_mj.html#X7F5C619B7A9C3EB9">25.4-4 IntegralizedMat</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap25_mj.html#X8512FB69824AE353">25.4-5 DecompositionInt</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap25_mj.html#X839C6ABE829355F4">25.5 <span class="Heading">Lattice Reduction</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap25_mj.html#X7D0FCEF8859E8637">25.5-1 LLLReducedBasis</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap25_mj.html#X86D23EB885EDE60E">25.5-2 LLLReducedGramMat</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap25_mj.html#X871DB00B803D5177">25.6 <span class="Heading">Orthogonal Embeddings</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap25_mj.html#X842280C2808FF05D">25.6-1 OrthogonalEmbeddings</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap25_mj.html#X79A692B6819353D4">25.6-2 ShortestVectors</a></span>
</div></div>
</div>
<h3>25 <span class="Heading">Integral matrices and lattices</span></h3>
<p><a id="X786A64B983339767" name="X786A64B983339767"></a></p>
<h4>25.1 <span class="Heading">Linear equations over the integers and Integral Matrices</span></h4>
<p><a id="X792315717F5B0294" name="X792315717F5B0294"></a></p>
<h5>25.1-1 NullspaceIntMat</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ NullspaceIntMat</code>( <var class="Arg">mat</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>If <var class="Arg">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 class="Arg">mat</var>, i.e., of those vectors in the nullspace of <var class="Arg">mat</var> that have integral entries.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">mat:=[[1,2,7],[4,5,6],[7,8,9],[10,11,19],[5,7,12]];;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">NullspaceMat(mat);</span>
[ [ -7/4, 9/2, -15/4, 1, 0 ], [ -3/4, -3/2, 1/4, 0, 1 ] ]
<span class="GAPprompt">gap></span> <span class="GAPinput">NullspaceIntMat(mat);</span>
[ [ 1, 18, -9, 2, -6 ], [ 0, 24, -13, 3, -7 ] ]
</pre></div>
<p><a id="X7D749F317DBD1E69" name="X7D749F317DBD1E69"></a></p>
<h5>25.1-2 SolutionIntMat</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ SolutionIntMat</code>( <var class="Arg">mat</var>, <var class="Arg">vec</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>If <var class="Arg">mat</var> is a matrix with integral entries and <var class="Arg">vec</var> a vector with integral entries, this function returns a vector <span class="SimpleMath">\(x\)</span> with integer entries that is a solution of the equation <span class="SimpleMath">\(x\)</span> <code class="code">* <var class="Arg">mat</var> = <var class="Arg">vec</var></code>. It returns <code class="keyw">fail</code> if no such vector exists.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">mat:=[[1,2,7],[4,5,6],[7,8,9],[10,11,19],[5,7,12]];;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">SolutionMat(mat,[95,115,182]);</span>
[ 47/4, -17/2, 67/4, 0, 0 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">SolutionIntMat(mat,[95,115,182]);</span>
[ 2285, -5854, 4888, -1299, 0 ]
</pre></div>
<p><a id="X82CECB6E7D515CD2" name="X82CECB6E7D515CD2"></a></p>
<h5>25.1-3 SolutionNullspaceIntMat</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ SolutionNullspaceIntMat</code>( <var class="Arg">mat</var>, <var class="Arg">vec</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>This function returns a list of length two, its first entry being the result of a call to <code class="func">SolutionIntMat</code> (<a href="chap25_mj.html#X7D749F317DBD1E69"><span class="RefLink">25.1-2</span></a>) with same arguments, the second the result of <code class="func">NullspaceIntMat</code> (<a href="chap25_mj.html#X792315717F5B0294"><span class="RefLink">25.1-1</span></a>) applied to the matrix <var class="Arg">mat</var>. The calculation is performed faster than if two separate calls would be used.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">mat:=[[1,2,7],[4,5,6],[7,8,9],[10,11,19],[5,7,12]];;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">SolutionNullspaceIntMat(mat,[95,115,182]);</span>
[ [ 2285, -5854, 4888, -1299, 0 ],
[ [ 1, 18, -9, 2, -6 ], [ 0, 24, -13, 3, -7 ] ] ]
</pre></div>
<p><a id="X7F66E8EA7D1AA2C1" name="X7F66E8EA7D1AA2C1"></a></p>
<h5>25.1-4 BaseIntMat</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ BaseIntMat</code>( <var class="Arg">mat</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>If <var class="Arg">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 class="Arg">mat</var>, i.e. of the set of integral linear combinations of the rows of <var class="Arg">mat</var>.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">mat:=[[1,2,7],[4,5,6],[10,11,19]];;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">BaseIntMat(mat);</span>
[ [ 1, 2, 7 ], [ 0, 3, 7 ], [ 0, 0, 15 ] ]
</pre></div>
<p><a id="X8771349D865C9179" name="X8771349D865C9179"></a></p>
<h5>25.1-5 BaseIntersectionIntMats</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ BaseIntersectionIntMats</code>( <var class="Arg">m</var>, <var class="Arg">n</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>If <var class="Arg">m</var> and <var class="Arg">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 class="Arg">m</var> and <var class="Arg">n</var>.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">nat:=[[5,7,2],[4,2,5],[7,1,4]];;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">BaseIntMat(nat);</span>
[ [ 1, 1, 15 ], [ 0, 2, 55 ], [ 0, 0, 64 ] ]
<span class="GAPprompt">gap></span> <span class="GAPinput">BaseIntersectionIntMats(mat,nat);</span>
[ [ 1, 5, 509 ], [ 0, 6, 869 ], [ 0, 0, 960 ] ]
</pre></div>
<p><a id="X7848EF9F83D491C1" name="X7848EF9F83D491C1"></a></p>
<h5>25.1-6 ComplementIntMat</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ ComplementIntMat</code>( <var class="Arg">full</var>, <var class="Arg">sub</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Let <var class="Arg">full</var> be a list of integer vectors generating an integral row module <span class="SimpleMath">\(M\)</span> and <var class="Arg">sub</var> a list of vectors defining a submodule <span class="SimpleMath">\(S\)</span> of <span class="SimpleMath">\(M\)</span>. This function computes a free basis for <span class="SimpleMath">\(M\)</span> that extends <span class="SimpleMath">\(S\)</span>. I.e., if the dimension of <span class="SimpleMath">\(S\)</span> is <span class="SimpleMath">\(n\)</span> it determines a basis <span class="SimpleMath">\(B = \{ b_1, \ldots, b_m \}\)</span> for <span class="SimpleMath">\(M\)</span>, as well as <span class="SimpleMath">\(n\)</span> integers <span class="SimpleMath">\(x_i\)</span> such that the <span class="SimpleMath">\(n\)</span> vectors <span class="SimpleMath">\(s_i:= x_i \cdot b_i\)</span> form a basis for <span class="SimpleMath">\(S\)</span>.</p>
<p>It returns a record with the following components:</p>
<dl>
<dt><strong class="Mark"><code class="code">complement</code></strong></dt>
<dd><p>the vectors <span class="SimpleMath">\(b_{{n+1}}\)</span> up to <span class="SimpleMath">\(b_m\)</span> (they generate a complement to <span class="SimpleMath">\(S\)</span>).</p>
</dd>
<dt><strong class="Mark"><code class="code">sub</code></strong></dt>
<dd><p>the vectors <span class="SimpleMath">\(s_i\)</span> (a basis for <span class="SimpleMath">\(S\)</span>).</p>
</dd>
<dt><strong class="Mark"><code class="code">moduli</code></strong></dt>
<dd><p>the factors <span class="SimpleMath">\(x_i\)</span>.</p>
</dd>
</dl>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">m:=IdentityMat(3);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">n:=[[1,2,3],[4,5,6]];;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">ComplementIntMat(m,n);</span>
rec( complement := [ [ 0, 0, 1 ] ], moduli := [ 1, 3 ],
sub := [ [ 1, 2, 3 ], [ 0, 3, 6 ] ] )
</pre></div>
<p><a id="X8143C1448069D846" name="X8143C1448069D846"></a></p>
<h4>25.2 <span class="Heading">Normal Forms over the Integers</span></h4>
<p>This section describes the computation of the Hermite and Smith normal form of integer matrices.</p>
<p>The Hermite Normal Form (HNF) <span class="SimpleMath">\(H\)</span> of an integer matrix <span class="SimpleMath">\(A\)</span> 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 <span class="SimpleMath">\(Q\)</span> such that <span class="SimpleMath">\(Q A = H\)</span>.</p>
<p>The Smith Normal Form <span class="SimpleMath">\(S\)</span> of an integer matrix <span class="SimpleMath">\(A\)</span> is the unique equivalent diagonal form with <span class="SimpleMath">\(S_i\)</span> dividing <span class="SimpleMath">\(S_j\)</span> for <span class="SimpleMath">\(i < j\)</span>. There exist unimodular integer matrices <span class="SimpleMath">\(P, Q\)</span> such that <span class="SimpleMath">\(P A Q = S\)</span>.</p>
<p>All routines described in this section build on the <q>workhorse</q> routine <code class="func">NormalFormIntMat</code> (<a href="chap25_mj.html#X81FB746E82BE6CDA"><span class="RefLink">25.2-9</span></a>).</p>
<p><a id="X783CEC847D81F22A" name="X783CEC847D81F22A"></a></p>
<h5>25.2-1 TriangulizedIntegerMat</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ TriangulizedIntegerMat</code>( <var class="Arg">mat</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Computes an upper triangular form of a matrix with integer entries. It returns a mutable matrix in upper triangular form.</p>
<p><a id="X7DBE174E8625AFA5" name="X7DBE174E8625AFA5"></a></p>
<h5>25.2-2 TriangulizedIntegerMatTransform</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ TriangulizedIntegerMatTransform</code>( <var class="Arg">mat</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Computes an upper triangular form of a matrix with integer entries. It returns a record with a component <code class="code">normal</code> (an immutable matrix in upper triangular form) and a component <code class="code">rowtrans</code> that gives the transformations done to the original matrix to bring it into upper triangular form.</p>
<p><a id="X78CD40A687FE2311" name="X78CD40A687FE2311"></a></p>
<h5>25.2-3 TriangulizeIntegerMat</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ TriangulizeIntegerMat</code>( <var class="Arg">mat</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Changes <var class="Arg">mat</var> to be in upper triangular form. (The result is the same as that of <code class="func">TriangulizedIntegerMat</code> (<a href="chap25_mj.html#X783CEC847D81F22A"><span class="RefLink">25.2-1</span></a>), but <var class="Arg">mat</var> will be modified, thus using less memory.) If <var class="Arg">mat</var> is immutable an error will be triggered.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">m:=[[1,15,28],[4,5,6],[7,8,9]];;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">TriangulizedIntegerMat(m);</span>
[ [ 1, 15, 28 ], [ 0, 1, 1 ], [ 0, 0, 3 ] ]
<span class="GAPprompt">gap></span> <span class="GAPinput">n:=TriangulizedIntegerMatTransform(m);</span>
rec( normal := [ [ 1, 15, 28 ], [ 0, 1, 1 ], [ 0, 0, 3 ] ],
rank := 3, rowC := [ [ 1, 0, 0 ], [ 0, 1, 0 ], [ 0, 0, 1 ] ],
rowQ := [ [ 1, 0, 0 ], [ 1, -30, 17 ], [ -3, 97, -55 ] ],
rowtrans := [ [ 1, 0, 0 ], [ 1, -30, 17 ], [ -3, 97, -55 ] ],
signdet := 1 )
<span class="GAPprompt">gap></span> <span class="GAPinput">n.rowtrans*m=n.normal;</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">TriangulizeIntegerMat(m); m;</span>
[ [ 1, 15, 28 ], [ 0, 1, 1 ], [ 0, 0, 3 ] ]
</pre></div>
<p><a id="X8535AC327932B89F" name="X8535AC327932B89F"></a></p>
<h5>25.2-4 HermiteNormalFormIntegerMat</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ HermiteNormalFormIntegerMat</code>( <var class="Arg">mat</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>This operation computes the Hermite normal form of a matrix <var class="Arg">mat</var> with integer entries. It returns a immutable matrix in HNF.</p>
<p><a id="X7FDA78F979574ACC" name="X7FDA78F979574ACC"></a></p>
<h5>25.2-5 HermiteNormalFormIntegerMatTransform</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ HermiteNormalFormIntegerMatTransform</code>( <var class="Arg">mat</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>This operation computes the Hermite normal form of a matrix <var class="Arg">mat</var> with integer entries. It returns a record with components <code class="code">normal</code> (a matrix <span class="SimpleMath">\(H\)</span>) and <code class="code">rowtrans</code> (a matrix <span class="SimpleMath">\(Q\)</span>) such that <span class="SimpleMath">\(Q A = H\)</span>.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">m:=[[1,15,28],[4,5,6],[7,8,9]];;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">HermiteNormalFormIntegerMat(m);</span>
[ [ 1, 0, 1 ], [ 0, 1, 1 ], [ 0, 0, 3 ] ]
<span class="GAPprompt">gap></span> <span class="GAPinput">n:=HermiteNormalFormIntegerMatTransform(m);</span>
rec( normal := [ [ 1, 0, 1 ], [ 0, 1, 1 ], [ 0, 0, 3 ] ], rank := 3,
rowC := [ [ 1, 0, 0 ], [ 0, 1, 0 ], [ 0, 0, 1 ] ],
rowQ := [ [ -2, 62, -35 ], [ 1, -30, 17 ], [ -3, 97, -55 ] ],
rowtrans := [ [ -2, 62, -35 ], [ 1, -30, 17 ], [ -3, 97, -55 ] ],
signdet := 1 )
<span class="GAPprompt">gap></span> <span class="GAPinput">n.rowtrans*m=n.normal;</span>
true
</pre></div>
<p><a id="X87089FEC7FBEEA8F" name="X87089FEC7FBEEA8F"></a></p>
<h5>25.2-6 SmithNormalFormIntegerMat</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ SmithNormalFormIntegerMat</code>( <var class="Arg">mat</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>This operation computes the Smith normal form of a matrix <var class="Arg">mat</var> with integer entries. It returns a new immutable matrix in the Smith normal form.</p>
<p><a id="X839C1F9E87273A93" name="X839C1F9E87273A93"></a></p>
<h5>25.2-7 SmithNormalFormIntegerMatTransforms</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ SmithNormalFormIntegerMatTransforms</code>( <var class="Arg">mat</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>This operation computes the Smith normal form of a matrix <var class="Arg">mat</var> with integer entries. It returns a record with components <code class="code">normal</code> (a matrix <span class="SimpleMath">\(S\)</span>), <code class="code">rowtrans</code> (a matrix <span class="SimpleMath">\(P\)</span>), and <code class="code">coltrans</code> (a matrix <span class="SimpleMath">\(Q\)</span>) such that <span class="SimpleMath">\(P A Q = S\)</span>.</p>
<p><a id="X80EF38737F6D61DB" name="X80EF38737F6D61DB"></a></p>
<h5>25.2-8 DiagonalizeIntMat</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ DiagonalizeIntMat</code>( <var class="Arg">mat</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>This function changes <var class="Arg">mat</var> to its SNF. (The result is the same as that of <code class="func">SmithNormalFormIntegerMat</code> (<a href="chap25_mj.html#X87089FEC7FBEEA8F"><span class="RefLink">25.2-6</span></a>), but <var class="Arg">mat</var> will be modified, thus using less memory.) If <var class="Arg">mat</var> is immutable an error will be triggered.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">m:=[[1,15,28],[4,5,6],[7,8,9]];;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">SmithNormalFormIntegerMat(m);</span>
[ [ 1, 0, 0 ], [ 0, 1, 0 ], [ 0, 0, 3 ] ]
<span class="GAPprompt">gap></span> <span class="GAPinput">n:=SmithNormalFormIntegerMatTransforms(m);</span>
rec( colC := [ [ 1, 0, 0 ], [ 0, 1, 0 ], [ 0, 0, 1 ] ],
colQ := [ [ 1, 0, -1 ], [ 0, 1, -1 ], [ 0, 0, 1 ] ],
coltrans := [ [ 1, 0, -1 ], [ 0, 1, -1 ], [ 0, 0, 1 ] ],
normal := [ [ 1, 0, 0 ], [ 0, 1, 0 ], [ 0, 0, 3 ] ], rank := 3,
rowC := [ [ 1, 0, 0 ], [ 0, 1, 0 ], [ 0, 0, 1 ] ],
rowQ := [ [ -2, 62, -35 ], [ 1, -30, 17 ], [ -3, 97, -55 ] ],
rowtrans := [ [ -2, 62, -35 ], [ 1, -30, 17 ], [ -3, 97, -55 ] ],
signdet := 1 )
<span class="GAPprompt">gap></span> <span class="GAPinput">n.rowtrans*m*n.coltrans=n.normal;</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">DiagonalizeIntMat(m);m;</span>
[ [ 1, 0, 0 ], [ 0, 1, 0 ], [ 0, 0, 3 ] ]
</pre></div>
<p><a id="X81FB746E82BE6CDA" name="X81FB746E82BE6CDA"></a></p>
<h5>25.2-9 NormalFormIntMat</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ NormalFormIntMat</code>( <var class="Arg">mat</var>, <var class="Arg">options</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>This general operation for computation of various Normal Forms is probably the most efficient.</p>
<p>Options bit values:</p>
<dl>
<dt><strong class="Mark">0/1</strong></dt>
<dd><p>Triangular Form / Smith Normal Form.</p>
</dd>
<dt><strong class="Mark">2</strong></dt>
<dd><p>Reduce off diagonal entries.</p>
</dd>
<dt><strong class="Mark">4</strong></dt>
<dd><p>Row Transformations.</p>
</dd>
<dt><strong class="Mark">8</strong></dt>
<dd><p>Col Transformations.</p>
</dd>
<dt><strong class="Mark">16</strong></dt>
<dd><p>Destructive (the original matrix may be destroyed)</p>
</dd>
</dl>
<p>Compute a Triangular, Hermite or Smith form of the <span class="SimpleMath">\(n \times m\)</span> integer input matrix <span class="SimpleMath">\(A\)</span>. Optionally, compute <span class="SimpleMath">\(n \times n\)</span> and <span class="SimpleMath">\(m \times m\)</span> unimodular transforming matrices <span class="SimpleMath">\(Q, P\)</span> which satisfy <span class="SimpleMath">\(Q A = H\)</span> or <span class="SimpleMath">\(Q A P = S\)</span>.</p>
<p>Note option is a value ranging from 0 to 15 but not all options make sense (e.g., reducing off diagonal entries with SNF option selected already). If an option makes no sense it is ignored.</p>
<p>Returns a record with component <code class="code">normal</code> containing the computed normal form and optional components <code class="code">rowtrans</code> and/or <code class="code">coltrans</code> which hold the respective transformation matrix. Also in the record are components holding the sign of the determinant, <code class="code">signdet</code>, and the rank of the matrix, <code class="code">rank</code>.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">m:=[[1,15,28],[4,5,6],[7,8,9]];;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">NormalFormIntMat(m,0); # Triangular, no transforms</span>
rec( normal := [ [ 1, 15, 28 ], [ 0, 1, 1 ], [ 0, 0, 3 ] ],
rank := 3, signdet := 1 )
<span class="GAPprompt">gap></span> <span class="GAPinput">NormalFormIntMat(m,6); # Hermite Normal Form with row transforms</span>
rec( normal := [ [ 1, 0, 1 ], [ 0, 1, 1 ], [ 0, 0, 3 ] ], rank := 3,
rowC := [ [ 1, 0, 0 ], [ 0, 1, 0 ], [ 0, 0, 1 ] ],
rowQ := [ [ -2, 62, -35 ], [ 1, -30, 17 ], [ -3, 97, -55 ] ],
rowtrans := [ [ -2, 62, -35 ], [ 1, -30, 17 ], [ -3, 97, -55 ] ],
signdet := 1 )
<span class="GAPprompt">gap></span> <span class="GAPinput">NormalFormIntMat(m,13); # Smith Normal Form with both transforms</span>
rec( colC := [ [ 1, 0, 0 ], [ 0, 1, 0 ], [ 0, 0, 1 ] ],
colQ := [ [ 1, 0, -1 ], [ 0, 1, -1 ], [ 0, 0, 1 ] ],
coltrans := [ [ 1, 0, -1 ], [ 0, 1, -1 ], [ 0, 0, 1 ] ],
normal := [ [ 1, 0, 0 ], [ 0, 1, 0 ], [ 0, 0, 3 ] ], rank := 3,
rowC := [ [ 1, 0, 0 ], [ 0, 1, 0 ], [ 0, 0, 1 ] ],
rowQ := [ [ -2, 62, -35 ], [ 1, -30, 17 ], [ -3, 97, -55 ] ],
rowtrans := [ [ -2, 62, -35 ], [ 1, -30, 17 ], [ -3, 97, -55 ] ],
signdet := 1 )
<span class="GAPprompt">gap></span> <span class="GAPinput">last.rowtrans*m*last.coltrans;</span>
[ [ 1, 0, 0 ], [ 0, 1, 0 ], [ 0, 0, 3 ] ]
</pre></div>
<p><a id="X8221694D7C99197A" name="X8221694D7C99197A"></a></p>
<h5>25.2-10 AbelianInvariantsOfList</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ AbelianInvariantsOfList</code>( <var class="Arg">list</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>Given a list of nonnegative integers, this routine returns a sorted list containing the prime power factors of the positive entries in the original list, as well as all zeroes of the original list.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">AbelianInvariantsOfList([4,6,2,0,12]);</span>
[ 0, 2, 2, 3, 3, 4, 4 ]
</pre></div>
<p><a id="X80F6990983C979FB" name="X80F6990983C979FB"></a></p>
<h4>25.3 <span class="Heading">Determinant of an integer matrix</span></h4>
<p><a id="X787599E087F4C0BA" name="X787599E087F4C0BA"></a></p>
<h5>25.3-1 DeterminantIntMat</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ DeterminantIntMat</code>( <var class="Arg">mat</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Computes the determinant of an integer matrix using the same strategy as <code class="func">NormalFormIntMat</code> (<a href="chap25_mj.html#X81FB746E82BE6CDA"><span class="RefLink">25.2-9</span></a>). This method is faster in general for matrices greater than <span class="SimpleMath">\(20 \times 20\)</span> but quite a lot slower for smaller matrices. It therefore passes the work to the more general <code class="func">DeterminantMat</code> (<a href="chap24_mj.html#X8488D69A7ADDB4E2"><span class="RefLink">24.4-4</span></a>) for these smaller matrices.</p>
<p><a id="X79F2EFEC7C3EA80C" name="X79F2EFEC7C3EA80C"></a></p>
<h4>25.4 <span class="Heading">Decompositions</span></h4>
<p>For computing the decomposition of a vector of integers into the rows of a matrix of integers, with integral coefficients, one can use <span class="SimpleMath">\(p\)</span>-adic approximations, as follows.</p>
<p>Let <span class="SimpleMath">\(A\)</span> be a square integral matrix, and <span class="SimpleMath">\(p\)</span> an odd prime. The reduction of <span class="SimpleMath">\(A\)</span> modulo <span class="SimpleMath">\(p\)</span> is <span class="SimpleMath">\(\overline{A}\)</span>, its entries are chosen in the interval <span class="SimpleMath">\([ -(p-1)/2, (p-1)/2 ]\)</span>. If <span class="SimpleMath">\(\overline{A}\)</span> is regular over the field with <span class="SimpleMath">\(p\)</span> elements, we can form <span class="SimpleMath">\(A' = \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
<p class="center">\[
x_i = (b_i A') \bmod p, b_{{i+1}} = (b_i - x_i A) / p,
i = 0, 1, 2, \ldots .
\]</p>
<p>By induction, we get</p>
<p class="center">\[
p^{{i+1}} b_{{i+1}} + \left( \sum_{{j = 0}}^i p^j x_j \right) A = b.
\]</p>
<p>If there is an integral solution <span class="SimpleMath">\(x\)</span> then it is unique, and there is an index <span class="SimpleMath">\(l\)</span> such that <span class="SimpleMath">\(b_{{l+1}}\)</span> is zero and <span class="SimpleMath">\(x = \sum_{{j = 0}}^l p^j x_j\)</span>.</p>
<p>There are two useful generalizations of this idea. First, <span class="SimpleMath">\(A\)</span> need not be square; it is only necessary that there is a square regular matrix formed by a subset of columns of <span class="SimpleMath">\(A\)</span>. Second, <span class="SimpleMath">\(A\)</span> does not need to be integral; the entries may be cyclotomic integers as well, in this case one can replace each column of <span class="SimpleMath">\(A\)</span> 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 <span class="SimpleMath">\(A\)</span> and <span class="SimpleMath">\(b\)</span>.</p>
<p><strong class="pkg">GAP</strong> provides the following functions for this purpose (see also <code class="func">InverseMatMod</code> (<a href="chap24_mj.html#X7D8D1E0E83C7F872"><span class="RefLink">24.15-1</span></a>)).</p>
<p><a id="X7911A60384C511AB" name="X7911A60384C511AB"></a></p>
<h5>25.4-1 Decomposition</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ Decomposition</code>( <var class="Arg">A</var>, <var class="Arg">B</var>, <var class="Arg">depth</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>For a <span class="SimpleMath">\(m \times n\)</span> matrix <var class="Arg">A</var> of cyclotomics that has rank <span class="SimpleMath">\(m \leq n\)</span>, and a list <var class="Arg">B</var> of cyclotomic vectors, each of length <span class="SimpleMath">\(n\)</span>, <code class="func">Decomposition</code> tries to find integral solutions of the linear equation systems <code class="code"><var class="Arg">x</var> * <var class="Arg">A</var> = <var class="Arg">B</var>[i]</code>, by computing the <span class="SimpleMath">\(p\)</span>-adic series of hypothetical solutions.</p>
<p><code class="code">Decomposition( <var class="Arg">A</var>, <var class="Arg">B</var>, <var class="Arg">depth</var> )</code>, where <var class="Arg">depth</var> is a nonnegative integer, computes for each vector <code class="code"><var class="Arg">B</var>[i]</code> the initial part <span class="SimpleMath">\(\sum_{{k = 0}}^{\textit{depth}} x_k p^k\)</span>, with all <span class="SimpleMath">\(x_k\)</span> vectors of integers with entries bounded by <span class="SimpleMath">\(\pm (p-1)/2\)</span>. The prime <span class="SimpleMath">\(p\)</span> is set to 83 first; if the reduction of <var class="Arg">A</var> modulo <span class="SimpleMath">\(p\)</span> is singular, the next prime is chosen automatically.</p>
<p>A list <var class="Arg">X</var> is returned. If the computed initial part for <code class="code"><var class="Arg">x</var> * <var class="Arg">A</var> = <var class="Arg">B</var>[i]</code> <em>is</em> a solution, we have <code class="code"><var class="Arg">X</var>[i] = <var class="Arg">x</var></code>, otherwise <code class="code"><var class="Arg">X</var>[i] = fail</code>.</p>
<p>If <var class="Arg">depth</var> is not an integer then it must be the string <code class="code">"nonnegative"</code>. <code class="code">Decomposition( <var class="Arg">A</var>, <var class="Arg">B</var>, "nonnegative" )</code> assumes that the solutions have only nonnegative entries, and that the first column of <var class="Arg">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 class="Arg">depth</var> of iterations can be computed; the <code class="code">i</code>-th entry of the returned list is <code class="keyw">fail</code> if there <em>exists</em> no nonnegative integral solution of the system <code class="code"><var class="Arg">x</var> * <var class="Arg">A</var> = <var class="Arg">B</var>[i]</code>, and it is the solution otherwise.</p>
<p><em>Note</em> that the result is a list of <code class="keyw">fail</code> if <var class="Arg">A</var> has not full rank, even if there might be a unique integral solution for some equation system.</p>
<p><a id="X843A976787600F13" name="X843A976787600F13"></a></p>
<h5>25.4-2 LinearIndependentColumns</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ LinearIndependentColumns</code>( <var class="Arg">mat</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Called with a matrix <var class="Arg">mat</var>, <code class="code">LinearIndependentColumns</code> returns a maximal list of column positions such that the restriction of <var class="Arg">mat</var> to these columns has the same rank as <var class="Arg">mat</var>.</p>
<p><a id="X8285776B7DD86925" name="X8285776B7DD86925"></a></p>
<h5>25.4-3 PadicCoefficients</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ PadicCoefficients</code>( <var class="Arg">A</var>, <var class="Arg">Amodpinv</var>, <var class="Arg">b</var>, <var class="Arg">prime</var>, <var class="Arg">depth</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Let <var class="Arg">A</var> be an integral matrix, <var class="Arg">prime</var> a prime integer, <var class="Arg">Amodpinv</var> an inverse of <var class="Arg">A</var> modulo <var class="Arg">prime</var>, <var class="Arg">b</var> an integral vector, and <var class="Arg">depth</var> a nonnegative integer. <code class="func">PadicCoefficients</code> returns the list <span class="SimpleMath">\([ x_0, x_1, \ldots, x_l, b_{{l+1}} ]\)</span> describing the <var class="Arg">prime</var>-adic approximation of <var class="Arg">b</var> (see above), where <span class="SimpleMath">\(l = \textit{depth}\)</span> or <span class="SimpleMath">\(l\)</span> is minimal with the property that <span class="SimpleMath">\(b_{{l+1}} = 0\)</span>.</p>
<p><a id="X7F5C619B7A9C3EB9" name="X7F5C619B7A9C3EB9"></a></p>
<h5>25.4-4 IntegralizedMat</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IntegralizedMat</code>( <var class="Arg">A</var>[, <var class="Arg">inforec</var>] )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="func">IntegralizedMat</code> returns, for a matrix <var class="Arg">A</var> of cyclotomics, a record <code class="code">intmat</code> with components <code class="code">mat</code> and <code class="code">inforec</code>. Each family of algebraic conjugate columns of <var class="Arg">A</var> is encoded in a set of columns of the rational matrix <code class="code">intmat.mat</code> by replacing cyclotomics in <var class="Arg">A</var> by their coefficients w.r.t. an integral basis. <code class="code">intmat.inforec</code> is a record containing the information how to encode the columns.</p>
<p>If the only argument is <var class="Arg">A</var>, the value of the component <code class="code">inforec</code> is computed that can be entered as second argument <var class="Arg">inforec</var> in a later call of <code class="func">IntegralizedMat</code> with a matrix <var class="Arg">B</var> that shall be encoded compatibly with <var class="Arg">A</var>.</p>
<p><a id="X8512FB69824AE353" name="X8512FB69824AE353"></a></p>
<h5>25.4-5 DecompositionInt</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ DecompositionInt</code>( <var class="Arg">A</var>, <var class="Arg">B</var>, <var class="Arg">depth</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="func">DecompositionInt</code> does the same as <code class="func">Decomposition</code> (<a href="chap25_mj.html#X7911A60384C511AB"><span class="RefLink">25.4-1</span></a>), except that <var class="Arg">A</var> and <var class="Arg">B</var> must be integral matrices, and <var class="Arg">depth</var> must be a nonnegative integer.</p>
<p><a id="X839C6ABE829355F4" name="X839C6ABE829355F4"></a></p>
<h4>25.5 <span class="Heading">Lattice Reduction</span></h4>
<p><a id="X7D0FCEF8859E8637" name="X7D0FCEF8859E8637"></a></p>
<h5>25.5-1 LLLReducedBasis</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ LLLReducedBasis</code>( [<var class="Arg">L</var>, ]<var class="Arg">vectors</var>[, <var class="Arg">y</var>][, <var class="Arg">"linearcomb"</var>][, <var class="Arg">lllout</var>] )</td><td class="tdright">( function )</td></tr></table></div>
<p>provides an implementation of the <em>LLL algorithm</em> by Lenstra, Lenstra and Lovász (see <a href="chapBib_mj.html#biBLLL82">[LLJL82]</a>, <a href="chapBib_mj.html#biBPoh87">[Poh87]</a>). The implementation follows the description in <a href="chapBib_mj.html#biBCoh93">[Coh93, p. 94f.]</a>.</p>
<p><code class="func">LLLReducedBasis</code> returns a record whose component <code class="code">basis</code> is a list of LLL reduced linearly independent vectors spanning the same lattice as the list <var class="Arg">vectors</var>. <var class="Arg">L</var> must be a lattice, with scalar product of the vectors <var class="Arg">v</var> and <var class="Arg">w</var> given by <code class="code">ScalarProduct( <var class="Arg">L</var>, <var class="Arg">v</var>, <var class="Arg">w</var> )</code>. If no lattice is specified then the scalar product of vectors given by <code class="code">ScalarProduct( <var class="Arg">v</var>, <var class="Arg">w</var> )</code> is used.</p>
<p>In the case of the option <code class="code">"linearcomb"</code>, the result record contains also the components <code class="code">relations</code> and <code class="code">transformation</code>, with the following meaning. <code class="code">relations</code> is a basis of the relation space of <var class="Arg">vectors</var>, i.e., of vectors <var class="Arg">x</var> such that <code class="code"><var class="Arg">x</var> * <var class="Arg">vectors</var></code> is zero. <code class="code">transformation</code> gives the expression of the new lattice basis in terms of the old, i.e., <code class="code">transformation * <var class="Arg">vectors</var></code> equals the <code class="code">basis</code> component of the result.</p>
<p>Another optional argument is <var class="Arg">y</var>, the <q>sensitivity</q> of the algorithm, a rational number between <span class="SimpleMath">\(1/4\)</span> and <span class="SimpleMath">\(1\)</span> (the default value is <span class="SimpleMath">\(3/4\)</span>).</p>
<p>The optional argument <var class="Arg">lllout</var> is a record with the components <code class="code">mue</code> and <code class="code">B</code>, both lists of length <span class="SimpleMath">\(k\)</span>, with the meaning that if <var class="Arg">lllout</var> is present then the first <span class="SimpleMath">\(k\)</span> vectors in <var class="Arg">vectors</var> form an LLL reduced basis of the lattice they generate, and <code class="code"><var class="Arg">lllout</var>.mue</code> and <code class="code"><var class="Arg">lllout</var>.B</code> contain their scalar products and norms used internally in the algorithm, which are also present in the output of <code class="func">LLLReducedBasis</code>. So <var class="Arg">lllout</var> can be used for <q>incremental</q> calls of <code class="func">LLLReducedBasis</code>.</p>
<p>The function <code class="func">LLLReducedGramMat</code> (<a href="chap25_mj.html#X86D23EB885EDE60E"><span class="RefLink">25.5-2</span></a>) computes an LLL reduced Gram matrix.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">vectors:= [ [ 9, 1, 0, -1, -1 ], [ 15, -1, 0, 0, 0 ],</span>
<span class="GAPprompt">></span> <span class="GAPinput"> [ 16, 0, 1, 1, 1 ], [ 20, 0, -1, 0, 0 ],</span>
<span class="GAPprompt">></span> <span class="GAPinput"> [ 25, 1, 1, 0, 0 ] ];;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">LLLReducedBasis( vectors, "linearcomb" );</span>
rec( B := [ 5, 36/5, 12, 50/3 ],
basis := [ [ 1, 1, 1, 1, 1 ], [ 1, 1, -2, 1, 1 ],
[ -1, 3, -1, -1, -1 ], [ -3, 1, 0, 2, 2 ] ],
mue := [ [ ], [ 2/5 ], [ -1/5, 1/3 ], [ 2/5, 1/6, 1/6 ] ],
relations := [ [ -1, 0, -1, 0, 1 ] ],
transformation := [ [ 0, -1, 1, 0, 0 ], [ -1, -2, 0, 2, 0 ],
[ 1, -2, 0, 1, 0 ], [ -1, -2, 1, 1, 0 ] ] )
</pre></div>
<p><a id="X86D23EB885EDE60E" name="X86D23EB885EDE60E"></a></p>
<h5>25.5-2 LLLReducedGramMat</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ LLLReducedGramMat</code>( <var class="Arg">G</var>[, <var class="Arg">y</var>] )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="func">LLLReducedGramMat</code> provides an implementation of the <em>LLL algorithm</em> by Lenstra, Lenstra and Lovász (see <a href="chapBib_mj.html#biBLLL82">[LLJL82]</a>, <a href="chapBib_mj.html#biBPoh87">[Poh87]</a>). The implementation follows the description in <a href="chapBib_mj.html#biBCoh93">[Coh93, p. 94f.]</a>.</p>
<p>Let <var class="Arg">G</var> the Gram matrix of the vectors <span class="SimpleMath">\((b_1, b_2, \ldots, b_n)\)</span>; this means <var class="Arg">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>
<p><code class="func">LLLReducedGramMat</code> returns a record whose component <code class="code">remainder</code> is the Gram matrix of the LLL reduced basis corresponding to <span class="SimpleMath">\((b_1, b_2, \ldots, b_n)\)</span>. If <var class="Arg">G</var> is a lower triangular matrix then also the <code class="code">remainder</code> component of the result record is a lower triangular matrix.</p>
<p>The result record contains also the components <code class="code">relations</code> and <code class="code">transformation</code>, which have the following meaning.</p>
<p><code class="code">relations</code> is a basis of the space of vectors <span class="SimpleMath">\((x_1, x_2, \ldots, x_n)\)</span> such that <span class="SimpleMath">\(\sum_{{i = 1}}^n x_i b_i\)</span> is zero, and <code class="code">transformation</code> gives the expression of the new lattice basis in terms of the old, i.e., <code class="code">transformation</code> is the matrix <span class="SimpleMath">\(T\)</span> such that <span class="SimpleMath">\(T \cdot \textit{G} \cdot T^{tr}\)</span> is the <code class="code">remainder</code> component of the result.</p>
<p>The optional argument <var class="Arg">y</var> denotes the <q>sensitivity</q> of the algorithm, it must be a rational number between <span class="SimpleMath">\(1/4\)</span> and <span class="SimpleMath">\(1\)</span>; the default value is <span class="SimpleMath">\(\textit{y} = 3/4\)</span>.</p>
<p>The function <code class="func">LLLReducedBasis</code> (<a href="chap25_mj.html#X7D0FCEF8859E8637"><span class="RefLink">25.5-1</span></a>) computes an LLL reduced basis.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">g:= [ [ 4, 6, 5, 2, 2 ], [ 6, 13, 7, 4, 4 ],</span>
<span class="GAPprompt">></span> <span class="GAPinput"> [ 5, 7, 11, 2, 0 ], [ 2, 4, 2, 8, 4 ], [ 2, 4, 0, 4, 8 ] ];;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">LLLReducedGramMat( g );</span>
rec( B := [ 4, 4, 75/16, 168/25, 32/7 ],
mue := [ [ ], [ 1/2 ], [ 1/4, -1/8 ], [ 1/2, 1/4, -2/25 ],
[ -1/4, 1/8, 37/75, 8/21 ] ], relations := [ ],
remainder := [ [ 4, 2, 1, 2, -1 ], [ 2, 5, 0, 2, 0 ],
[ 1, 0, 5, 0, 2 ], [ 2, 2, 0, 8, 2 ], [ -1, 0, 2, 2, 7 ] ],
transformation := [ [ 1, 0, 0, 0, 0 ], [ -1, 1, 0, 0, 0 ],
[ -1, 0, 1, 0, 0 ], [ 0, 0, 0, 1, 0 ], [ -2, 0, 1, 0, 1 ] ] )
</pre></div>
<p><a id="X871DB00B803D5177" name="X871DB00B803D5177"></a></p>
<h4>25.6 <span class="Heading">Orthogonal Embeddings</span></h4>
<p><a id="X842280C2808FF05D" name="X842280C2808FF05D"></a></p>
<h5>25.6-1 OrthogonalEmbeddings</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ OrthogonalEmbeddings</code>( <var class="Arg">gram</var>[, <var class="Arg">"positive"</var>][, <var class="Arg">maxdim</var>] )</td><td class="tdright">( function )</td></tr></table></div>
<p>computes all possible orthogonal embeddings of a lattice given by its Gram matrix <var class="Arg">gram</var>, which must be a regular symmetric matrix of integers. In other words, all integral solutions <span class="SimpleMath">\(X\)</span> of the equation <span class="SimpleMath">\(X^{tr} \cdot X = \)</span><var class="Arg">gram</var> are calculated. The implementation follows the description in <a href="chapBib_mj.html#biBPle90">[Ple95]</a>.</p>
<p>Usually there are many solutions <span class="SimpleMath">\(X\)</span> but all their rows belong to a small set of vectors, so <code class="func">OrthogonalEmbeddings</code> returns the solutions encoded by a record with the following components.</p>
<dl>
<dt><strong class="Mark"><code class="code">vectors</code></strong></dt>
<dd><p>the list <span class="SimpleMath">\(L = [ x_1, x_2, \ldots, x_n ]\)</span> of vectors that may be rows of a solution, up to sign; these are exactly the vectors with the property <span class="SimpleMath">\(x_i \cdot \)</span><var class="Arg">gram</var><span class="SimpleMath">\(^{{-1}} \cdot x_i^{tr} \leq 1\)</span>, see <code class="func">ShortestVectors</code> (<a href="chap25_mj.html#X79A692B6819353D4"><span class="RefLink">25.6-2</span></a>),</p>
</dd>
<dt><strong class="Mark"><code class="code">norms</code></strong></dt>
<dd><p>the list of values <span class="SimpleMath">\(x_i \cdot \)</span><var class="Arg">gram</var><span class="SimpleMath">\(^{{-1}} \cdot x_i^{tr}\)</span>, and</p>
</dd>
<dt><strong class="Mark"><code class="code">solutions</code></strong></dt>
<dd><p>a list <span class="SimpleMath">\(S\)</span> of index lists; the <span class="SimpleMath">\(i\)</span>-th solution matrix is <span class="SimpleMath">\(L\)</span><code class="code">{ </code><span class="SimpleMath">\(S[i]\)</span><code class="code"> }</code>, so the dimension of the <var class="Arg">i</var>-th solution is the length of <span class="SimpleMath">\(S[i]\)</span>, and we have <var class="Arg">gram</var><span class="SimpleMath">\( = \sum_{{j \in S[i]}} x_j^{tr} \cdot x_j\)</span>,</p>
</dd>
</dl>
<p>The optional argument <code class="code">"positive"</code> will cause <code class="func">OrthogonalEmbeddings</code> to compute only vectors <span class="SimpleMath">\(x_i\)</span> with nonnegative entries. In the context of characters this is allowed (and useful) if <var class="Arg">gram</var> is the matrix of scalar products of ordinary characters.</p>
<p>When <code class="func">OrthogonalEmbeddings</code> is called with the optional argument <var class="Arg">maxdim</var> (a positive integer), only solutions up to dimension <var class="Arg">maxdim</var> are computed; this may accelerate the algorithm.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">b:= [ [ 3, -1, -1 ], [ -1, 3, -1 ], [ -1, -1, 3 ] ];;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">c:=OrthogonalEmbeddings( b );</span>
rec( norms := [ 1, 1, 1, 1/2, 1/2, 1/2, 1/2, 1/2, 1/2 ],
solutions := [ [ 1, 2, 3 ], [ 1, 6, 6, 7, 7 ], [ 2, 5, 5, 8, 8 ],
[ 3, 4, 4, 9, 9 ], [ 4, 5, 6, 7, 8, 9 ] ],
vectors := [ [ -1, 1, 1 ], [ 1, -1, 1 ], [ -1, -1, 1 ],
[ -1, 1, 0 ], [ -1, 0, 1 ], [ 1, 0, 0 ], [ 0, -1, 1 ],
[ 0, 1, 0 ], [ 0, 0, 1 ] ] )
<span class="GAPprompt">gap></span> <span class="GAPinput">c.vectors{ c.solutions[1] };</span>
[ [ -1, 1, 1 ], [ 1, -1, 1 ], [ -1, -1, 1 ] ]
</pre></div>
<p><var class="Arg">gram</var> may be the matrix of scalar products of some virtual characters. From the characters and the embedding given by the matrix <span class="SimpleMath">\(X\)</span>, <code class="func">Decreased</code> (<a href="chap72_mj.html#X8799AB967C58C0E9"><span class="RefLink">72.10-7</span></a>) may be able to compute irreducibles.</p>
<p><a id="X79A692B6819353D4" name="X79A692B6819353D4"></a></p>
<h5>25.6-2 ShortestVectors</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ ShortestVectors</code>( <var class="Arg">G</var>, <var class="Arg">m</var>[, <var class="Arg">"positive"</var>] )</td><td class="tdright">( function )</td></tr></table></div>
<p>Let <var class="Arg">G</var> be a regular matrix of a symmetric bilinear form, and <var class="Arg">m</var> a nonnegative integer. <code class="func">ShortestVectors</code> computes the vectors <span class="SimpleMath">\(x\)</span> that satisfy <span class="SimpleMath">\(x \cdot \textit{G} \cdot x^{tr} \leq \textit{m}\)</span>, and returns a record describing these vectors. The result record has the components</p>
<dl>
<dt><strong class="Mark"><code class="code">vectors</code></strong></dt>
<dd><p>list of the nonzero vectors <span class="SimpleMath">\(x\)</span>, but only one of each pair <span class="SimpleMath">\((x,-x)\)</span>,</p>
</dd>
<dt><strong class="Mark"><code class="code">norms</code></strong></dt>
<dd><p>list of norms of the vectors according to the Gram matrix <var class="Arg">G</var>.</p>
</dd>
</dl>
<p>If the optional argument <code class="code">"positive"</code> is entered, only those vectors <span class="SimpleMath">\(x\)</span> with nonnegative entries are computed.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">g:= [ [ 2, 1, 1 ], [ 1, 2, 1 ], [ 1, 1, 2 ] ];;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">ShortestVectors(g,4);</span>
rec( norms := [ 4, 2, 2, 4, 2, 4, 2, 2, 2 ],
vectors := [ [ -1, 1, 1 ], [ 0, 0, 1 ], [ -1, 0, 1 ], [ 1, -1, 1 ],
[ 0, -1, 1 ], [ -1, -1, 1 ], [ 0, 1, 0 ], [ -1, 1, 0 ],
[ 1, 0, 0 ] ] )
</pre></div>
<div class="chlinkprevnextbot"> <a href="chap0_mj.html">[Top of Book]</a> <a href="chap0_mj.html#contents">[Contents]</a> <a href="chap24_mj.html">[Previous Chapter]</a> <a href="chap26_mj.html">[Next Chapter]</a> </div>
<div class="chlinkbot"><span class="chlink1">Goto Chapter: </span><a href="chap0_mj.html">Top</a> <a href="chap1_mj.html">1</a> <a href="chap2_mj.html">2</a> <a href="chap3_mj.html">3</a> <a href="chap4_mj.html">4</a> <a href="chap5_mj.html">5</a> <a href="chap6_mj.html">6</a> <a href="chap7_mj.html">7</a> <a href="chap8_mj.html">8</a> <a href="chap9_mj.html">9</a> <a href="chap10_mj.html">10</a> <a href="chap11_mj.html">11</a> <a href="chap12_mj.html">12</a> <a href="chap13_mj.html">13</a> <a href="chap14_mj.html">14</a> <a href="chap15_mj.html">15</a> <a href="chap16_mj.html">16</a> <a href="chap17_mj.html">17</a> <a href="chap18_mj.html">18</a> <a href="chap19_mj.html">19</a> <a href="chap20_mj.html">20</a> <a href="chap21_mj.html">21</a> <a href="chap22_mj.html">22</a> <a href="chap23_mj.html">23</a> <a href="chap24_mj.html">24</a> <a href="chap25_mj.html">25</a> <a href="chap26_mj.html">26</a> <a href="chap27_mj.html">27</a> <a href="chap28_mj.html">28</a> <a href="chap29_mj.html">29</a> <a href="chap30_mj.html">30</a> <a href="chap31_mj.html">31</a> <a href="chap32_mj.html">32</a> <a href="chap33_mj.html">33</a> <a href="chap34_mj.html">34</a> <a href="chap35_mj.html">35</a> <a href="chap36_mj.html">36</a> <a href="chap37_mj.html">37</a> <a href="chap38_mj.html">38</a> <a href="chap39_mj.html">39</a> <a href="chap40_mj.html">40</a> <a href="chap41_mj.html">41</a> <a href="chap42_mj.html">42</a> <a href="chap43_mj.html">43</a> <a href="chap44_mj.html">44</a> <a href="chap45_mj.html">45</a> <a href="chap46_mj.html">46</a> <a href="chap47_mj.html">47</a> <a href="chap48_mj.html">48</a> <a href="chap49_mj.html">49</a> <a href="chap50_mj.html">50</a> <a href="chap51_mj.html">51</a> <a href="chap52_mj.html">52</a> <a href="chap53_mj.html">53</a> <a href="chap54_mj.html">54</a> <a href="chap55_mj.html">55</a> <a href="chap56_mj.html">56</a> <a href="chap57_mj.html">57</a> <a href="chap58_mj.html">58</a> <a href="chap59_mj.html">59</a> <a href="chap60_mj.html">60</a> <a href="chap61_mj.html">61</a> <a href="chap62_mj.html">62</a> <a href="chap63_mj.html">63</a> <a href="chap64_mj.html">64</a> <a href="chap65_mj.html">65</a> <a href="chap66_mj.html">66</a> <a href="chap67_mj.html">67</a> <a href="chap68_mj.html">68</a> <a href="chap69_mj.html">69</a> <a href="chap70_mj.html">70</a> <a href="chap71_mj.html">71</a> <a href="chap72_mj.html">72</a> <a href=" | |
