<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="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="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.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.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="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="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="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, ..., 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 ⋅ 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>
<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.html#X81FB746E82BE6CDA"><span class="RefLink">25.2-9</span></a>).</p>
<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>
<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>
<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.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="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>
<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="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>
<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>
<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.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="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">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 × m</span> integer input matrix <span class="SimpleMath">A</span>. Optionally, compute <span class="SimpleMath">n × n</span> and <span class="SimpleMath">m × 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="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="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.html#X81FB746E82BE6CDA"><span class="RefLink">25.2-9</span></a>). This method is faster in general for matrices greater than <span class="SimpleMath">20 × 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.html#X8488D69A7ADDB4E2"><span class="RefLink">24.4-4</span></a>) for these smaller matrices.</p>
<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">overlineA</span>, its entries are chosen in the interval <span class="SimpleMath">[ -(p-1)/2, (p-1)/2 ]</span>. If <span class="SimpleMath">overlineA</span> is regular over the field with <span class="SimpleMath">p</span> elements, we can form <spanclass="SimpleMath">A' = overlineA^{-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="pcenter">x_i = (b_i A') mod p, b_{i+1} = (b_i - x_i A) / p, i = 0, 1, 2, ... .
<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 = ∑_{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.html#X7D8D1E0E83C7F872"><span class="RefLink">24.15-1</span></a>)).</p>
<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 × n</span> matrix <var class="Arg">A</var> of cyclotomics that has rank <span class="SimpleMath">m ≤ 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">∑_{k = 0}^<var class="Arg">depth</var> x_k p^k</span>, with all <span class="SimpleMath">x_k</span> vectors of integers with entries bounded by <span class="SimpleMath">± (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>
<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>
<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, ..., 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 = <var class="Arg">depth</var></span> or <span class="SimpleMath">l</span> is minimal with the property that <span class="SimpleMath">b_{l+1} = 0</span>.</p>
<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>
<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.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>
<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.html#biBLLL82">[LLJL82]</a>, <a href="chapBib.html#biBPoh87">[Poh87]</a>). The implementation follows the description in <a href="chapBib.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.html#X86D23EB885EDE60E"><span class="RefLink">25.5-2</span></a>) computes an LLL reduced Gram matrix.</p>
<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.html#biBLLL82">[LLJL82]</a>, <a href="chapBib.html#biBPoh87">[Poh87]</a>). The implementation follows the description in <a href="chapBib.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, ..., 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, ..., 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, ..., x_n)</span> such that <span class="SimpleMath">∑_{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 ⋅ <var class="Arg">G</var> ⋅ 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"><var class="Arg">y</var> = 3/4</span>.</p>
<p>The function <code class="func">LLLReducedBasis</code> (<a href="chap25.html#X7D0FCEF8859E8637"><span class="RefLink">25.5-1</span></a>) computes an LLL reduced basis.</p>
<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 ⋅ X =</span><var class="Arg">gram</var> are calculated. The implementation follows the description in <a href="chapBib.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, ..., 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 ⋅</span><var class="Arg">gram</var><span class="SimpleMath">^{-1} ⋅ x_i^tr ≤ 1</span>, see <code class="func">ShortestVectors</code> (<a href="chap25.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 ⋅</span><var class="Arg">gram</var><span class="SimpleMath">^{-1} ⋅ 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">= ∑_{j ∈ S[i]} x_j^tr ⋅ 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 <varclass="Arg">maxdim</var> (a positive integer), only solutions up to dimension <var class="Arg">maxdim</var> are computed; this may accelerate the algorithm.</p>
<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.html#X8799AB967C58C0E9"><span class="RefLink">72.10-7</span></a>) may be able to compute irreducibles.</p>
<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 ⋅ <var class="Arg">G</var> ⋅ x^tr ≤ <var class="Arg">m</var></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>
Die Informationen auf dieser Webseite wurden
nach bestem Wissen sorgfältig zusammengestellt. Es wird jedoch weder Vollständigkeit, noch Richtigkeit,
noch Qualität der bereit gestellten Informationen zugesichert.
Bemerkung:
Die farbliche Syntaxdarstellung ist noch experimentell.
