<h3>6 <span class="Heading">Linear machines and elements</span></h3>
<p><em>Linear</em> machines are a special class of FR machines, in which the stateset <span class="SimpleMath">Q</span> and the alphabet <span class="SimpleMath">X</span> are vector spaces over a field <span class="SimpleMath">Bbbk</span>, and the transition map <span class="SimpleMath">ϕ: Q⊗ X-> X⊗ Q</span> is a linear map; furthermore, there is a functional <span class="SimpleMath">π:Q->Bbbk</span> called the <em>output</em>.</p>
<p>As before, a choice of initial state <span class="SimpleMath">q∈ Q</span> induces a linear map <span class="SimpleMath">q:T(X)-> T(X)</span>, where <span class="SimpleMath">T(X)=⨁ X^⊗ n</span> is the tensor algebra generated by <span class="SimpleMath">X</span>. This map is defined as follows: given <span class="SimpleMath">x=x_1⊗dots⊗ x_n∈ T(X)</span>, rewrite <span class="SimpleMath">q⊗ x</span> as a sum of expressions of the form <span class="SimpleMath">y⊗ r</span> with <span class="SimpleMath">y∈ T(X)</span> and <span class="SimpleMath">r∈ Q</span>; then <span class="SimpleMath">q</span>, by definition, maps <span class="SimpleMath">x</span> to the sum of the <span class="SimpleMath">π(r)y</span>.</p>
<p>There are two sorts of linear machines: <em>vector machines</em>, for which the state space is a finite-dimensional vector space over a field; and <em>algebra machines</em>, for which the state space is a free algebra in a finite set of variables.</p>
<p>In a vector machine, the transition and output maps are stored as a matrix and a vector respectively. Minimization algorithms are implemented, as for Mealy machines.</p>
<p>In an algebra machine, the transition and output maps are stored as words in the algebra. These machines are natural extensions of group/monoid/semigroup machines.</p>
<p>Linear elements are given by a linear machine and an initial state. They can be added and multiplied, and act on the tensor algebra of the alphabet, admitting natural representations as matrices.</p>
<h4>6.1 <span class="Heading">Methods and operations for <code class="code">LinearFRMachine</code>s and <code class="code">LinearFRElement</code>s</span></h4>
<p>This function constructs a new linear machine or element, of vector type.</p>
<p><var class="Arg">transitions</var> is a matrix of matrices; for <code class="code">a,b</code> indices of basis vectors of the alphabet, <code class="code">transitions[a][b]</code> is a square matrix indexed by the stateset, which is the transition to be effected on the stateset upon the output <span class="SimpleMath">a-> b</span>.</p>
<p>The optional last argument <var class="Arg">category</var> specifies a category (<code class="func">IsAssociativeElement</code> (<a href="../../../doc/ref/chap31.html#X7979AFAA80FF795A"><span class="RefLink">Reference: IsAssociativeElement</span></a>), <code class="func">IsJacobianElement</code> (<a href="../../../doc/ref/chap31.html#X796957D0805A0221"><span class="RefLink">Reference: IsJacobianElement</span></a>),...) to which the new element should belong.</p>
<p><var class="Arg">output</var> and <var class="Arg">init</var> are vectors in the stateset.</p>
<p>In the "NC" version, no tests are performed to check that the arguments contain values within bounds, or even of the right type (beyond the simple checking performed by <strong class="pkg">GAP</strong>'s method selection algorithms). The first argument should be the family of the resulting object. These "NC" methods are mainly used internally by the package.
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">M := VectorMachine(Rationals,[[[[1]],[[2]]],[[[3]],[[4]]]],[1]);</span>
<Linear machine on alphabet Rationals^2 with 1-dimensional stateset>
<span class="GAPprompt">gap></span> <span class="GAPinput">Display(M);</span>
Rationals | 1 | 2 |
-----------+---+---+
1 | 1 | 2 |
-----------+---+---+
2 | 3 | 4 |
-----------+---+---+ Output: 1
<span class="GAPprompt">gap></span> <span class="GAPinput">A := VectorElement(Rationals,[[[[1]],[[2]]],[[[3]],[[4]]]],[1],[1]);</span>
<Linear element on alphabet Rationals^2 with 1-dimensional stateset>
<span class="GAPprompt">gap></span> <span class="GAPinput">Display(Activity(A,2));</span>
[ [ 1, 2, 2, 4 ],
[ 3, 4, 6, 8 ],
[ 3, 6, 4, 8 ],
[ 9, 12, 12, 16 ] ]
<span class="GAPprompt">gap></span> <span class="GAPinput">DecompositionOfFRElement(A);</span>
[ [ <Linear element on alphabet Rationals^2 with 1-dimensional stateset>,
<Linear element on alphabet Rationals^2 with 1-dimensional stateset> ],
[ <Linear element on alphabet Rationals^2 with 1-dimensional stateset>,
<Linear element on alphabet Rationals^2 with 1-dimensional stateset> ] ]
<span class="GAPprompt">gap></span> <span class="GAPinput">last=[[A,2*A],[3*A,4*A]];</span>
true
</pre></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ AssociativeObject</code>( <var class="Arg">x</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Returns: An associative object related to <var class="Arg">x</var>.</p>
<p>If <var class="Arg">x</var> belongs to a family that admits a non-associative and an associative product, and the product of <var class="Arg">x</var> is non-associative, this function returns the object corresponding to <var class="Arg">x</var>, but with associative product.</p>
<p>A typical example is that <var class="Arg">x</var> is a derivation of a vector space. The product of derivations is <span class="SimpleMath">a∘ b-b∘ a</span>, and is not associative; but derivations are endomorphisms of the vector space, and as such can be composed associatively.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">A := VectorElement(Rationals,[[[[0]],[[1]]],[[[1]],[[0]]]],[1],[1],IsJacobianElement);</span>
<Linear element on alphabet Rationals^2 with 1-dimensional stateset->
<span class="GAPprompt">gap></span> <span class="GAPinput">A^2;</span>
<Zero linear element on alphabet Rationals^2->
<span class="GAPprompt">gap></span> <span class="GAPinput">AssociativeObject(A)^2;</span>
<Identity linear element on alphabet Rationals^2>
</pre></div>
<p>This function constructs a new linear machine or element, of algebra type.</p>
<p><var class="Arg">ring</var> is a free associative algebra, optionally with one. <var class="Arg">domain</var> is the vector space on which the alphabet is defined. If absent, this argument defaults to the <code class="func">LeftActingDomain</code> (<a href="../../../doc/ref/chap57.html#X86F070E0807DC34E"><span class="RefLink">Reference: LeftActingDomain</span></a>) of <var class="Arg">ring</var>.</p>
<p><var class="Arg">transitions</var> is a list of matrices; for each generator number <span class="SimpleMath">i</span> of <var class="Arg">ring</var>, the matrix <code class="code">transitions[i]</code>, with entries in <var class="Arg">ring</var>, describes the decomposition of generator <span class="SimpleMath">i</span> as a matrix.</p>
<p><var class="Arg">output</var> is a vector over <var class="Arg">domain</var>, and <var class="Arg">init</var> is a vector over <var class="Arg">ring</var>.</p>
<p>In the "NC" version, no tests are performed to check that the arguments contain values within bounds, or even of the right type (beyond the simple checking performed by <strong class="pkg">GAP</strong>'s method selection algorithms). The first argument should be the family of the resulting object. These "NC" methods are mainly used internally by the package.
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ Transition</code>( <var class="Arg">m</var>, <var class="Arg">s</var>, <var class="Arg">a</var>, <var class="Arg">b</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Returns: An element of <var class="Arg">m</var>'s stateset.
<p>This function returns the state reached by <var class="Arg">m</var> when started in state <var class="Arg">s</var> and performing output <span class="SimpleMath">a-> b</span>.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ Transitions</code>( <var class="Arg">m</var>, <var class="Arg">s</var>, <var class="Arg">a</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Returns: An vector of elements of <var class="Arg">m</var>'s stateset.
<p>This function returns the state reached by <var class="Arg">m</var> when started in state <var class="Arg">s</var> and receiving input <var class="Arg">a</var>. The output is a vector, indexed by the alphabet's basis, of output states.
<p>The first form returns the entry at position <span class="SimpleMath">(i,j)</span> of <var class="Arg">e</var>'s decomposition. Both of i,j are lists. The second form returns the output of the state.
<p>In particular, <code class="code">e=NestedMatrixState(e,[],[])</code>, and <br /> <code class="code">Activity(e,1)[i][j]=NestedMatrixCoefficient(e,[i],[j])</code>, and <br /> <code class="code">DecompositionOfFRElement(e,1)[i][j]=NestedMatrixState(e,[i],[j])</code>.</p>
<p><code class="code">Activity(m,i)</code> returns an <span class="SimpleMath">n^i× n^i</span> matrix describing the action on the <span class="SimpleMath">i</span>-fold tensor power of the alphabet. This matrix can also be returned as a sparse matrix, and this is performed by this command. A sparse matrix is described as a list of expressions of the form <code class="code">[[i,j],c]</code>, representing the elementary matrix with entry <span class="SimpleMath">c</span> at position <span class="SimpleMath">(i,j)</span>. The activity matrix is then the sum of these elementary matrices.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ Activities</code>( <var class="Arg">m</var>, <var class="Arg">i</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Returns: Activities of <var class="Arg">m</var> on the first <var class="Arg">i</var> levels.</p>
<p><code class="code">Activity(m,i)</code> returns an <span class="SimpleMath">n^i× n^i</span> matrix describing the action on the <span class="SimpleMath">i</span>-fold tensor power of the alphabet. This command returns <code class="code">List([0..i-1],j->Activity(m,j))</code>.</p>
<p>Since linear FR elements may be interpreted as infinite matrices, it makes sense to transpose them, test whether they're symmetric, antisymmetric, diagonal, or triangular.
<p>Given a linear element <var class="Arg">e</var>, this command attempts to find a decomposition of the form <span class="SimpleMath">e=LDU</span>, where <span class="SimpleMath">L</span> is lower triangular, <span class="SimpleMath">D</span> is diagonal, and <span class="SimpleMath">U</span> is upper triangular (see <code class="func">IsLowerTriangularFRElement</code> (<a href="chap6.html#X8136C21885019A4A"><span class="RefLink">6.1-10</span></a>) etc.).</p>
<p>The result is returned thas a list with entries <span class="SimpleMath">L,D,U</span>. Note that it is not guaranteed to succeed. For more examples, see Section <a href="chap9.html#X7989134C83AF38AE"><span class="RefLink">9.4</span></a>.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">List([0..7],s->List([0..7],t->E(4)^ValuationInt(Binomial(s+t,s),2)));;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">A := GuessVectorElement(last);</span>
<Linear element on alphabet GaussianRationals^2 with 2-dimensional stateset>
<span class="GAPprompt">gap></span> <span class="GAPinput">LDU := LDUDecompositionFRElement(A);</span>
[ <Linear element on alphabet GaussianRationals^2 with 4-dimensional stateset>,
<Linear element on alphabet GaussianRationals^2 with 3-dimensional stateset>,
<Linear element on alphabet GaussianRationals^2 with 4-dimensional stateset> ]
<span class="GAPprompt">gap></span> <span class="GAPinput">IsLowerTriangularFRElement(LDU[1]); IsDiagonalFRElement(LDU[2]);</span>
true
true
<span class="GAPprompt">gap></span> <span class="GAPinput">TransposedFRElement(LDU[1])=LDU[3];</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">Product(LDU)=A;</span>
true
</pre></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ GuessVectorElement</code>( <var class="Arg">m</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: A vector element that acts like <var class="Arg">m</var>.</p>
<p>The arguments to this function include a matrix or list of matrices, and an optional ring. The return value is a vector element, over the ring if it was specified, that acts like the sequence of matrices.</p>
<p>If a single matrix is specified, then it is assumed to represent a convergent element (see <codeclass="func">IsConvergent</code> (<a href="chap6.html#X7EF5B7417AE6B3F8"><span class="RefLink">6.1-9</span></a>)).</p>
<p>This function returns <code class="keyw">fail</code> if it believes that it does not have enough information to make a reasonable guess.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">n := 3;;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">shift := VectorElement(CyclotomicField(n), [[[[1,0],[0,0]],</span>
[[0,0],[0,1]]],[[[0,1],[0,0]],,[[1,0],[0,0]]]],[1,E(n)],[1,0]);;
<Linear element on alphabet CF(3)^2 with 2-dimensional stateset>
<span class="GAPprompt">gap></span> <span class="GAPinput">GuessVectorElement(Activity(shift,3)); last=shift;</span>
<Linear element on alphabet CF(3)^2 with 2-dimensional stateset>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">GuessVectorElement(Inverse(Activity(shift,4)));</span>
fail
<span class="GAPprompt">gap></span> <span class="GAPinput">GuessVectorElement(Inverse(Activity(shift,5)));</span>
<Linear element on alphabet CF(3)^2 with 4-dimensional stateset>
<span class="GAPprompt">gap></span> <span class="GAPinput">IsOne(last*shift);</span>
true
</pre></div>
<p>This command accepts a domain and an ordinary machine/element, and constructs the corresponding linear machine/element, defined by extending linearly the action on <span class="SimpleMath">[1..d]</span> to an action on <span class="SimpleMath">r^d</span>.</p>
<p>If <var class="Arg">m</var> is a Mealy machine/element, the result is a vector machine/element. If <var class="Arg">m</var> is a group/monoid/semigroup machine/element, the result is an algebra machine/element. To obtain explicitly a vector or algebra machine/element, see <code class="func">AsVectorMachine</code> (<a href="chap6.html#X82586DFB8458EF05"><span class="RefLink">6.1-14</span></a>) and <code class="func">AsAlgebraMachine</code> (<a href="chap6.html#X7818245A7DABB311"><span class="RefLink">6.1-15</span></a>).</p>
<p>This command accepts a domain and an ordinary machine/element, and constructs the corresponding linear machine/element, defined by extending linearly the action on <span class="SimpleMath">[1..d]</span> to an action on <span class="SimpleMath">r^d</span>. For this command to succeed, the machine/element <var class="Arg">m</var> must be finite state. For examples see <code class="func">AsLinearMachine</code> (<a href="chap6.html#X865EE2E887ECC079"><span class="RefLink">6.1-13</span></a>).</p>
<p>This command accepts a domain and an ordinary machine/element, and constructs the corresponding linear machine/element, defined by extending linearly the action on <span class="SimpleMath">[1..d]</span> to an action on <span class="SimpleMath">r^d</span>. For examples see <code class="func">AsLinearMachine</code> (<a href="chap6.html#X865EE2E887ECC079"><span class="RefLink">6.1-13</span></a>).</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.
