<?xml version="1.0" encoding="UTF-8"?>

<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN"
         "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">

<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en">
<head>
<script type="text/javascript"
  src="https://cdn.jsdelivr.net/npm/mathjax@2/MathJax.js?config=TeX-AMS-MML_HTMLorMML">
</script>
<title>GAP (FR) - Chapter 8: Algebras</title>
<meta http-equiv="content-type" content="text/html; charset=UTF-8" />
<meta name="generator" content="GAPDoc2HTML" />
<link rel="stylesheet" type="text/css" href="manual.css" />
<script src="manual.js" type="text/javascript"></script>
<script type="text/javascript">overwriteStyle();</script>
</head>
<body class="chap8"  onload="jscontent()">


<div class="chlinktop"><span class="chlink1">Goto Chapter: </span><a href="chap0_mj.html">Top</a>  <a href="chap1_mj.html">1</a>  <a href="chap2_mj.html">2</a>  <a href="chap3_mj.html">3</a>  <a href="chap4_mj.html">4</a>  <a href="chap5_mj.html">5</a>  <a href="chap6_mj.html">6</a>  <a href="chap7_mj.html">7</a>  <a href="chap8_mj.html">8</a>  <a href="chap9_mj.html">9</a>  <a href="chap10_mj.html">10</a>  <a href="chap11_mj.html">11</a>  <a href="chapBib_mj.html">Bib</a>  <a href="chapInd_mj.html">Ind</a>  </div>

<div class="chlinkprevnexttop"> <a href="chap0_mj.html">[Top of Book]</a>   <a href="chap0_mj.html#contents">[Contents]</a>    <a href="chap7_mj.html">[Previous Chapter]</a>    <a href="chap9_mj.html">[Next Chapter]</a>   </div>

<p id="mathjaxlink" class="pcenter"><a href="chap8.html">[MathJax off]</a></p>
<p><a id="X7DDBF6F47A2E021C" name="X7DDBF6F47A2E021C"></a></p>
<div class="ChapSects"><a href="chap8_mj.html#X7DDBF6F47A2E021C">8 <span class="Heading">Algebras</span></a>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap8_mj.html#X842EE9427C63F92E">8.1 <span class="Heading">Creators for FR algebras</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap8_mj.html#X812FEA6778152E49">8.1-1 FRAlgebra</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap8_mj.html#X844B890F7BF56236">8.1-2 SCAlgebra</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap8_mj.html#X7B8330F180BABC43">8.1-3 NucleusOfFRAlgebra</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap8_mj.html#X81D8D0E886C8E143">8.1-4 BranchingIdeal</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap8_mj.html#X7EFB4F2E7E908B9F">8.2 <span class="Heading">Operations for FR algebras</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap8_mj.html#X8115B018871FD364">8.2-1 MatrixQuotient</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap8_mj.html#X8150FC4E84D208C6">8.2-2 ThinnedAlgebra</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap8_mj.html#X8572DCAE7F888DDA">8.2-3 Nillity</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap8_mj.html#X85163F29824C944D">8.2-4 DegreeOfHomogeneousElement</a></span>
</div></div>
</div>

<h3>8 <span class="Heading">Algebras</span></h3>

<p>Self-similar algebras and algebras with one (below <em>FR algebras</em>) are simply algebras [with one] whose elements are linear FR machines. They naturally act on the alphabet of their elements, which is a vector space.</p>

<p>Elements may be added, subtracted and multiplied. They can be vector or algebra linear elements; the vector elements are in general preferable, for efficiency reasons.</p>

<p>Finite-dimensional approximations of self-similar algebras can be computed; they are given as matrix algebras.</p>

<p><a id="X842EE9427C63F92E" name="X842EE9427C63F92E"></a></p>

<h4>8.1 <span class="Heading">Creators for FR algebras</span></h4>

<p>The most straightforward creation method for FR algebras is <code class="code">Algebra()</code>, applied with linear FR elements as arguments. There are shortcuts to this somewhat tedious method:</p>

