Quellcodebibliothek Statistik Leitseite products/Sources/formale Sprachen/GAP/pkg/groupoids/doc/   (Algebra von RWTH Aachen Version 4.15.1©)  Datei vom 11.8.2025 mit Größe 153 B image not shown  

Quelle  chap4.html   Sprache: HTML

 
 products/Sources/formale Sprachen/GAP/pkg/semigroups/doc/chap4.html


<?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 (Semigroups) - Chapter 4: 
    Partitioned binary relations (PBRs)
  </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="chap4"  onload="jscontent()">


<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="chap13.html">13</a>  <a href="chap14.html">14</a>  <a href="chap15.html">15</a>  <a href="chap16.html">16</a>  <a href="chap17.html">17</a>  <a href="chap18.html">18</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="chap0.html#contents">[Contents]</a>    <a href="chap3.html">[Previous Chapter]</a>    <a href="chap5.html">[Next Chapter]</a>   </div>

<p id="mathjaxlink" class="pcenter"><a href="chap4_mj.html">[MathJax on]</a></p>
<p><a id="X85A717D1790B7BB5" name="X85A717D1790B7BB5"></a></p>
<div class="ChapSects"><a href="chap4.html#X85A717D1790B7BB5">4 <span class="Heading">
    Partitioned binary relations (PBRs)
  </span></a>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap4.html#X7C40DA67826FF873">4.1 <span class="Heading">The family and categories of PBRs</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap4.html#X82CCBADC80AE2D15">4.1-1 IsPBR</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap4.html#X854A9CEA7AC14C0A">4.1-2 IsPBRCollection</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap4.html#X8758C4FB81D2C2A1">4.2 <span class="Heading">Creating PBRs</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap4.html#X82A8646F7C70CF3B">4.2-1 PBR</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap4.html#X82FE736F7F11B157">4.2-2 RandomPBR</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap4.html#X8646781B7EAE04C0">4.2-3 EmptyPBR</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap4.html#X80D20EA3816DC862">4.2-4 IdentityPBR</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap4.html#X847BA0177D90E9D7">4.2-5 UniversalPBR</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap4.html#X86B714987C01895F">4.3 <span class="Heading">Changing the representation of a PBR</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap4.html#X81CBBE6080439596">4.3-1 AsPBR</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap4.html#X8407F516825A514A">4.3-2 AsTransformation</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap4.html#X795B1C16819905E8">4.3-3 AsPartialPerm</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap4.html#X86786B297FBCD064">4.3-4 AsPermutation</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap4.html#X872B5817878660E5">4.4 <span class="Heading">Operators for PBRs</span></a>
</span>
</div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap4.html#X78EC8E597EB99730">4.5 <span class="Heading">Attributes for PBRs</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap4.html#X7DFC277E80A50C2F">4.5-1 StarOp</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap4.html#X785B576B7823D626">4.5-2 DegreeOfPBR</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap4.html#X78302D7E81BB1E54">4.5-3 ExtRepOfObj</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap4.html#X7F4C8A2B79E6D963">4.5-4 PBRNumber</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap4.html#X82FD0AB179ED4AFD">4.5-5 IsEmptyPBR</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap4.html#X7E263B2F7B838D6E">4.5-6 IsIdentityPBR</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap4.html#X7A280FC27BAD0EF0">4.5-7 IsUniversalPBR</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap4.html#X81EC86397E098BC8">4.5-8 IsBipartitionPBR</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap4.html#X7AF425D17BBE9023">4.5-9 IsTransformationPBR</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap4.html#X7962D03186B1AFDF">4.5-10 IsDualTransformationPBR</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap4.html#X7883CD5D824CC236">4.5-11 IsPartialPermPBR</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap4.html#X85B21BB0835FE166">4.5-12 IsPermPBR</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap4.html#X7ECD4BBD7A0E834E">4.6 <span class="Heading">
      Semigroups of PBRs
    </span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap4.html#X8554A3F878A4DC73">4.6-1 IsPBRSemigroup</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap4.html#X80FC004C7B65B4C0">4.6-2 DegreeOfPBRSemigroup</a></span>
</div></div>
</div>

<h3>4 <span class="Heading">
    Partitioned binary relations (PBRs)
  </span></h3>

<p>In this chapter we describe the functions in <strong class="pkg">Semigroups</strong> for creating and manipulating partitioned binary relations, henceforth referred to by their acronym PBRs. We begin by describing what these objects are.</p>

<p>PBRs were introduced in the paper <a href="chapBib.html#biBMartin2011aa">[MM13]</a> as, roughly speaking, the maximum generalization of bipartitions and related objects. Although, mathematically, bipartitions are a special type of PBR, in <strong class="pkg">Semigroups</strong> bipartitions and PBRs are currently distinct types of objects. It is possible to change the representation from bipartition to PBR, and from PBR to bipartition, when appropriate; see Section <a href="chap4.html#X86B714987C01895F"><span class="RefLink">4.3</span></a> for more details. The reason for this distinct is largely historical, bipartition appeared in the literature, and in the <strong class="pkg">Semigroups</strong> package, before PBRs.</p>

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

<h4>4.1 <span class="Heading">The family and categories of PBRs</span></h4>

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

<h5>4.1-1 IsPBR</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsPBR</code>( <var class="Arg">obj</var> )</td><td class="tdright">( category )</td></tr></table></div>
<p>Returns: <code class="keyw">true</code> or <code class="keyw">false</code>.</p>

<p>Every PBR in <strong class="pkg">GAP</strong> belongs to the category <code class="code">IsPBR</code>. Basic operations for PBRs are <code class="func">DegreeOfPBR</code> (<a href="chap4.html#X785B576B7823D626"><span class="RefLink">4.5-2</span></a>), <code class="func">ExtRepOfObj</code> (<a href="chap4.html#X78302D7E81BB1E54"><span class="RefLink">4.5-3</span></a>), <code class="func">PBRNumber</code> (<a href="chap4.html#X7F4C8A2B79E6D963"><span class="RefLink">4.5-4</span></a>), <code class="func">NumberPBR</code> (<a href="chap4.html#X7F4C8A2B79E6D963"><span class="RefLink">4.5-4</span></a>), <code class="func">StarOp</code> (<a href="chap4.html#X7DFC277E80A50C2F"><span class="RefLink">4.5-1</span></a>), and multiplication of two PBRs of equal degree is via <code class="keyw">*</code>.</p>

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

<h5>4.1-2 IsPBRCollection</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsPBRCollection</code>( <var class="Arg">obj</var> )</td><td class="tdright">( category )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsPBRCollColl</code>( <var class="Arg">obj</var> )</td><td class="tdright">( category )</td></tr></table></div>
<p>Returns: <code class="keyw">true</code> or <code class="keyw">false</code>.</p>

