<h4>6.1 <span class="Heading">Semi echelonised bases and cleaning</span></h4>
<p>A semi echelonised basis is a record with the following components: <code class="code">vectors</code> is a list of vectors of equal length, optionally (and optimally) they can be wrapped to a matrix. <code class="code">pivots</code> is a list of integers. The number <span class="SimpleMath">\(i\)</span> in position <span class="SimpleMath">\(j\)</span> indicates that the <span class="SimpleMath">\(j\)</span>th vector in <code class="code">vectors</code> has a one in column number <span class="SimpleMath">\(i\)</span> and all vectors with a number bigger than <span class="SimpleMath">\(i\)</span> in <code class="code">vectors</code> have a zero in column number <span class="SimpleMath">\(i\)</span>.</p>
<p>Note that for technical reasons another component <code class="code">helper</code> is bound containing a <code class="code">cvec</code> of length <span class="SimpleMath">\(1\)</span> over the same field.</p>
<p>Note further that the output of the <strong class="pkg">GAP</strong> library operation <code class="func">SemiEchelonMat</code> (<a href="../../../doc/ref/chap24_mj.html#X7D5D6BD07B7E981B"><span class="RefLink">Reference: SemiEchelonMat</span></a>) is not compatible to this setup, because it contains a component <code class="code">heads</code> that contains at position <spanclass="SimpleMath">\(i\)</span>, if nonzero, the number of the row for that the pivot element is in column <span class="SimpleMath">\(i\)</span>.</p>
<p>The argument <var class="Arg">b</var> must be a semi echelonised basis. This operation returns a (mutable) matrix whose rows are the basis vectors.</p>
<p>This is the basic operation for cleaning with a semi echelonised basis <var class="Arg">b</var>. The vector <var class="Arg">v</var> is cleaned with the vectors in the semi echelonised basis. The function returns <code class="code">true</code> if <var class="Arg">v</var> lies in the span of <var class="Arg">b</var> and false otherwise.</p>
<p>The boolean value <var class="Arg">extend</var> indicates, whether the basis should be extended in the latter case by the newly cleaned vector.</p>
<p>The argument <var class="Arg">dec</var> is either <code class="code">fail</code> in which case it is not used or a vector over the same field as <var class="Arg">v</var> that is at least as long as the number <span class="SimpleMath">\(n\)</span> of vectors in <var class="Arg">b</var> (plus one if <var class="Arg">extend</var> is <code class="code">true</code>). In this case, the first <span class="SimpleMath">\(n\)</span> components of <var class="Arg">dec</var> are changed such that <span class="SimpleMath">\(\sum_{{i=1}}^{n} \textit{dec}_i \textit{b}_i\)</span>. If <var class="Arg">extend</var> is <code class="code">true</code> and <var class="Arg">v</var> is not contained in the span of the vectors in <var class="Arg">b</var> and <var class="Arg">dec</var> is a vector, then the first <span class="SimpleMath">\(n+1\)</span> components of <var class="Arg">dec</var> are changed such that <span class="SimpleMath">\(\textit{v} = \sum_{{i=1}}^{n+1} \textit{dec}_i \textit{b}_i\)</span>.</p>
<p>Turns the output <var class="Arg">b</var> of <code class="func">SemiEchelonMat</code> (<a href="../../../doc/ref/chap24_mj.html#X7D5D6BD07B7E981B"><span class="RefLink">Reference: SemiEchelonMat</span></a>) into a valid semi echelonised basis in the sense of the <strong class="pkg">cvec</strong> package. This means that the component <code class="code">pivots</code> is calculated from the component <code class="code">heads</code>. Use this function only if absolutely necessary. Instead, directly invoke <code class="func">SemiEchelonBasisMutable</code> (<a href="chap6_mj.html#X82A37BC982B1D8CA"><span class="RefLink">6.1-6</span></a>) on the original matrix.</p>
<p>The argument <var class="Arg">m</var> must be a <code class="code">cmat</code>. This method calculates a semi echelonised basis for the row space of <var class="Arg">m</var>.</p>
<p>There are a number of similar operations the names of which are derived from <code class="func">SemiEchelonBasisMutable</code> by appending single letters: The letters <q>P</q>, <q>T</q> and <q>X</q> are modifiers and there are operations for most of the <span class="SimpleMath">\(8\)</span> combinations of those letters being present or not respectively. Always give the present letters in alphabetical order.</p>
<p>The <q>X</q> indicates, that the input matrix may be destroyed, that is, the rows of <var class="Arg">m</var> will be changed and the very same objects be used in the semi echelonised result basis.</p>
<p>The <q>T</q> indicates, that the transformation is calculated, that is, the resulting record <code class="code">r</code> will have a component <code class="code">coeffs</code>, such that <code class="code">r.coeffs * <var class="Arg">m</var></code> is equal to <code class="code">r.vectors</code> component of the semi echelonised result. Further, with given letter <q>T</q> there will be a component <code class="code">relations</code> which is a basis for the (left) nullspace of <var class="Arg">m</var>.</p>
<p>The <q>P</q> indicates, that a component <code class="code">r.p</code> is calculated such that <codeclass="code">r.p * r.vectors</code> is the original matrix <var class="Arg">m</var>.</p>
<p>Currently the variants with <q>P</q> and <q>T</q> both present are not implement because they will probably not be very useful.</p>
<p>Same as <code class="func">SemiEchelonBasisMutable</code> (<a href="chap6_mj.html#X82A37BC982B1D8CA"><span class="RefLink">6.1-6</span></a>) but destructive in <var class="Arg">m</var>.</p>
<p>Same as <code class="func">SemiEchelonBasisMutable</code> (<a href="chap6_mj.html#X82A37BC982B1D8CA"><span class="RefLink">6.1-6</span></a>) but in addition stores the transformation, see <code class="func">SemiEchelonBasisMutable</code> (<a href="chap6_mj.html#X82A37BC982B1D8CA"><span class="RefLink">6.1-6</span></a>).</p>
<p>Same as <code class="func">SemiEchelonBasisMutableT</code> (<a href="chap6_mj.html#X8309FC85858FC96B"><span class="RefLink">6.1-8</span></a>) but destructive in <var class="Arg">m</var>.</p>
<p>Same as <code class="func">SemiEchelonBasisMutable</code> (<a href="chap6_mj.html#X82A37BC982B1D8CA"><span class="RefLink">6.1-6</span></a>) but in addition stores the inverse transformation, see <code class="func">SemiEchelonBasisMutable</code> (<a href="chap6_mj.html#X82A37BC982B1D8CA"><span class="RefLink">6.1-6</span></a>).</p>
<p>Same as <code class="func">SemiEchelonBasisMutableP</code> (<a href="chap6_mj.html#X837F20C4831FA08E"><span class="RefLink">6.1-10</span></a>) but destructive in <var class="Arg">m</var>.</p>
<p>Returns a <code class="code">cmat</code> the rows of which are a basis of the (left) nullspace of the <code class="code">cmat</code> <var class="Arg">m</var>. Internally, <code class="func">SemiEchelonBasisMutableT</code> (<a href="chap6_mj.html#X8309FC85858FC96B"><span class="RefLink">6.1-8</span></a>) is used and the component <code class="code">relations</code> of the result is returned. The result is mutable, which is the reason for the introduction of a new operation besides <code class="func">NullspaceMat</code> (<a href="../../../doc/ref/chap24_mj.html#X7DA0D5887DB12DC4"><span class="RefLink">Reference: NullspaceMat</span></a>).</p>
<p>Same as <code class="func">MutableNullspaceMat</code> (<a href="chap6_mj.html#X7E5C2C297CAAE3FB"><span class="RefLink">6.1-12</span></a>) but destructive in <var class="Arg">m</var>.</p>
<p>Calculates the characteristic polynomial of the <code class="code">cmat</code> <var class="Arg">m</var> over its base field. Because during the calculations the polynomial automatically comes as a product of some not necessarily irreducible factors, the result is returned in a record with two components. The <code class="code">poly</code> component contains the full characteristic polynomial. The <code class="code">factors</code> component contains a list of not necessarily irreducibly factors the product of which is the characteristic polynomial. If an indeterminate number is given as second argument, the polynomials are written in that indeterminate, otherwise in the first indeterminate over the base field.</p>
<p>Calculates the characteristic polynomial of the <code class="code">cmat</code> <var class="Arg">m</var> over its base field. The result is a list of irreducible factors of the characteristic polynomial of <var class="Arg">m</var>, the product of which is the characteristic polynomial. Because during the calculations the polynomial automatically comes as a product of some not necessarily irreducible factors, this is more efficient than just calculating the characteristic polynomial and then factoring it. If an indeterminate number is given as second argument, the polynomials are written in that indeterminate, otherwise in the first indeterminate over the base field.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ MinimalPolynomialOfMatrix</code>( <var class="Arg">m</var>[, <var class="Arg">indetnr</var>] )</td><td class="tdright">( method )</td></tr></table></div>
<p>Returns: a polynomial over the base field of <var class="Arg">m</var></p>
<p>Calculates the minimal polynomial of the <code class="code">cmat</code> <var class="Arg">m</var> over its base field. The polynomial is returned. If an indeterminate number is given as second argument, the polynomials are written in that indeterminate, otherwise in the first indeterminate over the base field.</p>
<p>Calculates the characteristic and minimal polynomial of the <code class="code">cmat</code> <var class="Arg">m</var> over its base field. Because during the calculation of the minimal polynomial the characteristic polynomial is calculated anyway, the result is returned in a record with five components: The <code class="code">charpoly</code> component contains the full characteristic polynomial. The <code class="code">irreds</code> component contains the set of irreducible factors of the characteristic polynomial as a list. The <code class="code">mult</code> component contains a corresponding list of multiplicities, that is in position <span class="SimpleMath">\(i\)</span> is the multiplicity of the irreducible factor number <span class="SimpleMath">\(i\)</span> in the characteristic polynomial. The component <code class="code">minpoly</code> contains the minimal polynomial and the component <code class="code">multmin</code> the corresponding multiplicities of the irreducible factors of the characteristic polynomial in the minimal polynomial. If an indeterminate number is given as second argument, the polynomials are written in that indeterminate, otherwise in the first indeterminate over the base field.</p>
<p>This method calculates the characteristic and minimal polynomials of the row list matrix <varclass="Arg">m</var> over its base domain. It uses the Monte Carlo algorithm by Neunhoeffer and Praeger. The second argument <var class="Arg">prob</var> is an upper bound for the error probability, it can be <span class="SimpleMath">\(0\)</span> in which case a deterministic verification is done. The optional argument <var class="Arg">indetnr</var> is the number of the indeterminate over the base domain to be used to express polynomials.</p>
<p>The result is a record with the following components bound: The component <code class="code">charpoly</code> is the characteristic polynomial which is guaranteed to be correct. The component <code class="code">minpoly</code> is always a divisor of the minimal polynomial and usually is equal to it. See below for details. The component <code class="code">irreds</code> is a sorted list of the irreducible factors of the characteristic polynomial. The component <code class="code">mult</code> is a corresponding list of the same length containing the multiplicities of these irreducible factors in the characteristic polynomial. The component <code class="code">minmult</code> is a corresponding list of the same length containing the multiplicities of these irreducible factors in the polynomial given in <code class="code">minpoly</code>. The component <code class="code">proof</code> is set to <code class="code">true</code> if the result is proved to be correct, which can happen even if <var class="Arg">prob</var> was non-zero (for example in the case of a cyclic matrix). The component <code class="code">iscyclic</code> is set to <code class="code">true</code> if and only if the minimal polynomial is equal to the characteristic polynomial. The component <code class="code">prob</code> is set to the probability given in <var class="Arg">prob</var>, if that was zero then it is set to <span class="SimpleMath">\(1/10000\)</span> but <code class="code">proof</code> will be <code class="code">true</code>. The components <code class="code">A</code>, <code class="code">B</code> and <code class="code">S</code> describe a base change for <var class="Arg">m</var> to a sparse form which is obtained as a byproduct. <code class="code">S</code> is a semi echelonised basis which was obtained by a spin-up computation with <var class="Arg">m</var> and if <span class="SimpleMath">\(Y\)</span> is the sparse basis then <span class="SimpleMath">\(Y = A \cdot S\)</span> and <span class="SimpleMath">\(B=A^{-1}\)</span>.</p>
<p>The given result for the minimal polynomial could be a proper divisor of the real minimal polynomial if <var class="Arg">prob</var> was non-zero, however, the probability for this outcome is guaranteed to be less than or equal to <var class="Arg">prob</var>. Note that it is always guaranteed that all irreducible factors of the minimal polynomial are actually present, it can only happen that the multiplicities are too small.</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.