<p><a id="X812FEA6778152E49" name="X812FEA6778152E49"></a></p>

<h5>8.1-1 FRAlgebra</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; FRAlgebra</code>( <var class="Arg">ring</var>, <var class="Arg">{definition</var>, <var class="Arg">}</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">&#an style='color: green'>8227; FRAlgebraWithOne</code>( <var class="Arg">ring</var>, <var class="Arg">{definition</var>, <var class="Arg">}</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Returns: A new self-similar algebra [with one].</p>

<p>This function constructs a new FR algebra [with one], generated by linear FR elements. It receives as argument any number of strings, each of which represents a generator of the object to be constructed.</p>

<p><var class="Arg">ring</var> is the acting domain of the vector space on which the algebra will act.</p>

<p>Each <var class="Arg">definition</var> is of the form <code class="code">"name=[[...],...,[...]]"</code> or of the form <code class="code">"name=[[...],...,[...]]:out"</code>, namely a matrix whose entries are algebraic expressions in the <code class="code">names</code>, possibly using <code class="code">0,1</code>, optionally followed by a scalar. The matrix entries specify the decomposition of the element being defined, and the optional scalar specifies the output of that element, by default assumed to be one.</p>

<p>The option <code class="code">IsVectorElement</code> asks for the resulting algebra to be generated by vector elements, see example below. The generators must of course be finite-state.</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">m := FRAlgebra(Rationals,"a=[[1,a],[a,0]]");</span>
<self-similar algebra on alphabet Rationals^2 with 1 generator>
<span class="GAPprompt">gap></span> <span class="GAPinput">Display(Activity(m.1,2));</span>
[ [  1,  0,  1,  1 ],
  [  0,  1,  1,  0 ],
  [  1,  1,  0,  0 ],
  [  1,  0,  0,  0 ] ]
<span class="GAPprompt">gap></span> <span class="GAPinput">m2 := FRAlgebra(Rationals,"a=[[1,a],[a,0]]":IsVectorElement);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">m.1=m2.1;</span>
true
</pre></div>

<p><a id="X844B890F7BF56236" name="X844B890F7BF56236"></a></p>

<h5>8.1-2 SCAlgebra</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; SCAlgebra</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">&#an style='color: green'>8227; SCLieAlgebra</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">&#an style='color: green'>8227; SCAlgebraWithOne</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">&#an style='color: green'>8227; SCAlgebraNC</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">&#an style='color: green'>8227; SCAlgebraWithOneNC</code>( <var class="Arg">m</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Returns: The state-closed algebra [with one] generated by the machine <var class="Arg">m</var>.</p>

<p>This function constructs a new FR algebra [vith one] <code class="code">a</code>, generated by all the states of the FR machine <var class="Arg">m</var>. There is a bijective correspondence between <code class="code">GeneratorsOfFRMachine(m)</code> and the generators of <code class="code">a</code>, which is accessible via <code class="code">Correspondence(a)</code> (See <code class="func">Correspondence</code> (<a href="chap7_mj.html#X7F15D57A7959FEF6"><span class="RefLink">7.1-4</span></a>)); it is a homomorphism from the stateset of <var class="Arg">m</var> to <code class="code">a</code>, or a list indicating for each state of <var class="Arg">m</var> a corresponding generator index in the generators of <code class="code">a</code> (with 0 for identity).</p>

<p>In the non-<code class="code">NC</code> forms, redundant (equal, zero or one) states are removed from the generating set of <code class="code">a</code>.</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">a := SCAlgebra(AsLinearMachine(Rationals,I4Machine));</span>
<self-similar algebra on alphabet Rationals^2 with 3 generators>
<span class="GAPprompt">gap></span> <span class="GAPinput">a.1 = AsLinearElement(Rationals,I4Monoid.1);</span>
true
</pre></div>

<p><a id="X7B8330F180BABC43" name="X7B8330F180BABC43"></a></p>

<h5>8.1-3 NucleusOfFRAlgebra</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; NucleusOfFRAlgebra</code>( <var class="Arg">a</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; Nucleus</code>( <var class="Arg">a</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Returns: The nucleus of the contracting algebra <var class="Arg">a</var>.</p>

<p>This function returns the <em>nucleus</em> of the contracting algebra <var class="Arg">a</var>, i.e. the smallest subspace <code class="code">N</code> of <var class="Arg">a</var> such that the <code class="func">LimitStates</code> (<a href="chap4_mj.html#X8303B36C83371FB3"><span class="RefLink">4.2-11</span></a>) of every element of <var class="Arg">a</var> belong to <code class="code">N</code>.</p>

<p>This function returns <code class="keyw">fail</code> if no such <code class="code">N</code> exists. Usually, it loops forever without being able to decide whether <code class="code">N</code> is finite or infinite. It succeeds precisely when <code class="code">IsContracting(g)</code> succeeds.</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">> a := GrigorchukThinnedAlgebra(2);</span>
<self-similar algebra-with-one on alphabet GF(2)^2 with 4 generators, of dimension infinity>
<span class="GAPprompt">gap></span> <span class="GAPinput">NucleusOfFRAlgebra(a);</span>
<vector space over GF(2), with 4 generators>
</pre></div>

<p><a id="X81D8D0E886C8E143" name="X81D8D0E886C8E143"></a></p>

<h5>8.1-4 BranchingIdeal</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; BranchingIdeal</code>( <var class="Arg">A</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Returns: An ideal <span class="SimpleMath">\(I\)</span> that contains matrices over itself.</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">R := GrigorchukThinnedAlgebra(2);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">I := BranchingIdeal(R);</span>
<two-sided ideal in <self-similar algebra-with-one on alphabet GF(2)^2
 with 4 generators, of dimension infinity>, (3 generators)>
<span class="GAPprompt">gap></span> <span class="GAPinput">e := EpimorphismMatrixQuotient(R,3);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">eI := Ideal(Range(e),List(GeneratorsOfIdeal(I),x->x^e));</span>
<two-sided ideal in <algebra-with-one of dimension 22 over GF(2)>, (3 generators)>
<span class="GAPprompt">gap></span> <span class="GAPinput">Dimension(Range(e)/eI);</span>
6
</pre></div>

<p><a id="X7EFB4F2E7E908B9F" name="X7EFB4F2E7E908B9F"></a></p>

<h4>8.2 <span class="Heading">Operations for FR algebras</span></h4>

<p><a id="X8115B018871FD364" name="X8115B018871FD364"></a></p>

<h5>8.2-1 MatrixQuotient</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; MatrixQuotient</code>( <var class="Arg">a</var>, <var class="Arg">l</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">&#an style='color: green'>8227; EpimorphismMatrixQuotient</code>( <var class="Arg">a</var>, <var class="Arg">l</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Returns: The matrix algebra of <var class="Arg">a</var>'s action on level <var class="Arg">l</var>.</p>

<p>The first function returns the matrix algebra generated by the activities of <var class="Arg">a</var> on level <var class="Arg">l</var> (see the examples in <a href="chap6_mj.html#X7FCEE3BF86B02CC6"><span class="RefLink">6.1-7</span></a>). The second functon returns an algebra homomorphism from <var class="Arg">a</var> to the matrix algebra.</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">a := ThinnedAlgebraWithOne(GF(2),GrigorchukGroup);</span>
<self-similar algebra-with-one on alphabet GF(2)^2 with 4 generators>
<span class="GAPprompt">gap></span> <span class="GAPinput">List([0..4],i->Dimension(MatrixQuotient(a,i)));</span>
[ 1, 2, 6, 22, 78 ]
</pre></div>

<p><a id="X8150FC4E84D208C6" name="X8150FC4E84D208C6"></a></p>

<h5>8.2-2 ThinnedAlgebra</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; ThinnedAlgebra</code>( <var class="Arg">r</var>, <var class="Arg">g</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">&#an style='color: green'>8227; ThinnedAlgebraWithOne</code>( <var class="Arg">r</var>, <var class="Arg">g</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Returns: The thinned algebra [with one] associated with <var class="Arg">g</var>.</p>

<p>The first function returns the thinned algebra of a FR group/monoid/semigroup <var class="Arg">g</var>, over the domain <var class="Arg">r</var>. This is the linear envelope of <var class="Arg">g</var> in its natural action on sequences.</p>

<p>The embedding of <var class="Arg">g</var> in its thinned algebra is returned by <code class="code">Embedding(g,a)</code>.</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">a := ThinnedAlgebraWithOne(GF(2),GrigorchukGroup);</span>
<self-similar algebra on alphabet GF(2)^2 with 5 generators>
<span class="GAPprompt">gap></span> <span class="GAPinput">a.1 = GrigorchukGroup.1^Embedding(GrigorchukGroup,a);</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">Dimension(VectorSpace(GF(2),[One(a),a.2,a.3,a.4]));</span>
3
</pre></div>

<p><a id="X8572DCAE7F888DDA" name="X8572DCAE7F888DDA"></a></p>

<h5>8.2-3 Nillity</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; Nillity</code>( <var class="Arg">x</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; IsNilElement</code>( <var class="Arg">x</var> )</td><td class="tdright">( property )</td></tr></table></div>
<p>Returns: The smallest <code class="code">n</code> such that <span class="SimpleMath">\(x^n=0\)</span>.</p>

<p>The first command computes the nillity of <var class="Arg">x</var>, i.e. the smallest <code class="code">n</code> such that <span class="SimpleMath">\(x^n=0\)</span>. The command is not guaranteed to terminate.</p>

<p>The second command returns whether <var class="Arg">x</var> is nil, that is, whether its nillity is finite.</p>

<p><a id="X85163F29824C944D" name="X85163F29824C944D"></a></p>

<h5>8.2-4 DegreeOfHomogeneousElement</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; DegreeOfHomogeneousElement</code>( <var class="Arg">x</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; IsHomogeneousElement</code>( <var class="Arg">x</var> )</td><td class="tdright">( property )</td></tr></table></div>
<p>Returns: The degree of <var class="Arg">x</var> in its parent.</p>

<p>If <var class="Arg">x</var> belongs to a graded algebra <code class="code">A</code>, then the second command returns whether <var class="Arg">x</var> belongs to a homogeneous component of <code class="code">Grading(A)</code>, and the first command returns the degree of that component (or <code class="keyw">fail</code> if no such component exists).</p>


<div class="chlinkprevnextbot"> <a href="chap0_mj.html">[Top of Book]</a>   <a href="chap0_mj.html#contents">[Contents]</a>    <a href="chap7_mj.html">[Previous Chapter]</a>    <a href="chap9_mj.html">[Next Chapter]</a>   </div>


<div class="chlinkbot"><span class="chlink1">Goto Chapter: </span><a href="chap0_mj.html">Top</a>  <a href="chap1_mj.html">1</a>  <a href="chap2_mj.html">2</a>  <a href="chap3_mj.html">3</a>  <a href="chap4_mj.html">4</a>  <a href="chap5_mj.html">5</a>  <a href="chap6_mj.html">6</a>  <a href="chap7_mj.html">7</a>  <a href="chap8_mj.html">8</a>  <a href="chap9_mj.html">9</a>  <a href="chap10_mj.html">10</a>  <a href="chap11_mj.html">11</a>  <a href="chapBib_mj.html">Bib</a>  <a href="chapInd_mj.html">Ind</a>  </div>

<hr />
<p class="foot">generated by <a href="https://www.math.rwth-aachen.de/~Frank.Luebeck/GAPDoc">GAPDoc2HTML</a></p>
</body>
</html>