<?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>
<title>GAP (FR) - Chapter 6: Linear machines and elements</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" />
</head>
<body>
<div class="chlinktop"><span class="chlink1">Goto Chapter: </span><a href="chap0.html">Top</a> <a href="chap1.html">1</a> <a href="chap2.html">2</a> <a href="chap3.html">3</a> <a href="chap4.html">4</a> <a href="chap5.html">5</a> <a href="chap6.html">6</a> <a href="chap7.html">7</a> <a href="chap8.html">8</a> <a href="chap9.html">9</a> <a href="chap10.html">10</a> <a href="chap11.html">11</a> <a href="chap12.html">12</a> <a href="chapBib.html">Bib</a> <a href="chapInd.html">Ind</a> </div>
<div class="chlinkprevnexttop"> <a href="chap0.html">Top of Book</a> <a href="chap5.html">Previous Chapter</a> <a href="chap7.html">Next Chapter</a> </div>
<p><a id="X84AD415C872BFB91" name="X84AD415C872BFB91"></a></p>
<div class="ChapSects"><a href="chap6.html#X84AD415C872BFB91">6 <span class="Heading">Linear machines and elements</span></a>
<div class="ContSect"><span class="nocss"> </span><a href="chap6.html#X812C0F7B7A31FCEF">6.1 <span class="Heading">Methods and operations for <code class="code">LinearFRMachine</code>s and <code class="code">LinearFRElement</code>s</span></a>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap6.html#X7F1EB8CB87229764">6.1-1 VectorMachine</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap6.html#X7F65118683209DC5">6.1-2 AlgebraMachine</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap6.html#X7A19036B828BBA0C">6.1-3 Transition</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap6.html#X846683198081BA82">6.1-4 Transitions</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap6.html#X80F694298399E78D">6.1-5 NestedMatrixState</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap6.html#X7FCEE3BF86B02CC6">6.1-6 ActivitySparse</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap6.html#X8436BEA67F1C3C27">6.1-7 Activities</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap6.html#X7EF5B7417AE6B3F8">6.1-8 IsConvergent</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap6.html#X8136C21885019A4A">6.1-9 TransposedFRElement</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap6.html#X796B736286CACF85">6.1-10 LDUDecompositionFRElement</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap6.html#X783E8F427A23EAD1">6.1-11 GuessVectorElement</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap6.html#X865EE2E887ECC079">6.1-12 AsLinearMachine</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap6.html#X82586DFB8458EF05">6.1-13 AsVectorMachine</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap6.html#X7818245A7DABB311">6.1-14 AsAlgebraMachine</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap6.html#X7BDD40B27F7541B2">6.1-15 AsVectorMachine</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap6.html#X8120605981DDE434">6.1-16 AsAlgebraMachine</a></span>
</div>
</div>
<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 Q and the alphabet X are vector spaces over a field Bbbk, and the transition map phi: Qotimes X-> Xotimes Q is a linear map; furthermore, there is a functional pi:Q->Bbbk called the <em>output</em>.</p>
<p>As before, a choice of initial state qin Q induces a linear map q:T(X)-> T(X), where T(X)=bigoplus X^otimes n is the tensor algebra generated by X. This map is defined as follows: given x=x_1otimesdotsotimes x_nin T(X), rewrite qotimes x as a sum of expressions of the form yotimes r with yin T(X) and rin Q; then q, by definition, maps x to the sum of the pi(r)y.</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>
<p><a id="X812C0F7B7A31FCEF" name="X812C0F7B7A31FCEF"></a></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><a id="X7F1EB8CB87229764" name="X7F1EB8CB87229764"></a></p>
<h5>6.1-1 VectorMachine</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> VectorMachine</code>( <var class="Arg">domain, transitions, output</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> VectorElement</code>( <var class="Arg">domain, transitions, output, init</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> VectorMachineNC</code>( <var class="Arg">fam, transitions, output</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> VectorElementNC</code>( <var class="Arg">fam, transitions, output, init</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p><b>Returns: </b>A new vector machine/element.</p>
<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 a-> b.</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.</p>
<table class="example">
<tr><td><pre>
gap> M := VectorMachine(Rationals,[[[[1]],[[2]]],[[[3]],[[4]]]],[1]);
<Linear machine on alphabet Rationals^2 with 1-dimensional stateset>
gap> Display(M);
Rationals | 1 | 2 |
-----------+---+---+
1 | 1 | 2 |
-----------+---+---+
2 | 3 | 4 |
-----------+---+---+
Output: 1
gap> A := VectorElement(Rationals,[[[[1]],[[2]]],[[[3]],[[4]]]],[1],[1]);
<Linear element on alphabet Rationals^2 with 1-dimensional stateset>
gap> Display(Activity(A,2));
[ [ 1, 2, 2, 4 ],
[ 3, 4, 6, 8 ],
[ 3, 6, 4, 8 ],
[ 9, 12, 12, 16 ] ]
gap> DecompositionOfFRElement(A);
[ [ <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> ] ]
gap> last=[[A,2*A],[3*A,4*A]];
true
</pre></td></tr></table>
<p><a id="X7F65118683209DC5" name="X7F65118683209DC5"></a></p>
<h5>6.1-2 AlgebraMachine</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> AlgebraMachine</code>( <var class="Arg">[domain, ]ring, transitions, output</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> AlgebraElement</code>( <var class="Arg">[domain, ]ring, transitions, output, init</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> AlgebraMachineNC</code>( <var class="Arg">fam, ring, transitions, output</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> AlgebraElementNC</code>( <var class="Arg">fam, ring, transitions, output, init</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p><b>Returns: </b>A new algebra machine/element.</p>
<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="/usr/local/src/4.0/doc/ref/chap55.html#s1ss11"><b>Reference: LeftActingDomain</b></a>) of <var class="Arg">ring</var>.</p>
<p><var class="Arg">transitions</var> is a list of matrices; for each generator number i 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 i 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.</p>
<table class="example">
<tr><td><pre>
gap> F := FreeAssociativeAlgebraWithOne(Rationals,1);;
gap> A := AlgebraMachine(F,[[[F.1,F.1^2+F.1],[One(F),Zero(F)]]],[1]);
<Linear machine on alphabet Rationals^2 with generators [ (1)*x.1 ]>
gap> Display(A);
Rationals | 1 | 2 |
-----------+-----------+-----------+
1 | x.1 | x.1+x.1^2 |
-----------+-----------+-----------+
2 | 1 | 0 |
-----------+-----------+-----------+
Output: 1
gap> M := AlgebraElement(F,[[[F.1,F.1^2+F.1],[One(F),Zero(F)]]],[1],F.1);
<Rationals^2|(1)*x.1>
gap> Display(Activity(M,2));
[ [ 1, 2, 4, 4 ],
[ 1, 0, 2, 2 ],
[ 1, 0, 0, 0 ],
[ 0, 1, 0, 0 ] ]
</pre></td></tr></table>
<p><a id="X7A19036B828BBA0C" name="X7A19036B828BBA0C"></a></p>
<h5>6.1-3 Transition</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> Transition</code>( <var class="Arg">m, s, a, b</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p><b>Returns: </b>An element of <var class="Arg">m</var>'s stateset.</p>
<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 a-> b.</p>
<table class="example">
<tr><td><pre>
gap> M := AsVectorMachine(Rationals,FRMachine(GuptaSidkiGroup.2));
<Linear machine on alphabet Rationals^3 with 4-dimensional stateset>
gap> Transition(M,[1,0,0,0],[1,0,0],[1,0,0]);
[ 0, 1, 0, 0 ]
gap> Transition(M,[1,0,0,0],[0,1,0],[0,1,0]);
[ 0, 0, 1, 0 ]
gap> Transition(M,[1,0,0,0],[0,0,1],[0,0,1]);
[ 1, 0, 0, 0 ]
gap> A := AsVectorElement(Rationals,GuptaSidkiGroup.2);
<Linear element on alphabet Rationals^3 with 4-dimensional stateset>
gap> Transition(A,[1,0,0],[1,0,0]);
[ 0, 1, 0, 0 ]
</pre></td></tr></table>
<p><a id="X846683198081BA82" name="X846683198081BA82"></a></p>
<h5>6.1-4 Transitions</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> Transitions</code>( <var class="Arg">m, s, a</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p><b>Returns: </b>An vector of elements of <var class="Arg">m</var>'s stateset.</p>
<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>
<table class="example">
<tr><td><pre>
gap> M := AsVectorMachine(Rationals,FRMachine(GuptaSidkiGroup.2));
<Linear machine on alphabet Rationals^3 with 4-dimensional stateset>
gap> Transitions(M,[1,0,0,0],[1,0,0]);
[ [ 0, 1, 0, 0 ], [ 0, 0, 0, 0 ], [ 0, 0, 0, 0 ] ]
gap> A := AsVectorElement(Rationals,GuptaSidkiGroup.2);
<Linear element on alphabet Rationals^3 with 4-dimensional stateset>
gap> Transitions(A,[1,0,0]);
[ [ 0, 1, 0, 0 ], [ 0, 0, 0, 0 ], [ 0, 0, 0, 0 ] ]
</pre></td></tr></table>
<p><a id="X80F694298399E78D" name="X80F694298399E78D"></a></p>
<h5>6.1-5 NestedMatrixState</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> NestedMatrixState</code>( <var class="Arg">e, i, j</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> NestedMatrixCoefficient</code>( <var class="Arg">e, i, j</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p><b>Returns: </b>A coefficent of an iterated decomposition of <var class="Arg">e</var>.</p>
<p>The first form returns the entry at position (i,j) of <var class="Arg">e</var>'s decomposition. Both of <var class="Arg">i,j</var> are lists. The second form returns the output of the state.</p>
<p>In particular, <code class="code">NestedMatrixState(e,[],[])=e</code>, and <code class="code">Activity(e,1)[i][j]=NestedMatrixCoefficient(e,[i],[j])</code>, and <code class="code">DecompositionOfFRElement(e,1)[i][j]=NestedMatrixState(e,[i],[j])</code>.</p>
<table class="example">
<tr><td><pre>
gap> A := AsVectorElement(Rationals,GuptaSidkiGroup.2);;
gap> A=NestedMatrixState(A,[3,3],[3,3]);
true
gap> IsOne(NestedMatrixState(A,[3,3,3,3,1,1],[3,3,3,3,1,2]));
true
gap> List([1..3],i->List([1..3],j->NestedMatrixCoefficient(A,[i],[j])))=Activity(A,1);
true
</pre></td></tr></table>
<p><a id="X7FCEE3BF86B02CC6" name="X7FCEE3BF86B02CC6"></a></p>
<h5>6.1-6 ActivitySparse</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> ActivitySparse</code>( <var class="Arg">m, i</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p><b>Returns: </b>A sparse matrix.</p>
<p><code class="code">Activity(m,i)</code> returns an n^ix n^i matrix describing the action on the i-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 c at position (i,j). The activity matrix is then the sum of these elementary matrices.</p>
<table class="example">
<tr><td><pre>
gap> A := AsVectorElement(Rationals,GuptaSidkiGroup.2);;
gap> Display(Activity(A,2));
[ [ 0, 1, 0, 0, 0, 0, 0, 0, 0 ],
[ 0, 0, 1, 0, 0, 0, 0, 0, 0 ],
[ 1, 0, 0, 0, 0, 0, 0, 0, 0 ],
[ 0, 0, 0, 0, 0, 1, 0, 0, 0 ],
[ 0, 0, 0, 1, 0, 0, 0, 0, 0 ],
[ 0, 0, 0, 0, 1, 0, 0, 0, 0 ],
[ 0, 0, 0, 0, 0, 0, 1, 0, 0 ],
[ 0, 0, 0, 0, 0, 0, 0, 1, 0 ],
[ 0, 0, 0, 0, 0, 0, 0, 0, 1 ] ]
gap> ActivitySparse(A,2);
[ [ [ 1, 2 ], 1 ], [ [ 2, 3 ], 1 ], [ [ 3, 1 ], 1 ], [ [ 4, 6 ], 1 ],
[ [ 5, 4 ], 1 ], [ [ 6, 5 ], 1 ], [ [ 7, 7 ], 1 ], [ [ 8, 8 ], 1 ],
[ [ 9, 9 ], 1 ] ]
</pre></td></tr></table>
<p><a id="X8436BEA67F1C3C27" name="X8436BEA67F1C3C27"></a></p>
<h5>6.1-7 Activities</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> Activities</code>( <var class="Arg">m, i</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p><b>Returns: </b>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 n^ix n^i matrix describing the action on the i-fold tensor power of the alphabet. This command returns <code class="code">List([0..i-1],j->Activity(m,j))</code>.</p>
<table class="example">
<tr><td><pre>
gap> A := AsVectorElement(Rationals,GrigorchukGroup.2);;
gap> Activities(A,3);
[ [ [ 1 ] ],
[ [ 1, 0 ], [ 0, 1 ] ],
[ [ 0, 1, 0, 0 ], [ 1, 0, 0, 0 ], [ 0, 0, 1, 0 ], [ 0, 0, 0, 1 ] ] ]
</pre></td></tr></table>
<p><a id="X7EF5B7417AE6B3F8" name="X7EF5B7417AE6B3F8"></a></p>
<h5>6.1-8 IsConvergent</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> IsConvergent</code>( <var class="Arg">e</var> )</td><td class="tdright">( property )</td></tr></table></div>
<p><b>Returns: </b>Whether the linear element <var class="Arg">e</var> is convergent.</p>
<p>A linear element is <em>convergent</em> if its state at position (1,1) is equal to itself.</p>
<table class="example">
<tr><td><pre>
gap> n := 3;;
gap> shift := VectorElement(CyclotomicField(n), [[[[1,0],[0,0]],
[[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>
gap> IsConvergent(shift);
true
gap> Display(Activity(shift,2));
[ [ 1, 0, 0, 0 ],
[ E(3), 1, 0, 0 ],
[ 0, E(3), 1, 0 ],
[ 0, 0, E(3), 1 ] ]
gap> Display(Activity(shift,3));
[ [ 1, 0, 0, 0, 0, 0, 0, 0 ],
[ E(3), 1, 0, 0, 0, 0, 0, 0 ],
[ 0, E(3), 1, 0, 0, 0, 0, 0 ],
[ 0, 0, E(3), 1, 0, 0, 0, 0 ],
[ 0, 0, 0, E(3), 1, 0, 0, 0 ],
[ 0, 0, 0, 0, E(3), 1, 0, 0 ],
[ 0, 0, 0, 0, 0, E(3), 1, 0 ],
[ 0, 0, 0, 0, 0, 0, E(3), 1 ] ]
</pre></td></tr></table>
<p><a id="X8136C21885019A4A" name="X8136C21885019A4A"></a></p>
<h5>6.1-9 TransposedFRElement</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> TransposedFRElement</code>( <var class="Arg">e</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> IsSymmetricFRElement</code>( <var class="Arg">e</var> )</td><td class="tdright">( property )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> IsAntisymmetricFRElement</code>( <var class="Arg">e</var> )</td><td class="tdright">( property )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> IsLowerTriangularFRElement</code>( <var class="Arg">e</var> )</td><td class="tdright">( property )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> IsUpperTriangularFRElement</code>( <var class="Arg">e</var> )</td><td class="tdright">( property )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> IsDiagonalFRElement</code>( <var class="Arg">e</var> )</td><td class="tdright">( property )</td></tr></table></div>
<p><b>Returns: </b>The elementary matrix operation/property.</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>
<table class="example">
<tr><td><pre>
gap> n := 3;;
gap> shift := VectorElement(CyclotomicField(n), [[[[1,0],[0,0]],
[[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>
gap> Display(Activity(shift,2));
[ [ 1, 0, 0, 0 ],
[ E(3), 1, 0, 0 ],
[ 0, E(3), 1, 0 ],
[ 0, 0, E(3), 1 ] ]
gap> Display(Activity(TransposedFRElement(shift),2));
[ [ 1, E(3), 0, 0 ],
[ 0, 1, E(3), 0 ],
[ 0, 0, 1, E(3) ],
[ 0, 0, 0, 1 ] ]
gap> IsSymmetricFRElement(shift);
false
gap> IsSymmetricFRElement(shift+TransposedFRElement(shift));
true
gap> IsLowerTriangularFRElement(shift);
true
gap> IsUpperTriangularFRElement(shift);
false
</pre></td></tr></table>
<p><a id="X796B736286CACF85" name="X796B736286CACF85"></a></p>
<h5>6.1-10 LDUDecompositionFRElement</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> LDUDecompositionFRElement</code>( <var class="Arg">e</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p><b>Returns: </b>A factorization e=LDU.</p>
<p>Given a linear element <var class="Arg">e</var>, this command attempts to find a decomposition of the form e=LDU, where L is lower triangular, D is diagonal, and U is upper triangular (see <code class="func">IsLowerTriangularFRElement</code> (<a href="chap6.html#X8136C21885019A4A"><b>6.1-9</b></a>) etc.).</p>
<p>The result is returned thas a list with entries L,D,U. Note that it is not guaranteed to succeed. For more examples, see Section <a href="chap10.html#X7989134C83AF38AE"><b>10.4</b></a>.</p>
<table class="example">
<tr><td><pre>
gap> List([0..7],s->List([0..7],t->E(4)^ValuationInt(Binomial(s+t,s),2)));;
gap> A := GuessVectorElement(last);
<Linear element on alphabet GaussianRationals^2 with 2-dimensional stateset>
gap> LDU := LDUDecompositionFRElement(A);
[ <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> ]
gap> IsLowerTriangularFRElement(LDU[1]); IsDiagonalFRElement(LDU[2]);
true
true
gap> TransposedFRElement(LDU[1])=LDU[3];
true
gap> Product(LDU)=A;
true
</pre></td></tr></table>
<p><a id="X783E8F427A23EAD1" name="X783E8F427A23EAD1"></a></p>
<h5>6.1-11 GuessVectorElement</h5>
<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><b>Returns: </b>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 <code class="func">IsConvergent</code> (<a href="chap6.html#X7EF5B7417AE6B3F8"><b>6.1-8</b></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>
<table class="example">
<tr><td><pre>
gap> n := 3;;
gap> shift := VectorElement(CyclotomicField(n), [[[[1,0],[0,0]],
[[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>
gap> GuessVectorElement(Activity(shift,3)); last=shift;
<Linear element on alphabet CF(3)^2 with 2-dimensional stateset>
true
gap> GuessVectorElement(Inverse(Activity(shift,4)));
fail
gap> GuessVectorElement(Inverse(Activity(shift,5)));
<Linear element on alphabet CF(3)^2 with 4-dimensional stateset>
gap> IsOne(last*shift);
true
</pre></td></tr></table>
<p><a id="X865EE2E887ECC079" name="X865EE2E887ECC079"></a></p>
<h5>6.1-12 AsLinearMachine</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> AsLinearMachine</code>( <var class="Arg">r, m</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> AsLinearElement</code>( <var class="Arg">r, m</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p><b>Returns: </b>The linear machine/element associated with <var class="Arg">m</var>.</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 [1..d] to an action on r^d.</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"><b>6.1-13</b></a>) and <code class="func">AsAlgebraMachine</code> (<a href="chap6.html#X7818245A7DABB311"><b>6.1-14</b></a>).</p>
<table class="example">
<tr><td><pre>
gap> Display(I4Machine);
| 1 2
---+-----+-----+
a | c,2 c,1
b | a,1 b,1
c | c,1 c,2
---+-----+-----+
gap> A := AsLinearMachine(Rationals,I4Machine);
<Linear machine on alphabet Rationals^2 with 3-dimensional stateset>
Correspondence(A);
[ [ 1, 0, 0 ], [ 0, 1, 0 ], [ 0, 0, 1 ] ]
gap> Display(A);
Rationals | 1 | 2 |
-----------+-------+-------+
1 | 0 0 0 | 0 0 1 |
| 1 0 0 | 0 0 0 |
| 0 0 1 | 0 0 0 |
-----------+-------+-------+
2 | 0 0 1 | 0 0 0 |
| 0 1 0 | 0 0 0 |
| 0 0 0 | 0 0 1 |
-----------+-------+-------+
Output: 1 1 1
gap> B := AsLinearMachine(Rationals,AsMonoidFRMachine(I4Machine));
<Linear machine on alphabet Rationals^2 with generators [ (1)*m1, (1)*m2 ]>
gap> Correspondence(B);
MappingByFunction( <free monoid on the generators [ m1, m2 ]>,
<algebra-with-one over Rationals, with 2 generators>, function( w ) ... end )
gap> Display(B);
Rationals | 1 | 2 |
-----------+----+----+
1 | 0 | 1 |
| m1 | 0 |
-----------+----+----+
2 | 1 | 0 |
| m2 | 0 |
-----------+----+----+
Output: 1 1
gap> AsLinearElement(Rationals,I4Monoid.1)*AsLinearElement(Rationals,I4Monoid.2);
<Linear element on alphabet Rationals^2 with 4-dimensional stateset>
gap> last=AsLinearElement(Rationals,I4Monoid.1*I4Monoid.2);
true
</pre></td></tr></table>
<p><a id="X82586DFB8458EF05" name="X82586DFB8458EF05"></a></p>
<h5>6.1-13 AsVectorMachine</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> AsVectorMachine</code>( <var class="Arg">r, m</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> AsVectorElement</code>( <var class="Arg">r, m</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p><b>Returns: </b>The vector machine/element associated with <var class="Arg">m</var>.</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 [1..d] to an action on r^d. 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"><b>6.1-12</b></a>).</p>
<p><a id="X7818245A7DABB311" name="X7818245A7DABB311"></a></p>
<h5>6.1-14 AsAlgebraMachine</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> AsAlgebraMachine</code>( <var class="Arg">r, m</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> AsAlgebraElement</code>( <var class="Arg">r, m</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p><b>Returns: </b>The algebra machine/element associated with <var class="Arg">m</var>.</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 [1..d] to an action on r^d. For examples see <code class="func">AsLinearMachine</code> (<a href="chap6.html#X865EE2E887ECC079"><b>6.1-12</b></a>).</p>
<p><a id="X7BDD40B27F7541B2" name="X7BDD40B27F7541B2"></a></p>
<h5>6.1-15 AsVectorMachine</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> AsVectorMachine</code>( <var class="Arg">m</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> AsVectorElement</code>( <var class="Arg">m</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p><b>Returns: </b>The machine/element <var class="Arg">m</var> in vector form.</p>
<p>This command accepts a linear machine, and converts it to vector form. This command is not guaranteed to terminate.</p>
<table class="example">
<tr><td><pre>
gap> A := AsLinearElement(Rationals,I4Monoid.1);
<Linear element on alphabet Rationals^2 with 2-dimensional stateset>
gap> B := AsAlgebraElement(A);
<Rationals^2|(1)*x.1>
gap> C := AsVectorElement(B);
gap> A=B; B=C;
true
true
</pre></td></tr></table>
<p><a id="X8120605981DDE434" name="X8120605981DDE434"></a></p>
<h5>6.1-16 AsAlgebraMachine</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> AsAlgebraMachine</code>( <var class="Arg">m</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> AsAlgebraElement</code>( <var class="Arg">m</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p><b>Returns: </b>The machine/element <var class="Arg">m</var> in algebra form.</p>
<p>This command accepts a linear machine, and converts it to algebra form.</p>
<table class="example">
<tr><td><pre>
gap> A := AsLinearElement(Rationals,I4Monoid.1);
<Linear element on alphabet Rationals^2 with 2-dimensional stateset>
gap> AsAlgebraElement(A)=AsAlgebraElement(Rationals,I4Monoid.1);
true
gap> A=AsAlgebraElement(A);
true
</pre></td></tr></table>
<div class="chlinkprevnextbot"> <a href="chap0.html">Top of Book</a> <a href="chap5.html">Previous Chapter</a> <a href="chap7.html">Next Chapter</a> </div>
<div class="chlinkbot"><span class="chlink1">Goto Chapter: </span><a href="chap0.html">Top</a> <a href="chap1.html">1</a> <a href="chap2.html">2</a> <a href="chap3.html">3</a> <a href="chap4.html">4</a> <a href="chap5.html">5</a> <a href="chap6.html">6</a> <a href="chap7.html">7</a> <a href="chap8.html">8</a> <a href="chap9.html">9</a> <a href="chap10.html">10</a> <a href="chap11.html">11</a> <a href="chap12.html">12</a> <a href="chapBib.html">Bib</a> <a href="chapInd.html">Ind</a> </div>
<hr />
<p class="foot">generated by <a href="http://www.math.rwth-aachen.de/~Frank.Luebeck/GAPDoc">GAPDoc2HTML</a></p>
</body>
</html>
distrib
>
Mandriva
>
2010.0
>
i586
>
media
>
contrib-release
>
by-pkgid
>
91213ddcfbe7f54821d42c2d9e091326
>
files
>
1164