<p>Every collection of PBRs belongs to the category <code class="code">IsPBRCollection</code>. For example, PBR semigroups belong to <code class="code">IsPBRCollection</code>.</p>

<p>Every collection of collections of PBRs belongs to <code class="code">IsPBRCollColl</code>. For example, a list of PBR semigroups belongs to <code class="code">IsPBRCollColl</code>.</p>

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

<h4>4.2 <span class="Heading">Creating PBRs</span></h4>

<p>There are several ways of creating PBRs in <strong class="pkg">GAP</strong>, which are described in this section.</p>

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

<h5>4.2-1 PBR</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ PBR</code>( <var class="Arg">left</var>, <var class="Arg">right</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Returns: A PBR.</p>

<p>The arguments <var class="Arg">left</var> and <var class="Arg">right</var> of this function should each be a list of length <code class="code">n</code> whose entries are lists of integers in the ranges <code class="code">[-n .. -1]</code> and <code class="code">[1 .. n]</code> for some <code class="code">n</code> greater than 0.</p>

<p>Given such an argument, <code class="code">PBR</code> returns the PBR <code class="code">x</code> where:</p>


<ul>
<li><p>for each <code class="code">i</code> in the range <code class="code">[1 .. n]</code> there is an edge from <code class="code">i</code> to every <code class="code">j</code> in <var class="Arg">left[i]</var>;</p>

</li>
<li><p>for each <code class="code">i</code> in the range <code class="code">[-n .. -1]</code> there is an edge from <code class="code">i</code> to every <code class="code">j</code> in <var class="Arg">right[-i]</var>;</p>

</li>
</ul>
<p><code class="code">PBR</code> returns an error if the argument does not define a PBR.</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">PBR([[-3, -2, -1, 2, 3], [-1], [-3, -2, 1, 2]],</span>
<span class="GAPprompt">></span> <span class="GAPinput">       [[-2, -1, 1, 2, 3], [3], [-3, -2, -1, 1, 3]]);</span>
PBR([ [ -3, -2, -1, 2, 3 ], [ -1 ], [ -3, -2, 1, 2 ] ],
  [ [ -2, -1, 1, 2, 3 ], [ 3 ], [ -3, -2, -1, 1, 3 ] ])</pre></div>

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

<h5>4.2-2 RandomPBR</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ RandomPBR</code>( <var class="Arg">n</var>[, <var class="Arg">p</var>] )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Returns: A PBR.</p>

<p>If <var class="Arg">n</var> is a positive integer and <var class="Arg">p</var> is an float between <code class="code">0</code> and <code class="code">1</code>, then <code class="code">RandomPBR</code> returns a random PBR of degree <var class="Arg">n</var> where the probability of there being an edge from <code class="code">i</code> to <code class="code">j</code> is approximately <code class="code">p</code>.</p>

<p>If the optional second argument is not present, then a random value <var class="Arg">p</var> is used (chosen with uniform probability).</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">RandomPBR(6);</span>
PBR(
  [ [ -5, 1, 2, 3 ], [ -6, -3, -1, 2, 5 ], [ -5, -2, 2, 3, 5 ],
      [ -6, -4, -1, 2, 3, 6 ], [ -4, -1, 2, 4 ],
      [ -5, -3, -1, 1, 2, 3, 5 ] ],
  [ [ -6, -4, -2, 1, 3, 5, 6 ], [ -5, -2, 1, 2, 3, 5 ],
      [ -6, -5, -2, 1, 5 ], [ -6, -5, -3, -2, 1, 3, 4 ],
      [ -6, -5, -4, -2, 3, 5 ], [ -6, -4, -2, -1, 1, 2, 6 ] ])</pre></div>

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

<h5>4.2-3 EmptyPBR</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ EmptyPBR</code>( <var class="Arg">n</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Returns: A PBR.</p>

<p>If <var class="Arg">n</var> is a positive integer, then <code class="code">EmptyPBR</code> returns the PBR of degree <var class="Arg">n</var> with no edges.</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">x := EmptyPBR(3);</span>
PBR([ [  ], [  ], [  ] ], [ [  ], [  ], [  ] ])
<span class="GAPprompt">gap></span> <span class="GAPinput">IsEmptyPBR(x);</span>
true</pre></div>

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

<h5>4.2-4 IdentityPBR</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IdentityPBR</code>( <var class="Arg">n</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Returns: A PBR.</p>

<p>If <var class="Arg">n</var> is a positive integer, then <code class="code">IdentityPBR</code> returns the identity PBR of degree <var class="Arg">n</var>. This PBR has <code class="code">2</code><var class="Arg">n</var> edges: specifically, for each <code class="code">i</code> in the ranges <code class="code">[1 .. n]</code> and <code class="code">[-n .. -1]</code>, the identity PBR has an edge from <code class="code">i</code> to <code class="code">-i</code>.</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">x := IdentityPBR(3);</span>
PBR([ [ -1 ], [ -2 ], [ -3 ] ], [ [ 1 ], [ 2 ], [ 3 ] ])
<span class="GAPprompt">gap></span> <span class="GAPinput">IsIdentityPBR(x);</span>
true</pre></div>

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

<h5>4.2-5 UniversalPBR</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ UniversalPBR</code>( <var class="Arg">n</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Returns: A PBR.</p>

<p>If <var class="Arg">n</var> is a positive integer, then <code class="code">UniversalPBR</code> returns the PBR of degree <var class="Arg">n</var> with <code class="code">4 * n ^ 2</code> edges, i.e. every possible edge.</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">x := UniversalPBR(2);</span>
PBR([ [ -2, -1, 1, 2 ], [ -2, -1, 1, 2 ] ],
  [ [ -2, -1, 1, 2 ], [ -2, -1, 1, 2 ] ])
<span class="GAPprompt">gap></span> <span class="GAPinput">IsUniversalPBR(x);</span>
true</pre></div>

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

<h4>4.3 <span class="Heading">Changing the representation of a PBR</span></h4>

<p>It is possible that a PBR can be represented as another type of object, or that another type of <strong class="pkg">GAP</strong> object can be represented as a PBR. In this section, we describe the functions in the <strong class="pkg">Semigroups</strong> package for changing the representation of PBR, or for changing the representation of another type of object to that of a PBR.</p>

<p>The operations <code class="func">AsPermutation</code> (<a href="chap4.html#X86786B297FBCD064"><span class="RefLink">4.3-4</span></a>), <code class="func">AsPartialPerm</code> (<a href="chap4.html#X795B1C16819905E8"><span class="RefLink">4.3-3</span></a>), <code class="func">AsTransformation</code> (<a href="chap4.html#X8407F516825A514A"><span class="RefLink">4.3-2</span></a>), <code class="func">AsBipartition</code> (<a href="chap3.html#X855126D98583C181"><span class="RefLink">3.3-1</span></a>), <code class="func">AsBooleanMat</code> (<a href="chap5.html#X7DA524567E0E7E16"><span class="RefLink">5.3-2</span></a>) can be used to convert PBRs into permutations, partial permutations, transformations, bipartitions, and boolean matrices where appropriate.</p>

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

<h5>4.3-1 AsPBR</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ AsPBR</code>( <var class="Arg">x</var>[, <var class="Arg">n</var>] )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Returns: A PBR.</p>

<p><code class="code">AsPBR</code> returns the boolean matrix, bipartition, transformation, partial permutation, or permutation <var class="Arg">x</var> as a PBR of degree <var class="Arg">n</var>.</p>

<p>There are several possible arguments for <code class="code">AsPBR</code>:</p>


<dl>
<dt><strong class="Mark">bipartitions</strong></dt>
<dd><p>If <var class="Arg">x</var> is a bipartition and <var class="Arg">n</var> is a positive integer, then <code class="code">AsPBR</code> returns a PBR corresponding to <var class="Arg">x</var> with degree <var class="Arg">n</var>. The resulting PBR has an edge from <code class="code">i</code> to <code class="code">j</code> whenever <code class="code">i</code> and <code class="code">j</code> belong to the same block of <var class="Arg">x</var>.</p>

<p>If the optional second argument <var class="Arg">n</var> is not specified, then degree of the bipartition <var class="Arg">x</var> is used by default.</p>

</dd>
<dt><strong class="Mark">boolean matrices</strong></dt>
<dd><p>If <var class="Arg">x</var> is a boolean matrix of even dimension <code class="code">2 * m</code> and <var class="Arg">n</var> is a positive integer, then <code class="code">AsPBR</code> returns a PBR corresponding to <var class="Arg">x</var> with degree <var class="Arg">n</var>. If the optional second argument <var class="Arg">n</var> is not specified, then dimension of the boolean matrix <var class="Arg">x</var> is used by default.</p>

</dd>
<dt><strong class="Mark">transformations, partial perms, permutations</strong></dt>
<dd><p>If <var class="Arg">x</var> is a transformation, partial perm, or permutation and <var class="Arg">n</var> is a positive integer, then <code class="code">AsPBR</code> is a synonym for <code class="code">AsPBR(AsBipartition(<var class="Arg">x</var>, <var class="Arg">n</var>))</code>. If the optional second argument <var class="Arg">n</var> is not specified, then <code class="code">AsPBR</code> is a synonym for <code class="code">AsPBR(AsBipartition(<var class="Arg">x</var>))</code>. See <code class="func">AsBipartition</code> (<a href="chap3.html#X855126D98583C181"><span class="RefLink">3.3-1</span></a>) for more details.</p>

</dd>
</dl>

<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">x := Bipartition([[1, 2, -1], [3, -2], [4, -3, -4]]);</span>
<block bijection: [ 1, 2, -1 ], [ 3, -2 ], [ 4, -3, -4 ]>
<span class="GAPprompt">gap></span> <span class="GAPinput">AsPBR(x, 2);</span>
PBR([ [ -1, 1, 2 ], [ -1, 1, 2 ] ], [ [ -1, 1, 2 ], [ -2 ] ])
<span class="GAPprompt">gap></span> <span class="GAPinput">AsPBR(x, 5);</span>
PBR([ [ -1, 1, 2 ], [ -1, 1, 2 ], [ -2, 3 ], [ -4, -3, 4 ], [  ] ],
  [ [ -1, 1, 2 ], [ -2, 3 ], [ -4, -3, 4 ], [ -4, -3, 4 ], [  ] ])
<span class="GAPprompt">gap></span> <span class="GAPinput">AsPBR(x);</span>
PBR([ [ -1, 1, 2 ], [ -1, 1, 2 ], [ -2, 3 ], [ -4, -3, 4 ] ],
  [ [ -1, 1, 2 ], [ -2, 3 ], [ -4, -3, 4 ], [ -4, -3, 4 ] ])
<span class="GAPprompt">gap></span> <span class="GAPinput">mat := Matrix(IsBooleanMat, [[1, 0, 0, 1],</span>
<span class="GAPprompt">></span> <span class="GAPinput">                                [0, 1, 1, 0],</span>
<span class="GAPprompt">></span> <span class="GAPinput">                                [1, 0, 1, 1],</span>
<span class="GAPprompt">></span> <span class="GAPinput">                                [0, 0, 0, 1]]);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">AsPBR(mat);</span>
PBR([ [ -2, 1 ], [ -1, 2 ] ], [ [ -2, -1, 1 ], [ -2 ] ])
<span class="GAPprompt">gap></span> <span class="GAPinput">AsPBR(mat, 2);</span>
PBR([ [ 1 ] ], [ [ -1 ] ])
<span class="GAPprompt">gap></span> <span class="GAPinput">AsPBR(mat, 6);</span>
PBR([ [ -2, 1 ], [ -1, 2 ], [  ] ], [ [ -2, -1, 1 ], [ -2 ], [  ] ])
<span class="GAPprompt">gap></span> <span class="GAPinput">x := Transformation([2, 2, 1]);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">AsPBR(x);</span>
PBR([ [ -2 ], [ -2 ], [ -1 ] ], [ [ 3 ], [ 1, 2 ], [  ] ])
<span class="GAPprompt">gap></span> <span class="GAPinput">AsPBR(x, 2);</span>
PBR([ [ -2 ], [ -2 ] ], [ [  ], [ 1, 2 ] ])
<span class="GAPprompt">gap></span> <span class="GAPinput">AsPBR(x, 4);</span>
PBR([ [ -2 ], [ -2 ], [ -1 ], [ -4 ] ],
  [ [ 3 ], [ 1, 2 ], [  ], [ 4 ] ])
<span class="GAPprompt">gap></span> <span class="GAPinput">x := PartialPerm([4, 3]);</span>
[1,4][2,3]
<span class="GAPprompt">gap></span> <span class="GAPinput">AsPBR(x);</span>
PBR([ [ -4 ], [ -3 ], [  ], [  ] ], [ [  ], [  ], [ 2 ], [ 1 ] ])
<span class="GAPprompt">gap></span> <span class="GAPinput">AsPBR(x, 2);</span>
PBR([ [  ], [  ] ], [ [  ], [  ] ])
<span class="GAPprompt">gap></span> <span class="GAPinput">AsPBR(x, 5);</span>
PBR([ [ -4 ], [ -3 ], [  ], [  ], [  ] ],
  [ [  ], [  ], [ 2 ], [ 1 ], [  ] ])
<span class="GAPprompt">gap></span> <span class="GAPinput">x := (1, 3)(2, 4);</span>
(1,3)(2,4)
<span class="GAPprompt">gap></span> <span class="GAPinput">AsPBR(x);</span>
PBR([ [ -3, 1 ], [ -4, 2 ], [ -1, 3 ], [ -2, 4 ] ],
  [ [ -1, 3 ], [ -2, 4 ], [ -3, 1 ], [ -4, 2 ] ])
<span class="GAPprompt">gap></span> <span class="GAPinput">AsPBR(x, 5);</span>
PBR([ [ -3, 1 ], [ -4, 2 ], [ -1, 3 ], [ -2, 4 ], [ -5, 5 ] ],
  [ [ -1, 3 ], [ -2, 4 ], [ -3, 1 ], [ -4, 2 ], [ -5, 5 ] ])</pre></div>

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

<h5>4.3-2 AsTransformation</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ AsTransformation</code>( <var class="Arg">x</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>Returns: A transformation.</p>

<p>When the argument <var class="Arg">x</var> is a PBR which satisfies <code class="func">IsTransformationPBR</code> (<a href="chap4.html#X7AF425D17BBE9023"><span class="RefLink">4.5-9</span></a>), then this attribute returns that transformation.</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">x := PBR([[-3], [-3], [-2]], [[], [3], [1, 2]]);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">IsTransformationPBR(x);</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">AsTransformation(x);</span>
Transformation( [ 3, 3, 2 ] )
<span class="GAPprompt">gap></span> <span class="GAPinput">x := PBR([[1], [1, 2]], [[-2, -1], [-2, -1]]);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">AsTransformation(x);</span>
Error, the argument (a pbr) does not define a transformation</pre></div>

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

<h5>4.3-3 AsPartialPerm</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ AsPartialPerm</code>( <var class="Arg">x</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Returns: A partial perm.</p>

<p>When the argument <var class="Arg">x</var> is a PBR which satisfies <code class="func">IsPartialPermPBR</code> (<a href="chap4.html#X7883CD5D824CC236"><span class="RefLink">4.5-11</span></a>), then this function returns that partial perm.</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">x := PBR([[-1, 1], [-3, 2], [-4, 3], [4], [5]],</span>
<span class="GAPprompt">></span> <span class="GAPinput">            [[-1, 1], [-2], [-3, 2], [-4, 3], [-5]]);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">IsPartialPermPBR(x);</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">AsPartialPerm(x);</span>
[2,3,4](1)</pre></div>

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

<h5>4.3-4 AsPermutation</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ AsPermutation</code>( <var class="Arg">x</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>Returns: A permutation.</p>

<p>When the argument <var class="Arg">x</var> is a PBR which satisfies <code class="func">IsPermPBR</code> (<a href="chap4.html#X85B21BB0835FE166"><span class="RefLink">4.5-12</span></a>), then this attribute returns that permutation.</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">x := PBR([[-1, 1], [-4, 2], [-2, 3], [-3, 4]],</span>
<span class="GAPprompt">></span> <span class="GAPinput">            [[-1, 1], [-2, 3], [-3, 4], [-4, 2]]);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">IsPermPBR(x);</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">AsPermutation(x);</span>
(2,4,3)</pre></div>

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

<h4>4.4 <span class="Heading">Operators for PBRs</span></h4>


<dl>
<dt><strong class="Mark"><code class="code"><var class="Arg">x</var> * <var class="Arg">y</var></code></strong></dt>
<dd><p>returns the product of <var class="Arg">x</var> and <var class="Arg">y</var> when <var class="Arg">x</var> and <var class="Arg">y</var> are PBRs.</p>

</dd>
<dt><strong class="Mark"><code class="code"><var class="Arg">x</var> < <var class="Arg">y</var></code></strong></dt>
<dd><p>returns <code class="keyw">true</code> if the degree of <var class="Arg">x</var> is less than the degree of <var class="Arg">y</var>, or the degrees are equal and the out-neighbours of <var class="Arg">x</var> (as a list of list of positive integers) is lexicographically less than the out-neighbours of <var class="Arg">y</var>.</p>

</dd>
<dt><strong class="Mark"><code class="code"><var class="Arg">x</var> = <var class="Arg">y</var></code></strong></dt>
<dd><p>returns <code class="keyw">true</code> if the PBR <var class="Arg">x</var> equals the PBR <var class="Arg">y</var> and returns <code class="keyw">false</code> if it does not.</p>

</dd>
</dl>
<p><a id="X78EC8E597EB99730" name="X78EC8E597EB99730"></a></p>

<h4>4.5 <span class="Heading">Attributes for PBRs</span></h4>

<p>In this section we describe various attributes that a PBR can possess.</p>

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

<h5>4.5-1 StarOp</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ StarOp</code>( <var class="Arg">x</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">‣ Star</code>( <var class="Arg">x</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>Returns: A PBR.</p>

<p><code class="code">StarOp</code> returns the unique PBR <code class="code">y</code> obtained by exchanging the positive and negative numbers in <var class="Arg">x</var> (i.e. multiplying <code class="func">ExtRepOfObj</code> (<a href="chap4.html#X78302D7E81BB1E54"><span class="RefLink">4.5-3</span></a>) by <code class="code">-1</code> and swapping its first and second components).</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">x := PBR([[], [-1], []], [[-3, -2, 2, 3], [-2, 1], []]);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">Star(x);</span>
PBR([ [ -3, -2, 2, 3 ], [ -1, 2 ], [  ] ], [ [  ], [ 1 ], [  ] ])</pre></div>

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

<h5>4.5-2 DegreeOfPBR</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ DegreeOfPBR</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">‣ DegreeOfPBRCollection</code>( <var class="Arg">x</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>Returns: A positive integer.</p>

<p>The degree of a PBR is, roughly speaking, the number of points where it is defined. More precisely, if <var class="Arg">x</var> is a PBR defined on <code class="code">2 * n</code> points, then the degree of <var class="Arg">x</var> is <code class="code">n</code>.</p>

<p>The degree of a collection <var class="Arg">coll</var> of PBRs of equal degree is just the degree of any (and every) PBR in <var class="Arg">coll</var>. The degree of collection of PBRs of unequal degrees is not defined.</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">x := PBR([[-2], [-2, -1, 2, 3], [-1, 1, 2, 3]],</span>
<span class="GAPprompt">></span> <span class="GAPinput">            [[-1, 1], [2, 3], [-3, 2, 3]]);</span>
PBR([ [ -2 ], [ -2, -1, 2, 3 ], [ -1, 1, 2, 3 ] ],
  [ [ -1, 1 ], [ 2, 3 ], [ -3, 2, 3 ] ])
<span class="GAPprompt">gap></span> <span class="GAPinput">DegreeOfPBR(x);</span>
3
<span class="GAPprompt">gap></span> <span class="GAPinput">S := FullPBRMonoid(2);</span>
<pbr monoid of degree 2 with 10 generators>
<span class="GAPprompt">gap></span> <span class="GAPinput">DegreeOfPBRCollection(S);</span>
2</pre></div>

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

<h5>4.5-3 ExtRepOfObj</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ ExtRepOfObj</code>( <var class="Arg">x</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Returns: A pair of lists of lists of integers.</p>

<p>If <code class="code">n</code> is the degree of the PBR <var class="Arg">x</var>, then <code class="code">ExtRepOfObj</code> returns the argument required by <code class="func">PBR</code> (<a href="chap4.html#X82A8646F7C70CF3B"><span class="RefLink">4.2-1</span></a>) to create a PBR equal to <var class="Arg">x</var>, i.e. <code class="code">PBR(ExtRepOfObj(<var class="Arg">x</var>))</code> returns a PBR equal to <var class="Arg">x</var>.</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">x := PBR([[-1, 1], [-2, 2]],</span>
<span class="GAPprompt">></span> <span class="GAPinput">            [[-2, -1, 1], [-1, 1, 2]]);</span>
PBR([ [ -1, 1 ], [ -2, 2 ] ], [ [ -2, -1, 1 ], [ -1, 1, 2 ] ])
<span class="GAPprompt">gap></span> <span class="GAPinput">ExtRepOfObj(x);</span>
[ [ [ -1, 1 ], [ -2, 2 ] ], [ [ -2, -1, 1 ], [ -1, 1, 2 ] ] ]</pre></div>

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

<h5>4.5-4 PBRNumber</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ PBRNumber</code>( <var class="Arg">m</var>, <var class="Arg">n</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">‣ NumberPBR</code>( <var class="Arg">mat</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Returns: A PBR, or a positive integer.</p>

<p>These functions implement a bijection from the set of all PBRs of degree <var class="Arg">n</var> and the numbers <code class="code">[1 .. 2 ^ (4 * <var class="Arg">n</var> ^ 2)]</code>.</p>

<p>More precisely, if <var class="Arg">m</var> and <var class="Arg">n</var> are positive integers such that <var class="Arg">m</var> is at most <code class="code">2 ^ (4 * <var class="Arg">n</var> ^ 2)</code>, then <code class="code">PBRNumber</code> returns the <var class="Arg">m</var>th PBR of degree <var class="Arg">n</var>.</p>

<p>If <var class="Arg">mat</var> is a PBR of degree <var class="Arg">n</var>, then <code class="code">NumberPBR</code> returns the number in <code class="code">[1 .. 2 ^ (4 * <var class="Arg">n</var> ^ 2)]</code> that corresponds to <var class="Arg">mat</var>.</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">S := FullPBRMonoid(1);</span>
<pbr monoid of degree 1 with 4 generators>
<span class="GAPprompt">gap></span> <span class="GAPinput">List(S, NumberPBR);</span>
[ 3, 15, 5, 7, 8, 1, 4, 11, 13, 16, 6, 2, 9, 12, 14, 10 ]</pre></div>

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

<h5>4.5-5 IsEmptyPBR</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsEmptyPBR</code>( <var class="Arg">x</var> )</td><td class="tdright">( property )</td></tr></table></div>
<p>Returns: <code class="keyw">true</code> or <code class="keyw">false</code>.</p>

<p>A PBR is <strong class="button">empty</strong> if it has no edges. <code class="code">IsEmptyPBR</code> returns <code class="keyw">true</code> if the PBR <var class="Arg">x</var> is empty and <code class="keyw">false</code> if it is not.</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">x := PBR([[]], [[]]);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">IsEmptyPBR(x);</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">x := PBR([[-2, 1], [2]], [[-1], [-2, 1]]);</span>
PBR([ [ -2, 1 ], [ 2 ] ], [ [ -1 ], [ -2, 1 ] ])
<span class="GAPprompt">gap></span> <span class="GAPinput">IsEmptyPBR(x);</span>
false</pre></div>

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

<h5>4.5-6 IsIdentityPBR</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsIdentityPBR</code>( <var class="Arg">x</var> )</td><td class="tdright">( property )</td></tr></table></div>
<p>Returns: <code class="keyw">true</code> or <code class="keyw">false</code>.</p>

<p>A PBR of degree <code class="code">n</code> is the <strong class="button">identity</strong> PBR of degree <code class="code">n</code> if it is the identity of the full PBR monoid of degree <code class="code">n</code>. The identity PBR of degree <code class="code">n</code> has <code class="code">2n</code> edges. Specifically, for each <code class="code">i</code> in the ranges <code class="code">[1 .. n]</code> and <code class="code">[-n .. -1]</code>, the identity PBR has an edge from <code class="code">i</code> to <code class="code">-i</code>.</p>

<p><code class="code">IsIdentityPBR</code> returns <code class="keyw">true</code> is the PBR <var class="Arg">x</var> is an identity PBR and <code class="keyw">false</code> if it is not.</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">x := PBR([[-2], [-1]], [[1], [2]]);</span>
PBR([ [ -2 ], [ -1 ] ], [ [ 1 ], [ 2 ] ])
<span class="GAPprompt">gap></span> <span class="GAPinput">IsIdentityPBR(x);</span>
false
<span class="GAPprompt">gap></span> <span class="GAPinput">x := PBR([[-1]], [[1]]);</span>
PBR([ [ -1 ] ], [ [ 1 ] ])
<span class="GAPprompt">gap></span> <span class="GAPinput">IsIdentityPBR(x);</span>
true</pre></div>

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

<h5>4.5-7 IsUniversalPBR</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsUniversalPBR</code>( <var class="Arg">x</var> )</td><td class="tdright">( property )</td></tr></table></div>
<p>Returns: <code class="keyw">true</code> or <code class="keyw">false</code>.</p>

<p>A PBR of degree <code class="code">n</code> is <strong class="button">universal</strong> if it has <code class="code">4 * n ^ 2</code> edges, i.e. every possible edge.</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">x := PBR([[]], [[]]);</span>
PBR([ [  ] ], [ [  ] ])
<span class="GAPprompt">gap></span> <span class="GAPinput">IsUniversalPBR(x);</span>
false
<span class="GAPprompt">gap></span> <span class="GAPinput">x := PBR([[-2, 1], [2]], [[-1], [-2, 1]]);</span>
PBR([ [ -2, 1 ], [ 2 ] ], [ [ -1 ], [ -2, 1 ] ])
<span class="GAPprompt">gap></span> <span class="GAPinput">IsUniversalPBR(x);</span>
false
<span class="GAPprompt">gap></span> <span class="GAPinput">x := PBR([[-1, 1]], [[-1, 1]]);</span>
PBR([ [ -1, 1 ] ], [ [ -1, 1 ] ])
<span class="GAPprompt">gap></span> <span class="GAPinput">IsUniversalPBR(x);</span>
true</pre></div>

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

<h5>4.5-8 IsBipartitionPBR</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsBipartitionPBR</code>( <var class="Arg">x</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">‣ IsBlockBijectionPBR</code>( <var class="Arg">x</var> )</td><td class="tdright">( property )</td></tr></table></div>
<p>Returns: <code class="keyw">true</code> or <code class="keyw">false</code>.</p>

<p>If the PBR <var class="Arg">x</var> defines a bipartition, then <code class="code">IsBipartitionPBR</code> returns <code class="keyw">true</code>, and if not, then it returns <code class="keyw">false</code>.</p>

<p>A PBR <var class="Arg">x</var> defines a bipartition if and only if when considered as a boolean matrix it is an equivalence.</p>

<p>If <var class="Arg">x</var> satisfies <code class="code">IsBipartitionPBR</code> and when considered as a bipartition it is a block bijection, then <code class="code">IsBlockBijectionPBR</code> returns <code class="keyw">true</code>.</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">x := PBR([[-1, 3], [-1, 3], [-2, 1, 2, 3]],</span>
<span class="GAPprompt">></span> <span class="GAPinput">            [[-2, -1, 2], [-2, -1, 1, 2, 3],</span>
<span class="GAPprompt">></span> <span class="GAPinput">             [-2, -1, 1, 2]]);</span>
PBR([ [ -1, 3 ], [ -1, 3 ], [ -2, 1, 2, 3 ] ],
  [ [ -2, -1, 2 ], [ -2, -1, 1, 2, 3 ], [ -2, -1, 1, 2 ] ])
<span class="GAPprompt">gap></span> <span class="GAPinput">IsBipartitionPBR(x);</span>
false
<span class="GAPprompt">gap></span> <span class="GAPinput">x := PBR([[-2, -1, 1], [2, 3], [2, 3]],</span>
<span class="GAPprompt">></span> <span class="GAPinput">            [[-2, -1, 1], [-2, -1, 1], [-3]]);</span>
PBR([ [ -2, -1, 1 ], [ 2, 3 ], [ 2, 3 ] ],
  [ [ -2, -1, 1 ], [ -2, -1, 1 ], [ -3 ] ])
<span class="GAPprompt">gap></span> <span class="GAPinput">IsBipartitionPBR(x);</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">IsBlockBijectionPBR(x);</span>
false</pre></div>

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

<h5>4.5-9 IsTransformationPBR</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsTransformationPBR</code>( <var class="Arg">x</var> )</td><td class="tdright">( property )</td></tr></table></div>
<p>Returns: <code class="keyw">true</code> or <code class="keyw">false</code>.</p>

<p>If the PBR <var class="Arg">x</var> defines a transformation, then <code class="code">IsTransformationPBR</code> returns <code class="keyw">true</code>, and if not, then <code class="keyw">false</code> is returned.</p>

<p>A PBR <var class="Arg">x</var> defines a transformation if and only if it satisfies <code class="func">IsBipartitionPBR</code> (<a href="chap4.html#X81EC86397E098BC8"><span class="RefLink">4.5-8</span></a>) and when it is considered as a bipartition it satisfies <code class="func">IsTransBipartition</code> (<a href="chap3.html#X79C556827A578509"><span class="RefLink">3.5-12</span></a>).</p>

<p>With this definition, <code class="func">AsPBR</code> (<a href="chap4.html#X81CBBE6080439596"><span class="RefLink">4.3-1</span></a>) and <code class="func">AsTransformation</code> (<a href="chap4.html#X8407F516825A514A"><span class="RefLink">4.3-2</span></a>) define mutually inverse isomorphisms from the full transformation monoid of degree <code class="code">n</code> to the submonoid of the full PBR monoid of degree <code class="code">n</code> consisting of all the elements satisfying <code class="code">IsTransformationPBR</code>.</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">x := PBR([[-3], [-1], [-3]], [[2], [], [1, 3]]);</span>
PBR([ [ -3 ], [ -1 ], [ -3 ] ], [ [ 2 ], [  ], [ 1, 3 ] ])
<span class="GAPprompt">gap></span> <span class="GAPinput">IsTransformationPBR(x);</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">x := AsTransformation(x);</span>
Transformation( [ 3, 1, 3 ] )
<span class="GAPprompt">gap></span> <span class="GAPinput">AsPBR(x) * AsPBR(x) = AsPBR(x ^ 2);</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">Number(FullPBRMonoid(1), IsTransformationPBR);</span>
1
<span class="GAPprompt">gap></span> <span class="GAPinput">x := PBR([[-2, -1, 2], [-2, 1, 2]], [[-1, 1], [-2]]);</span>
PBR([ [ -2, -1, 2 ], [ -2, 1, 2 ] ], [ [ -1, 1 ], [ -2 ] ])
<span class="GAPprompt">gap></span> <span class="GAPinput">IsTransformationPBR(x);</span>
false</pre></div>

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

<h5>4.5-10 IsDualTransformationPBR</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsDualTransformationPBR</code>( <var class="Arg">x</var> )</td><td class="tdright">( property )</td></tr></table></div>
<p>Returns: <code class="keyw">true</code> or <code class="keyw">false</code>.</p>

<p>If the PBR <var class="Arg">x</var> defines a dual transformation, then <code class="code">IsDualTransformationPBR</code> returns <code class="keyw">true</code>, and if not, then <code class="keyw">false</code> is returned.</p>

<p>A PBR <var class="Arg">x</var> defines a dual transformation if and only if <code class="code">Star(<var class="Arg">x</var>)</code> satisfies <code class="func">IsTransformationPBR</code> (<a href="chap4.html#X7AF425D17BBE9023"><span class="RefLink">4.5-9</span></a>).</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">x := PBR([[-3, 1, 3], [-1, 2], [-3, 1, 3]],</span>
<span class="GAPprompt">></span> <span class="GAPinput">            [[-1, 2], [-2], [-3, 1, 3]]);</span>
PBR([ [ -3, 1, 3 ], [ -1, 2 ], [ -3, 1, 3 ] ],
  [ [ -1, 2 ], [ -2 ], [ -3, 1, 3 ] ])
<span class="GAPprompt">gap></span> <span class="GAPinput">IsDualTransformationPBR(x);</span>
false
<span class="GAPprompt">gap></span> <span class="GAPinput">IsDualTransformationPBR(Star(x));</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">Number(FullPBRMonoid(1), IsDualTransformationPBR);</span>
1</pre></div>

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

<h5>4.5-11 IsPartialPermPBR</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsPartialPermPBR</code>( <var class="Arg">x</var> )</td><td class="tdright">( property )</td></tr></table></div>
<p>Returns: <code class="keyw">true</code> or <code class="keyw">false</code>.</p>

<p>If the PBR <var class="Arg">x</var> defines a partial permutation, then <code class="code">IsPartialPermPBR</code> returns <code class="keyw">true</code>, and if not, then <code class="keyw">false</code> is returned.</p>

<p>A PBR <var class="Arg">x</var> defines a partial perm if and only if it satisfies <code class="func">IsBipartitionPBR</code> (<a href="chap4.html#X81EC86397E098BC8"><span class="RefLink">4.5-8</span></a>) and and when it is considered as a bipartition it satisfies <code class="func">IsPartialPermBipartition</code> (<a href="chap3.html#X87C771D37B1FE95C"><span class="RefLink">3.5-15</span></a>).</p>

<p>With this definition, <code class="func">AsPBR</code> (<a href="chap4.html#X81CBBE6080439596"><span class="RefLink">4.3-1</span></a>) and <code class="func">AsPartialPerm</code> (<a href="chap4.html#X795B1C16819905E8"><span class="RefLink">4.3-3</span></a>) define mutually inverse isomorphisms from the symmetric inverse monoid of degree <code class="code">n</code> to the submonoid of the full PBR monoid of degree <code class="code">n</code> consisting of all the elements satisfying <code class="code">IsPartialPermPBR</code>.</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">x := PBR([[-1, 1], [2]], [[-1, 1], [-2]]);</span>
PBR([ [ -1, 1 ], [ 2 ] ], [ [ -1, 1 ], [ -2 ] ])
<span class="GAPprompt">gap></span> <span class="GAPinput">IsPartialPermPBR(x);</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">x := PartialPerm([3, 1]);</span>
[2,1,3]
<span class="GAPprompt">gap></span> <span class="GAPinput">AsPBR(x) * AsPBR(x) = AsPBR(x ^ 2);</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">Number(FullPBRMonoid(1), IsPartialPermPBR);</span>
2</pre></div>

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

<h5>4.5-12 IsPermPBR</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsPermPBR</code>( <var class="Arg">x</var> )</td><td class="tdright">( property )</td></tr></table></div>
<p>Returns: <code class="keyw">true</code> or <code class="keyw">false</code>.</p>

<p>If the PBR <var class="Arg">x</var> defines a permutation, then <code class="code">IsPermPBR</code> returns <code class="keyw">true</code>, and if not, then <code class="keyw">false</code> is returned.</p>

<p>A PBR <var class="Arg">x</var> defines a permutation if and only if it satisfies <code class="func">IsBipartitionPBR</code> (<a href="chap4.html#X81EC86397E098BC8"><span class="RefLink">4.5-8</span></a>) and and when it is considered as a bipartition it satisfies <code class="func">IsPermBipartition</code> (<a href="chap3.html#X8031B53E7D0ECCFA"><span class="RefLink">3.5-14</span></a>).</p>

<p>With this definition, <code class="func">AsPBR</code> (<a href="chap4.html#X81CBBE6080439596"><span class="RefLink">4.3-1</span></a>) and <code class="func">AsPermutation</code> (<a href="chap4.html#X86786B297FBCD064"><span class="RefLink">4.3-4</span></a>) define mutually inverse isomorphisms from the symmetric group of degree <code class="code">n</code> to the subgroup of the full PBR monoid of degree <code class="code">n</code> consisting of all the elements satisfying <code class="code">IsPermPBR</code> (i.e. the <code class="func">GroupOfUnits</code> (<a href="chap11.html#X811AEDD88280C277"><span class="RefLink">11.9-1</span></a>) of the full PBR monoid of degree <code class="code">n</code>).</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">x := PBR([[-2, 1], [-4, 2], [-1, 3], [-3, 4]],</span>
<span class="GAPprompt">></span> <span class="GAPinput">[[-1, 3], [-2, 1], [-3, 4], [-4, 2]]);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">IsPermPBR(x);</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">x := (1, 5)(2, 4, 3);</span>
(1,5)(2,4,3)
<span class="GAPprompt">gap></span> <span class="GAPinput">y := (1, 4, 3)(2, 5);</span>
(1,4,3)(2,5)
<span class="GAPprompt">gap></span> <span class="GAPinput">AsPBR(x) * AsPBR(y) = AsPBR(x * y);</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">Number(FullPBRMonoid(1), IsPermPBR);</span>
1</pre></div>

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

<h4>4.6 <span class="Heading">
      Semigroups of PBRs
    </span></h4>

<p>Semigroups and monoids of PBRs can be created in the usual way in <strong class="pkg">GAP</strong> using the functions <code class="func">Semigroup</code> (<a href="../../../doc/ref/chap51_mj.html#X7F55D28F819B2817"><span class="RefLink">Reference: Semigroup</span></a>) and <code class="func">Monoid</code> (<a href="../../../doc/ref/chap51_mj.html#X7F95328B7C7E49EA"><span class="RefLink">Reference: Monoid</span></a>); see Chapter <a href="chap6.html#X7995B4F18672DDB0"><span class="RefLink">6</span></a> for more details.</p>

<p>It is possible to create inverse semigroups and monoids of PBRs using <code class="func">InverseSemigroup</code> (<a href="../../../doc/ref/chap51_mj.html#X78B13FED7AFB4326"><span class="RefLink">Reference: InverseSemigroup</span></a>) and <code class="func">InverseMonoid</code> (<a href="../../../doc/ref/chap51_mj.html#X80D9B9A98736051B"><span class="RefLink">Reference: InverseMonoid</span></a>) when the argument is a collection of PBRs satisfying <code class="func">IsBipartitionPBR</code> (<a href="chap4.html#X81EC86397E098BC8"><span class="RefLink">4.5-8</span></a>) and when considered as bipartitions, the collection satisfies <code class="code">IsGeneratorsOfInverseSemigroup</code>.</p>

<p>Note that every PBR semigroup in <strong class="pkg">Semigroups</strong> is finite.</p>

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

<h5>4.6-1 IsPBRSemigroup</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsPBRSemigroup</code>( <var class="Arg">S</var> )</td><td class="tdright">( filter )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsPBRMonoid</code>( <var class="Arg">S</var> )</td><td class="tdright">( filter )</td></tr></table></div>
<p>Returns: <code class="keyw">true</code> or <code class="keyw">false</code>.</p>

<p>A <em>PBR semigroup</em> is simply a semigroup consisting of PBRs. An object <var class="Arg">obj</var> is a PBR semigroup in <strong class="pkg">GAP</strong> if it satisfies <code class="func">IsSemigroup</code> (<a href="../../../doc/ref/chap51_mj.html#X7B412E5B8543E9B7"><span class="RefLink">Reference: IsSemigroup</span></a>) and <code class="func">IsPBRCollection</code> (<a href="chap4.html#X854A9CEA7AC14C0A"><span class="RefLink">4.1-2</span></a>).</p>

<p>A <em>PBR monoid</em> is a monoid consisting of PBRs. An object <var class="Arg">obj</var> is a PBR monoid in <strong class="pkg">GAP</strong> if it satisfies <code class="func">IsMonoid</code> (<a href="../../../doc/ref/chap51_mj.html#X861C523483C6248C"><span class="RefLink">Reference: IsMonoid</span></a>) and <code class="func">IsPBRCollection</code> (<a href="chap4.html#X854A9CEA7AC14C0A"><span class="RefLink">4.1-2</span></a>).</p>

<p>Note that it is possible for a PBR semigroup to have a multiplicative neutral element (i.e. an identity element) but not to satisfy <code class="code">IsPBRMonoid</code>. For example,</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">x := PBR([[-2, -1, 3], [-2, 2], [-3, -2, 1, 2, 3]],</span>
<span class="GAPprompt">></span> <span class="GAPinput">            [[-3, -2, -1, 2, 3], [-3, -2, -1, 2, 3], [-1]]);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">S := Semigroup(x, One(x));</span>
<commutative pbr monoid of degree 3 with 1 generator>
<span class="GAPprompt">gap></span> <span class="GAPinput">IsMonoid(S);</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">IsPBRMonoid(S);</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">S := Semigroup([</span>
<span class="GAPprompt">></span> <span class="GAPinput"> PBR([[-2, 1], [-3, 2], [-1, 3], [-4, 4, 5], [-4, 4, 5]],</span>
<span class="GAPprompt">></span> <span class="GAPinput">     [[-1, 3], [-2, 1], [-3, 2], [-4, 4, 5], [-5]]),</span>
<span class="GAPprompt">></span> <span class="GAPinput"> PBR([[-2, 1], [-1, 2], [-3, 3], [-4, 4, 5], [-4, 4, 5]],</span>
<span class="GAPprompt">></span> <span class="GAPinput">     [[-1, 2], [-2, 1], [-3, 3], [-4, 4, 5], [-5]]),</span>
<span class="GAPprompt">></span> <span class="GAPinput"> PBR([[-1, 1, 3], [-2, 2], [-1, 1, 3], [-4, 4, 5], [-4, 4, 5]],</span>
<span class="GAPprompt">></span> <span class="GAPinput">     [[-1, 1, 3], [-2, 2], [-3], [-4, 4, 5], [-5]])]);</span>
<pbr semigroup of degree 5 with 3 generators>
<span class="GAPprompt">gap></span> <span class="GAPinput">One(S);</span>
fail
<span class="GAPprompt">gap></span> <span class="GAPinput">MultiplicativeNeutralElement(S);</span>
PBR([ [ -1, 1 ], [ -2, 2 ], [ -3, 3 ], [ -4, 4, 5 ], [ -4, 4, 5 ] ],
  [ [ -1, 1 ], [ -2, 2 ], [ -3, 3 ], [ -4, 4, 5 ], [ -5 ] ])
<span class="GAPprompt">gap></span> <span class="GAPinput">IsPBRMonoid(S);</span>
false</pre></div>

<p>In this example <code class="code">S</code> cannot be converted into a monoid using <code class="func">AsMonoid</code> (<a href="../../../doc/ref/chap51_mj.html#X7B22038F832B9C0F"><span class="RefLink">Reference: AsMonoid</span></a>) since the <code class="func">One</code> (<a href="../../../doc/ref/chap31_mj.html#X8046262384895B2A"><span class="RefLink">Reference: One</span></a>) of any element in <code class="code">S</code> differs from the multiplicative neutral element.</p>

<p>For more details see <code class="func">IsMagmaWithOne</code> (<a href="../../../doc/ref/chap35_mj.html#X86071DE7835F1C7C"><span class="RefLink">Reference: IsMagmaWithOne</span></a>).</p>

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

<h5>4.6-2 DegreeOfPBRSemigroup</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ DegreeOfPBRSemigroup</code>( <var class="Arg">S</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>Returns: A non-negative integer.</p>

<p>The <em>degree</em> of a PBR semigroup <var class="Arg">S</var> is just the degree of any (and every) element of <var class="Arg">S</var>.</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">S := Semigroup(</span>
<span class="GAPprompt">></span> <span class="GAPinput"> PBR([[-1, 1], [-2, 2], [-3, 3]],</span>
<span class="GAPprompt">></span> <span class="GAPinput">     [[-1, 1], [-2, 2], [-3, 3]]),</span>
<span class="GAPprompt">></span> <span class="GAPinput"> PBR([[1, 2], [1, 2], [-3, 3]],</span>
<span class="GAPprompt">></span> <span class="GAPinput">     [[-2, -1], [-2, -1], [-3, 3]]),</span>
<span class="GAPprompt">></span> <span class="GAPinput"> PBR([[-1, 1], [2, 3], [2, 3]],</span>
<span class="GAPprompt">></span> <span class="GAPinput">     [[-1, 1], [-3, -2], [-3, -2]]));</span>
<pbr semigroup of degree 3 with 3 generators>
<span class="GAPprompt">gap></span> <span class="GAPinput">DegreeOfPBRSemigroup(S);</span>
3</pre></div>


<div class="chlinkprevnextbot"> <a href="chap0.html">[Top of Book]</a>   <a href="chap0.html#contents">[Contents]</a>    <a href="chap3.html">[Previous Chapter]</a>    <a href="chap5.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="chap13.html">13</a>  <a href="chap14.html">14</a>  <a href="chap15.html">15</a>  <a href="chap16.html">16</a>  <a href="chap17.html">17</a>  <a href="chap18.html">18</a>  <a href="chapBib.html">Bib</a>  <a href="chapInd.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>

100%


¤ Diese beiden folgenden Angebotsgruppen bietet das Unternehmen0.27Angebot  Wie Sie bei der Firma Beratungs- und Dienstleistungen beauftragen können  ¤

*Eine klare Vorstellung vom Zielzustand




Wurzel

Suchen

Beweissystem der NASA

Beweissystem Isabelle

NIST Cobol Testsuite

Cephes Mathematical Library

Wiener Entwicklungsmethode

Haftungshinweis

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.