Quellcodebibliothek Statistik Leitseite products/Sources/formale Sprachen/GAP/pkg/loops/data/rcc/   (GAP Algebra Version 4.15.1©)  Datei vom 29.7.2024 mit Größe 20 B image not shown  

SSL chap5_mj.html   Sprache: unbekannt

 
<?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 (Semigroups) - Chapter 5: 
    Matrices over semirings
  </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="chap5"  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="chap12_mj.html">12</a>  <a href="chap13_mj.html">13</a>  <a href="chap14_mj.html">14</a>  <a href="chap15_mj.html">15</a>  <a href="chap16_mj.html">16</a>  <a href="chap17_mj.html">17</a>  <a href="chap18_mj.html">18</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="chap4_mj.html">[Previous Chapter]</a>    <a href="chap6_mj.html">[Next Chapter]</a>   </div>

<p id="mathjaxlink" class="pcenter"><a href="chap5.html">[MathJax off]</a></p>
<p><a id="X82D6B7FE7CAC0AFA" name="X82D6B7FE7CAC0AFA"></a></p>
<div class="ChapSects"><a href="chap5_mj.html#X82D6B7FE7CAC0AFA">5 <span class="Heading">
    Matrices over semirings
  </span></a>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap5_mj.html#X7ECF673C7BE2384D">5.1 <span class="Heading">Creating matrices over semirings</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap5_mj.html#X8711618C7A8A1B60">5.1-1 IsMatrixOverSemiring</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap5_mj.html#X86F696B883677D6B">5.1-2 IsMatrixOverSemiringCollection</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap5_mj.html#X7C1CDA817CE076FD">5.1-3 DimensionOfMatrixOverSemiring</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap5_mj.html#X7FF0B2A783BA2D06">5.1-4 DimensionOfMatrixOverSemiringCollection</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap5_mj.html#X7DCA234C86ED8BD3">5.1-5 Matrix</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap5_mj.html#X85426D8885431ECE">5.1-6 AsMatrix</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap5_mj.html#X82172D747D66C8CC">5.1-7 RandomMatrix</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap5_mj.html#X782480C686F1A663">5.1-8 <span class="Heading">Matrix filters</span></a>
</span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap5_mj.html#X86233A3E86512493">5.1-9 <span class="Heading">Matrix collection filters</span></a>
</span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap5_mj.html#X8289FCCC8274C89D">5.1-10 AsList</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap5_mj.html#X7D21408E845E4648">5.1-11 ThresholdTropicalMatrix</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap5_mj.html#X7874559881FE8779">5.1-12 ThresholdNTPMatrix</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap5_mj.html#X807E402687741CDA">5.2 <span class="Heading">Operators for matrices over semirings</span></a>
</span>
</div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap5_mj.html#X844A32A184E5EB75">5.3 <span class="Heading">
      Boolean matrices
    </span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap5_mj.html#X84A16D4D7D015885">5.3-1 BooleanMat</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap5_mj.html#X7DA524567E0E7E16">5.3-2 AsBooleanMat</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap5_mj.html#X87BDB89B7AAFE8AD"><code>5.3-3 \in</code></a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap5_mj.html#X8629FA5F7B682078">5.3-4 OnBlist</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap5_mj.html#X85E2FD8B82652876">5.3-5 Successors</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap5_mj.html#X7E0FD5878106AB66">5.3-6 BooleanMatNumber</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap5_mj.html#X793A1C277C1D7D6D">5.3-7 BlistNumber</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap5_mj.html#X7EEA5011862E6298">5.3-8 CanonicalBooleanMat</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap5_mj.html#X794C91597CC9F784">5.3-9 IsRowTrimBooleanMat</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap5_mj.html#X7D22BA78790EFBC6">5.3-10 IsSymmetricBooleanMat</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap5_mj.html#X7C373B7D87044050">5.3-11 IsReflexiveBooleanMat</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap5_mj.html#X7CDAD39B856AC3E5">5.3-12 IsTransitiveBooleanMat</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap5_mj.html#X8570C8A08549383D">5.3-13 IsAntiSymmetricBooleanMat</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap5_mj.html#X7A68D87982A07C6F">5.3-14 IsTotalBooleanMat</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap5_mj.html#X7D9BECEA7E9B72A7">5.3-15 IsPartialOrderBooleanMat</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap5_mj.html#X82EA957982B79827">5.3-16 IsEquivalenceBooleanMat</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap5_mj.html#X7E6B588887D34A0A">5.3-17 IsTransformationBooleanMat</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap5_mj.html#X873822B6830CE367">5.4 <span class="Heading">
      Matrices over finite fields
    </span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap5_mj.html#X857E626783CCF766">5.4-1 RowSpaceBasis</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap5_mj.html#X8733B04781B682E5">5.4-2 RightInverse</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap5_mj.html#X8770A88E82AA24B7">5.5 <span class="Heading">
      Matrices over the integers
    </span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap5_mj.html#X7BC66ECE8378068E">5.5-1 InverseOp</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap5_mj.html#X7CA636F080777C36">5.5-2 IsTorsion</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap5_mj.html#X84F59A2687C62763">5.5-3 Order</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap5_mj.html#X86BFFFBC87F2AB1E">5.6 <span class="Heading">
      Max-plus and min-plus matrices
    </span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap5_mj.html#X82EC4F49877D6EB1">5.6-1 InverseOp</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap5_mj.html#X83663A5387042B69">5.6-2 RadialEigenvector</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap5_mj.html#X83FCFB368743E4BA">5.6-3 SpectralRadius</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap5_mj.html#X869F60527C2B9328">5.6-4 UnweightedPrecedenceDigraph</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap5_mj.html#X79B614AA803BD103">5.7 <span class="Heading">
      Matrix semigroups
    </span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap5_mj.html#X7DC6EB0680B3E4DD">5.7-1 <span class="Heading">Matrix semigroup filters</span></a>
</span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap5_mj.html#X8616225581BC7414">5.7-2 <span class="Heading">Matrix monoid filters</span></a>
</span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap5_mj.html#X808A4061809A6E67">5.7-3 IsFinite</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap5_mj.html#X80C6B26284721409">5.7-4 IsTorsion</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap5_mj.html#X873DE466868DA849">5.7-5 NormalizeSemigroup</a></span>
</div></div>
</div>

<h3>5 <span class="Heading">
    Matrices over semirings
  </span></h3>

<p>In this chapter we describe the functionality in <strong class="pkg">Semigroups</strong> for creating matrices over semirings. <strong class="button">Only square matrices are currently supported.</strong> We use the term <strong class="button">matrix</strong> to mean <strong class="button">square matrix</strong> everywhere in this manual.</p>

<p>For reference, matrices over the following semirings are currently supported:</p>


<dl>
<dt><strong class="Mark">the Boolean semiring</strong></dt>
<dd><p>the set <span class="SimpleMath">\(\{0, 1\}\)</span> where <span class="SimpleMath">\(0 + 0 = 0\)</span>, <span class="SimpleMath">\(0 + 1 = 1 + 1 = 1 + 0 = 1\)</span>, <span class="SimpleMath">\(1\cdot 0 = 0 \cdot 0 = 0 \cdot 1 = 0\)</span>, and <span class="SimpleMath">\(1\cdot 1 = 1\)</span>.</p>

</dd>
<dt><strong class="Mark">the max-plus semiring</strong></dt>
<dd><p>the set of integers and negative infinity <span class="SimpleMath">\(\mathbb{Z}\cup \{-\infty\}\)</span> with operations max and plus.</p>

</dd>
<dt><strong class="Mark">the min-plus semiring</strong></dt>
<dd><p>the set of integers and infinity <span class="SimpleMath">\(\mathbb{Z}\cup \{\infty\}\)</span> with operations min and plus;</p>

</dd>
<dt><strong class="Mark">tropical max-plus semirings</strong></dt>
<dd><p>the set <span class="SimpleMath">\(\{-\infty, 0, 1, \ldots, t\}\)</span> for some threshold <span class="SimpleMath">\(t\)</span> with operations max and plus;</p>

</dd>
<dt><strong class="Mark">tropical min-plus semirings</strong></dt>
<dd><p>the set <span class="SimpleMath">\(\{0, 1, \ldots, t, \infty\}\)</span> for some threshold <span class="SimpleMath">\(t\)</span> with operations min and plus;</p>

</dd>
<dt><strong class="Mark">the semiring <span class="SimpleMath">\(\mathbb{N}_{t,p}\)</span></strong></dt>
<dd><p>the semiring <span class="SimpleMath">\(\mathbb{N}_{t,p} = \{0, 1, \ldots, t, t + 1, \ldots, t + p - 1\}\)</span> for some threshold <span class="SimpleMath">\(t\)</span> and period <span class="SimpleMath">\(p\)</span> under addition and multiplication modulo the congruence <span class="SimpleMath">\(t = t + p\)</span>;</p>

</dd>
<dt><strong class="Mark">the integers</strong></dt>
<dd><p>the usual ring of integers;</p>

</dd>
<dt><strong class="Mark">finite fields</strong></dt>
<dd><p>the finite fields <code class="code">GF(q^d)</code> for prime <code class="code">q</code> and some positive integer <code class="code">d</code>.</p>

</dd>
</dl>
<p>With the exception of matrices of finite fields, semigroups of matrices in <strong class="pkg">Semigroups</strong> are of the second type described in Section <a href="chap6_mj.html#X7A19D22B7A05CC2F"><span class="RefLink">6.1</span></a>. In other words, a version of the Froidure-Pin Algorithm <a href="chapBib_mj.html#biBFroidure1997aa">[FP97]</a> is used to compute semigroups of these types, i.e it is possible that all of the elements of such a semigroup are enumerated and stored in the memory of your computer.</p>

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

<h4>5.1 <span class="Heading">Creating matrices over semirings</span></h4>

<p>In this section we describe the two main operations for creating matrices over semirings in <strong class="pkg">Semigroups</strong>, and the categories, attributes, and operations which apply to every matrix over one of the semirings given at the start of this chapter.</p>

<p>There are several special methods for boolean matrices, which can be found in Section <a href="chap5_mj.html#X844A32A184E5EB75"><span class="RefLink">5.3</span></a>. There are also several special methods for finite fields, which can be found in section <a href="chap5_mj.html#X873822B6830CE367"><span class="RefLink">5.4</span></a>.</p>

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

<h5>5.1-1 IsMatrixOverSemiring</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; IsMatrixOverSemiring</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 matrix over a semiring in <strong class="pkg">Semigroups</strong> is a member of the category <code class="code">IsMatrixOverSemiring</code>, which is a subcategory of <code class="func">IsMultiplicativeElementWithOne</code> (<a href="../../../doc/ref/chap31_mj.html#X82BC294F7D388AE8"><span class="RefLink">Reference: IsMultiplicativeElementWithOne</span></a>), <code class="func">IsAssociativeElement</code> (<a href="../../../doc/ref/chap31_mj.html#X7979AFAA80FF795A"><span class="RefLink">Reference: IsAssociativeElement</span></a>), and <code class="code">IsPositionalObjectRep</code>; see <a href="../../../doc/ref/chap13_mj.html#X8698205F8648EB33"><span class="RefLink">Reference: Representation</span></a>.</p>

<p>Every matrix over a semiring in <strong class="pkg">Semigroups</strong> is a square matrix.</p>

<p>Basic operations for matrices over semirings are: <code class="func">DimensionOfMatrixOverSemiring</code> (<a href="chap5_mj.html#X7C1CDA817CE076FD"><span class="RefLink">5.1-3</span></a>), <code class="func">TransposedMat</code> (<a href="../../../doc/ref/chap24_mj.html#X7C52A38C79C36C35"><span class="RefLink">Reference: TransposedMat</span></a>), and <code class="func">One</code> (<a href="../../../doc/ref/chap31_mj.html#X8046262384895B2A"><span class="RefLink">Reference: One</span></a>).</p>

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

<h5>5.1-2 IsMatrixOverSemiringCollection</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; IsMatrixOverSemiringCollection</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">&#an style='color: green'>8227; IsMatrixOverSemiringCollColl</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 matrices over the same semiring belongs to the category <code class="code">IsMatrixOverSemiringCollection</code>. For example, semigroups of matrices over a semiring belong to <code class="code">IsMatrixOverSemiringCollection</code>.</p>

<p>Every collection of collections of matrices over the same semiring belongs to the category <code class="code">IsMatrixOverSemiringCollColl</code>. For example, a list of semigroups of matrices over semirings belongs to <code class="code">IsMatrixOverSemiringCollColl</code>.</p>

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

<h5>5.1-3 DimensionOfMatrixOverSemiring</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; DimensionOfMatrixOverSemiring</code>( <var class="Arg">mat</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>Returns: A positive integer.</p>

<p>If <var class="Arg">mat</var> is a matrix over a semiring (i.e. belongs to the category <code class="func">IsMatrixOverSemiring</code> (<a href="chap5_mj.html#X8711618C7A8A1B60"><span class="RefLink">5.1-1</span></a>)), then <var class="Arg">mat</var> is a square <code class="code">n</code> by <code class="code">n</code> matrix. <code class="code">DimensionOfMatrixOverSemiring</code> returns the dimension <code class="code">n</code> of <var class="Arg">mat</var>.</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">x := BooleanMat([[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>
Matrix(IsBooleanMat, [[1, 0, 0, 1], [0, 1, 1, 0], [1, 0, 1, 1],
  [0, 0, 0, 1]])
<span class="GAPprompt">gap></span> <span class="GAPinput">DimensionOfMatrixOverSemiring(x);</span>
4</pre></div>

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

<h5>5.1-4 DimensionOfMatrixOverSemiringCollection</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; DimensionOfMatrixOverSemiringCollection</code>( <var class="Arg">coll</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>Returns: A positive integer.</p>

<p>If <var class="Arg">coll</var> is a collection of matrices over a semiring (i.e. belongs to the category <code class="func">IsMatrixOverSemiringCollection</code> (<a href="chap5_mj.html#X86F696B883677D6B"><span class="RefLink">5.1-2</span></a>)), then the elements of <var class="Arg">coll</var> are square <code class="code">n</code> by <code class="code">n</code> matrices. <code class="code">DimensionOfMatrixOverSemiringCollection</code> returns the dimension <code class="code">n</code> of these matrices.</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">x := BooleanMat([[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>
Matrix(IsBooleanMat, [[1, 0, 0, 1], [0, 1, 1, 0], [1, 0, 1, 1],
  [0, 0, 0, 1]])
<span class="GAPprompt">gap></span> <span class="GAPinput">DimensionOfMatrixOverSemiringCollection(Semigroup(x));</span>
4</pre></div>

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

<h5>5.1-5 Matrix</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; Matrix</code>( <var class="Arg">filt</var>, <var class="Arg">mat</var>[, <var class="Arg">threshold</var>[, <var class="Arg">period</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; Matrix</code>( <var class="Arg">semiring</var>, <var class="Arg">mat</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Returns: A matrix over semiring.</p>

<p>This operation can be used to construct a matrix over a semiring in <strong class="pkg">Semigroups</strong>.</p>

<p>In its first form, the first argument <var class="Arg">filt</var> specifies the filter to be used to create the matrix, the second argument <var class="Arg">mat</var> is a <strong class="pkg">GAP</strong> matrix (i.e. a list of lists) compatible with <var class="Arg">filt</var>, the third and fourth arguments <var class="Arg">threshold</var> and <var class="Arg">period</var> (if required) must be positive integers.</p>


<dl>
<dt><strong class="Mark"><var class="Arg">filt</var></strong></dt>
<dd><p>This must be one of the filters given in Section <a href="chap5_mj.html#X782480C686F1A663"><span class="RefLink">5.1-8</span></a>.</p>

</dd>
<dt><strong class="Mark"><var class="Arg">mat</var></strong></dt>
<dd><p>This must be a list of <code class="code">n</code> lists each of length <code class="code">n</code> (i.e. a square matrix), consisting of elements belonging to the underlying semiring described by <var class="Arg">filt</var>, and <var class="Arg">threshold</var> and <var class="Arg">period</var> if present. An error is given if <var class="Arg">mat</var> is not compatible with the other arguments.</p>

<p>For example, if <var class="Arg">filt</var> is <code class="code">IsMaxPlusMatrix</code>, then the entries of <var class="Arg">mat</var> must belong to the max-plus semiring, i.e. they must be integers or -<span class="SimpleMath">\(\infty\)</span>.</p>

<p>The supported semirings are fully described at the start of this chapter.</p>

</dd>
<dt><strong class="Mark"><var class="Arg">threshold</var></strong></dt>
<dd><p>If <var class="Arg">filt</var> is any of <code class="func">IsTropicalMaxPlusMatrix</code> (<a href="chap5_mj.html#X782480C686F1A663"><span class="RefLink">5.1-8</span></a>), <code class="func">IsTropicalMinPlusMatrix</code> (<a href="chap5_mj.html#X782480C686F1A663"><span class="RefLink">5.1-8</span></a>), or <code class="func">IsNTPMatrix</code> (<a href="chap5_mj.html#X782480C686F1A663"><span class="RefLink">5.1-8</span></a>), then this argument specifies the threshold of the underlying semiring of the matrix being created.</p>

</dd>
<dt><strong class="Mark"><var class="Arg">period</var></strong></dt>
<dd><p>If <var class="Arg">filt</var> is <code class="func">IsNTPMatrix</code> (<a href="chap5_mj.html#X782480C686F1A663"><span class="RefLink">5.1-8</span></a>), then this argument specifies the period of the underlying semiring of the matrix being created.</p>

</dd>
</dl>
<p>In its second form, the arguments should be a semiring <var class="Arg">semiring</var> and matrix <var class="Arg">mat</var> with entries in <var class="Arg">semiring</var>. Currently, the only supported semirings are finite fields of prime order, and the integers <code class="func">Integers</code> (<a href="../../../doc/ref/chap14_mj.html#X853DF11B80068ED5"><span class="RefLink">Reference: Integers</span></a>).</p>

<p>The function <code class="func">BooleanMat</code> (<a href="chap5_mj.html#X84A16D4D7D015885"><span class="RefLink">5.3-1</span></a>) is provided for specifically creating boolean matrices.</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">Matrix(IsBooleanMat, [[1, 0, 0, 0],</span>
<span class="GAPprompt">></span> <span class="GAPinput">                         [0, 0, 0, 0],</span>
<span class="GAPprompt">></span> <span class="GAPinput">                         [1, 1, 1, 1],</span>
<span class="GAPprompt">></span> <span class="GAPinput">                         [1, 0, 1, 1]]);</span>
Matrix(IsBooleanMat, [[1, 0, 0, 0], [0, 0, 0, 0], [1, 1, 1, 1],
  [1, 0, 1, 1]])
<span class="GAPprompt">gap></span> <span class="GAPinput">Matrix(IsMaxPlusMatrix, [[4, 0, -2],</span>
<span class="GAPprompt">></span> <span class="GAPinput">                            [1, -3, 0],</span>
<span class="GAPprompt">></span> <span class="GAPinput">                            [5, -1, -4]]);</span>
Matrix(IsMaxPlusMatrix, [[4, 0, -2], [1, -3, 0], [5, -1, -4]])
<span class="GAPprompt">gap></span> <span class="GAPinput">Matrix(IsMinPlusMatrix, [[-1, infinity],</span>
<span class="GAPprompt">></span> <span class="GAPinput">                            [1, -1]]);</span>
Matrix(IsMinPlusMatrix, [[-1, infinity], [1, -1]])
<span class="GAPprompt">gap></span> <span class="GAPinput">Matrix(IsTropicalMaxPlusMatrix, [[3, 2, 4],</span>
<span class="GAPprompt">></span> <span class="GAPinput">                                    [3, 1, 1],</span>
<span class="GAPprompt">></span> <span class="GAPinput">                                    [-infinity, 1, 1]],</span>
<span class="GAPprompt">></span> <span class="GAPinput">          9);</span>
Matrix(IsTropicalMaxPlusMatrix, [[3, 2, 4], [3, 1, 1],
  [-infinity, 1, 1]], 9)
<span class="GAPprompt">gap></span> <span class="GAPinput">Matrix(IsTropicalMinPlusMatrix, [[1, 1, 1],</span>
<span class="GAPprompt">></span> <span class="GAPinput">                                    [0, 3, 0],</span>
<span class="GAPprompt">></span> <span class="GAPinput">                                    [1, 1, 3]],</span>
<span class="GAPprompt">></span> <span class="GAPinput">          9);</span>
Matrix(IsTropicalMinPlusMatrix, [[1, 1, 1], [0, 3, 0], [1, 1, 3]], 9)
<span class="GAPprompt">gap></span> <span class="GAPinput">Matrix(IsNTPMatrix, [[0, 0, 0],</span>
<span class="GAPprompt">></span> <span class="GAPinput">                        [2, 0, 1],</span>
<span class="GAPprompt">></span> <span class="GAPinput">                        [2, 2, 2]],</span>
<span class="GAPprompt">></span> <span class="GAPinput">          2, 1);</span>
Matrix(IsNTPMatrix, [[0, 0, 0], [2, 0, 1], [2, 2, 2]], 2, 1)
<span class="GAPprompt">gap></span> <span class="GAPinput">Matrix(Integers, [[-1, -2, 0],</span>
<span class="GAPprompt">></span> <span class="GAPinput">                     [0, 3, -1],</span>
<span class="GAPprompt">></span> <span class="GAPinput">                     [1, 0, -3]]);</span>
<3x3-matrix over Integers>
<span class="GAPprompt">gap></span> <span class="GAPinput">Matrix(Integers, [[-1, -2, 0],</span>
<span class="GAPprompt">></span> <span class="GAPinput">                     [0, 3, -1],</span>
<span class="GAPprompt">></span> <span class="GAPinput">                     [1, 0, -3]]);</span>
<3x3-matrix over Integers>
</pre></div>

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

<h5>5.1-6 AsMatrix</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; AsMatrix</code>( <var class="Arg">filt</var>, <var class="Arg">mat</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; AsMatrix</code>( <var class="Arg">filt</var>, <var class="Arg">mat</var>, <var class="Arg">threshold</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; AsMatrix</code>( <var class="Arg">filt</var>, <var class="Arg">mat</var>, <var class="Arg">threshold</var>, <var class="Arg">period</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Returns: A matrix.</p>

<p>This operation can be used to change the representation of certain matrices over semirings. If <var class="Arg">mat</var> is a matrix over a semiring (in the category <code class="func">IsMatrixOverSemiring</code> (<a href="chap5_mj.html#X8711618C7A8A1B60"><span class="RefLink">5.1-1</span></a>)), then <code class="code">AsMatrix</code> returns a new matrix corresponding to <var class="Arg">mat</var> of the type specified by the filter <var class="Arg">filt</var>, and if applicable the arguments <var class="Arg">threshold</var> and <var class="Arg">period</var>. The dimension of the matrix <var class="Arg">mat</var> is not changed by this operation.</p>

<p>The version of the operation with arguments <var class="Arg">filt</var> and <var class="Arg">mat</var> can be applied to:</p>


<ul>
<li><p><code class="func">IsMinPlusMatrix</code> (<a href="chap5_mj.html#X782480C686F1A663"><span class="RefLink">5.1-8</span></a>) and a tropical min-plus matrix (i.e. convert a tropical min-plus matrix to a (non-tropical) min-plus matrix);</p>

</li>
<li><p><code class="func">IsMaxPlusMatrix</code> (<a href="chap5_mj.html#X782480C686F1A663"><span class="RefLink">5.1-8</span></a>) and a tropical max-plus matrix;</p>

</li>
</ul>
<p>The version of the operation with arguments <var class="Arg">filt</var>, <var class="Arg">mat</var>, and <var class="Arg">threshold</var> can be applied to:</p>


<ul>
<li><p><code class="func">IsTropicalMinPlusMatrix</code> (<a href="chap5_mj.html#X782480C686F1A663"><span class="RefLink">5.1-8</span></a>), a tropical min-plus or min-plus matrix, and a value for the threshold of the resulting matrix.</p>

</li>
<li><p><code class="func">IsTropicalMaxPlusMatrix</code> (<a href="chap5_mj.html#X782480C686F1A663"><span class="RefLink">5.1-8</span></a>) and a tropical max-plus, or max-plus matrix, and a value for the threshold of the resulting matrix.</p>

</li>
</ul>
<p>The version of the operation with arguments <var class="Arg">filt</var>, <var class="Arg">mat</var>, <var class="Arg">threshold</var>, and <var class="Arg">period</var> can be applied to <code class="func">IsNTPMatrix</code> (<a href="chap5_mj.html#X782480C686F1A663"><span class="RefLink">5.1-8</span></a>) and an ntp matrix, or integer matrix.</p>

<p>When converting matrices with negative entries to an ntp, tropical max-plus, or tropical min-plus matrix, the entry is replaced with its absolute value.</p>

<p>When converting non-tropical matrices to tropical matrices entries higher than the specified threshold are reduced to the threshold.</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">mat := Matrix(IsTropicalMinPlusMatrix, [[0, 1, 3],</span>
<span class="GAPprompt">></span> <span class="GAPinput">                                           [1, 1, 6],</span>
<span class="GAPprompt">></span> <span class="GAPinput">                                           [0, 4, 2]], 10);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">AsMatrix(IsMinPlusMatrix, mat);</span>
Matrix(IsMinPlusMatrix, [[0, 1, 3], [1, 1, 6], [0, 4, 2]])
<span class="GAPprompt">gap></span> <span class="GAPinput">mat := Matrix(IsTropicalMaxPlusMatrix, [[-infinity, -infinity, 3],</span>
<span class="GAPprompt">></span> <span class="GAPinput">                                           [0, 1, 3],</span>
<span class="GAPprompt">></span> <span class="GAPinput">                                           [4, 1, 0]], 10);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">AsMatrix(IsMaxPlusMatrix, mat);</span>
Matrix(IsMaxPlusMatrix, [[-infinity, -infinity, 3], [0, 1, 3],
  [4, 1, 0]])
<span class="GAPprompt">gap></span> <span class="GAPinput">mat := Matrix(IsNTPMatrix, [[1, 2, 2],</span>
<span class="GAPprompt">></span> <span class="GAPinput">                               [0, 2, 0],</span>
<span class="GAPprompt">></span> <span class="GAPinput">                               [1, 3, 0]], 4, 5);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">Matrix(Integers, mat);</span>
<3x3-matrix over Integers>
<span class="GAPprompt">gap></span> <span class="GAPinput">mat := Matrix(IsMinPlusMatrix, [[0, 1, 3], [1, 1, 6], [0, 4, 2]]);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">mat := AsMatrix(IsTropicalMinPlusMatrix, mat, 2);</span>
Matrix(IsTropicalMinPlusMatrix, [[0, 1, 2], [1, 1, 2], [0, 2, 2]], 2)
<span class="GAPprompt">gap></span> <span class="GAPinput">mat := AsMatrix(IsTropicalMinPlusMatrix, mat, 1);</span>
Matrix(IsTropicalMinPlusMatrix, [[0, 1, 1], [1, 1, 1], [0, 1, 1]], 1)
<span class="GAPprompt">gap></span> <span class="GAPinput">mat := Matrix(IsTropicalMaxPlusMatrix, [[-infinity, -infinity, 3],</span>
<span class="GAPprompt">></span> <span class="GAPinput">                                           [0, 1, 3],</span>
<span class="GAPprompt">></span> <span class="GAPinput">                                           [4, 1, 0]], 10);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">AsMatrix(IsTropicalMaxPlusMatrix, mat, 4);</span>
Matrix(IsTropicalMaxPlusMatrix, [[-infinity, -infinity, 3],
  [0, 1, 3], [4, 1, 0]], 4)
<span class="GAPprompt">gap></span> <span class="GAPinput">mat := Matrix(IsMaxPlusMatrix, [[-infinity, -infinity, 3],</span>
<span class="GAPprompt">></span> <span class="GAPinput">                                   [0, 1, 3],</span>
<span class="GAPprompt">></span> <span class="GAPinput">                                   [4, 1, 0]]);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">AsMatrix(IsTropicalMaxPlusMatrix, mat, 10);</span>
Matrix(IsTropicalMaxPlusMatrix, [[-infinity, -infinity, 3],
  [0, 1, 3], [4, 1, 0]], 10)
<span class="GAPprompt">gap></span> <span class="GAPinput">mat := Matrix(IsNTPMatrix, [[0, 1, 0],</span>
<span class="GAPprompt">></span> <span class="GAPinput">                               [1, 3, 1],</span>
<span class="GAPprompt">></span> <span class="GAPinput">                               [1, 0, 1]], 10, 10);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">mat := AsMatrix(IsNTPMatrix, mat, 5, 6);</span>
Matrix(IsNTPMatrix, [[0, 1, 0], [1, 3, 1], [1, 0, 1]], 5, 6)
<span class="GAPprompt">gap></span> <span class="GAPinput">mat := AsMatrix(IsNTPMatrix, mat, 2, 6);</span>
Matrix(IsNTPMatrix, [[0, 1, 0], [1, 3, 1], [1, 0, 1]], 2, 6)
<span class="GAPprompt">gap></span> <span class="GAPinput">mat := AsMatrix(IsNTPMatrix, mat, 2, 1);</span>
Matrix(IsNTPMatrix, [[0, 1, 0], [1, 2, 1], [1, 0, 1]], 2, 1)
<span class="GAPprompt">gap></span> <span class="GAPinput">mat := Matrix(Integers, mat);</span>
<3x3-matrix over Integers>
<span class="GAPprompt">gap></span> <span class="GAPinput">AsMatrix(IsNTPMatrix, mat, 1, 2);</span>
Matrix(IsNTPMatrix, [[0, 1, 0], [1, 2, 1], [1, 0, 1]], 1, 2)</pre></div>

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

<h5>5.1-7 RandomMatrix</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; RandomMatrix</code>( <var class="Arg">filt</var>, <var class="Arg">dim</var>[, <var class="Arg">threshold</var>[, <var class="Arg">period</var>]] )</td><td class="tdright">( function )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; RandomMatrix</code>( <var class="Arg">semiring</var>, <var class="Arg">dim</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: A matrix over semiring.</p>

<p>This operation can be used to construct a random matrix over a semiring in <strong class="pkg">Semigroups</strong>. The usage of <code class="code">RandomMatrix</code> is similar to that of <code class="func">Matrix</code> (<a href="chap5_mj.html#X7DCA234C86ED8BD3"><span class="RefLink">5.1-5</span></a>).</p>

<p>In its first form, the first argument <var class="Arg">filt</var> specifies the filter to be used to create the matrix, the second argument <var class="Arg">dim</var> is dimension of the matrix, the third and fourth arguments <var class="Arg">threshold</var> and <var class="Arg">period</var> (if required) must be positive integers.</p>


<dl>
<dt><strong class="Mark"><var class="Arg">filt</var></strong></dt>
<dd><p>This must be one of the filters given in Section <a href="chap5_mj.html#X782480C686F1A663"><span class="RefLink">5.1-8</span></a>.</p>

</dd>
<dt><strong class="Mark"><var class="Arg">dim</var></strong></dt>
<dd><p>This must be a positive integer.</p>

</dd>
<dt><strong class="Mark"><var class="Arg">threshold</var></strong></dt>
<dd><p>If <var class="Arg">filt</var> is any of <code class="func">IsTropicalMaxPlusMatrix</code> (<a href="chap5_mj.html#X782480C686F1A663"><span class="RefLink">5.1-8</span></a>), <code class="func">IsTropicalMinPlusMatrix</code> (<a href="chap5_mj.html#X782480C686F1A663"><span class="RefLink">5.1-8</span></a>), or <code class="func">IsNTPMatrix</code> (<a href="chap5_mj.html#X782480C686F1A663"><span class="RefLink">5.1-8</span></a>), then this argument specifies the threshold of the underlying semiring of the matrix being created.</p>

</dd>
<dt><strong class="Mark"><var class="Arg">period</var></strong></dt>
<dd><p>If <var class="Arg">filt</var> is <code class="func">IsNTPMatrix</code> (<a href="chap5_mj.html#X782480C686F1A663"><span class="RefLink">5.1-8</span></a>), then this argument specifies the period of the underlying semiring of the matrix being created.</p>

</dd>
</dl>
<p>In its second form, the arguments should be a semiring <var class="Arg">semiring</var> and dimension <var class="Arg">dim</var>. Currently, the only supported semirings are finite fields of prime order and the integers <code class="func">Integers</code> (<a href="../../../doc/ref/chap14_mj.html#X853DF11B80068ED5"><span class="RefLink">Reference: Integers</span></a>).</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">RandomMatrix(IsBooleanMat, 3);</span>
Matrix(IsBooleanMat, [[1, 0, 0], [1, 0, 1], [1, 0, 1]])
<span class="GAPprompt">gap></span> <span class="GAPinput">RandomMatrix(IsMaxPlusMatrix, 2);</span>
Matrix(IsMaxPlusMatrix, [[1, -infinity], [1, 0]])
<span class="GAPprompt">gap></span> <span class="GAPinput">RandomMatrix(IsMinPlusMatrix, 3);</span>
Matrix(IsMinPlusMatrix, [[infinity, 2, infinity], [4, 0, -2], [1, -3, 0]])
<span class="GAPprompt">gap></span> <span class="GAPinput">RandomMatrix(IsTropicalMaxPlusMatrix, 3, 5);</span>
Matrix(IsTropicalMaxPlusMatrix, [[5, 1, 4], [1, -infinity, 1], [1, 0, 2]],
  5)
<span class="GAPprompt">gap></span> <span class="GAPinput">RandomMatrix(IsTropicalMinPlusMatrix, 3, 2);</span>
Matrix(IsTropicalMinPlusMatrix, [[1, -infinity, -infinity], [1, 1, 1],
  [2, 2, 1]], 2)
<span class="GAPprompt">gap></span> <span class="GAPinput">RandomMatrix(IsNTPMatrix, 3, 2, 5);</span>
Matrix(IsNTPMatrix, [[1, 1, 1], [1, 1, 0], [3, 0, 1]], 2, 5)
<span class="GAPprompt">gap></span> <span class="GAPinput">RandomMatrix(Integers, 2);</span>
Matrix(Integers, [[1, 3], [0, 0]])
<span class="GAPprompt">gap></span> <span class="GAPinput">RandomMatrix(Integers, 2);</span>
Matrix(Integers, [[-1, 0], [0, -1]])
<span class="GAPprompt">gap></span> <span class="GAPinput">RandomMatrix(GF(5), 1);</span>
Matrix(GF(5), [[Z(5)^0]])</pre></div>

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

<h5>5.1-8 <span class="Heading">Matrix filters</span></h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; IsBooleanMat</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">&#an style='color: green'>8227; IsMatrixOverFiniteField</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">&#an style='color: green'>8227; IsMaxPlusMatrix</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">&#an style='color: green'>8227; IsMinPlusMatrix</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">&#an style='color: green'>8227; IsTropicalMatrix</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">&#an style='color: green'>8227; IsTropicalMaxPlusMatrix</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">&#an style='color: green'>8227; IsTropicalMinPlusMatrix</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">&#an style='color: green'>8227; IsNTPMatrix</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">&#an style='color: green'>8227; Integers</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 matrix over a semiring in <strong class="pkg">Semigroups</strong> is a member of one of these categories, which are subcategory of <code class="func">IsMatrixOverSemiring</code> (<a href="chap5_mj.html#X8711618C7A8A1B60"><span class="RefLink">5.1-1</span></a>).</p>

<p><code class="code">IsTropicalMatrix</code> is a supercategory of <code class="code">IsTropicalMaxPlusMatrix</code> and <code class="code">IsTropicalMinPlusMatrix</code>.</p>

<p>Basic operations for matrices over semirings include: multiplication via \*, <code class="func">DimensionOfMatrixOverSemiring</code> (<a href="chap5_mj.html#X7C1CDA817CE076FD"><span class="RefLink">5.1-3</span></a>), <code class="func">One</code> (<a href="../../../doc/ref/chap31_mj.html#X8046262384895B2A"><span class="RefLink">Reference: One</span></a>), the underlying list of lists used to create the matrix can be accessed using <code class="func">AsList</code> (<a href="chap5_mj.html#X8289FCCC8274C89D"><span class="RefLink">5.1-10</span></a>), the rows of <code class="code">mat</code> can be accessed using <code class="code">mat[i]</code> where <code class="code">i</code> is between <code class="code">1</code> and the dimension of the matrix, it also possible to loop over the rows of a matrix; for tropical matrices <code class="func">ThresholdTropicalMatrix</code> (<a href="chap5_mj.html#X7D21408E845E4648"><span class="RefLink">5.1-11</span></a>); for ntp matrices <code class="func">ThresholdNTPMatrix</code> (<a href="chap5_mj.html#X7874559881FE8779"><span class="RefLink">5.1-12</span></a>) and <code class="func">PeriodNTPMatrix</code> (<a href="chap5_mj.html#X7874559881FE8779"><span class="RefLink">5.1-12</span></a>).</p>

<p>For matrices over finite fields see Section <a href="chap5_mj.html#X873822B6830CE367"><span class="RefLink">5.4</span></a>; for Boolean matrices more details can be found in Section <a href="chap5_mj.html#X844A32A184E5EB75"><span class="RefLink">5.3</span></a>.</p>

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

<h5>5.1-9 <span class="Heading">Matrix collection filters</span></h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; IsBooleanMatCollection</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">&#an style='color: green'>8227; IsBooleanMatCollColl</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">&#an style='color: green'>8227; IsMatrixOverFiniteFieldCollection</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">&#an style='color: green'>8227; IsMatrixOverFiniteFieldCollColl</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">&#an style='color: green'>8227; IsMaxPlusMatrixCollection</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">&#an style='color: green'>8227; IsMaxPlusMatrixCollColl</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">&#an style='color: green'>8227; IsMinPlusMatrixCollection</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">&#an style='color: green'>8227; IsMinPlusMatrixCollColl</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">&#an style='color: green'>8227; IsTropicalMatrixCollection</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">&#an style='color: green'>8227; IsTropicalMaxPlusMatrixCollection</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">&#an style='color: green'>8227; IsTropicalMaxPlusMatrixCollColl</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">&#an style='color: green'>8227; IsTropicalMinPlusMatrixCollection</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">&#an style='color: green'>8227; IsTropicalMinPlusMatrixCollColl</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">&#an style='color: green'>8227; IsNTPMatrixCollection</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">&#an style='color: green'>8227; IsNTPMatrixCollColl</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 matrices over the same semiring in <strong class="pkg">Semigroups</strong> belongs to one of the categories above. For example, semigroups of boolean matrices belong to <code class="code">IsBooleanMatCollection</code>.</p>

<p>Similarly, every collection of collections of matrices over the same semiring in <strong class="pkg">Semigroups</strong> belongs to one of the categories above.</p>

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

<h5>5.1-10 AsList</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; AsList</code>( <var class="Arg">mat</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; AsMutableList</code>( <var class="Arg">mat</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Returns: A list of lists.</p>

<p>If <var class="Arg">mat</var> is a matrix over a semiring (in the category <code class="func">IsMatrixOverSemiring</code> (<a href="chap5_mj.html#X8711618C7A8A1B60"><span class="RefLink">5.1-1</span></a>)), then <code class="code">AsList</code> returns the underlying list of lists of semiring elements corresponding to <var class="Arg">mat</var>. In this case, the returned list and all of its entries are immutable.</p>

<p>The operation <code class="code">AsMutableList</code> returns a mutable copy of the underlying list of lists of the matrix over semiring <var class="Arg">mat</var>.</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">mat := Matrix(IsNTPMatrix,</span>
<span class="GAPprompt">></span> <span class="GAPinput">                 [[0, 1, 0], [1, 3, 1], [1, 0, 1]], 5, 6);</span>
Matrix(IsNTPMatrix, [[0, 1, 0], [1, 3, 1], [1, 0, 1]], 5, 6)
<span class="GAPprompt">gap></span> <span class="GAPinput">list := AsList(mat);</span>
[ [ 0, 1, 0 ], [ 1, 3, 1 ], [ 1, 0, 1 ] ]
<span class="GAPprompt">gap></span> <span class="GAPinput">IsMutable(list);</span>
false
<span class="GAPprompt">gap></span> <span class="GAPinput">IsMutable(list[1]);</span>
false
<span class="GAPprompt">gap></span> <span class="GAPinput">list := AsMutableList(mat);</span>
[ [ 0, 1, 0 ], [ 1, 3, 1 ], [ 1, 0, 1 ] ]
<span class="GAPprompt">gap></span> <span class="GAPinput">IsMutable(list);</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">IsMutable(list[1]);</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">mat = Matrix(IsNTPMatrix, AsList(mat), 5, 6);</span>
true</pre></div>

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

<h5>5.1-11 ThresholdTropicalMatrix</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; ThresholdTropicalMatrix</code>( <var class="Arg">mat</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>Returns: A positive integer.</p>

<p>If <var class="Arg">mat</var> is a tropical matrix (i.e. belongs to the category <code class="func">IsTropicalMatrix</code> (<a href="chap5_mj.html#X782480C686F1A663"><span class="RefLink">5.1-8</span></a>)), then <code class="code">ThresholdTropicalMatrix</code> returns the threshold (i.e. the largest integer) of the underlying semiring.</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">mat := Matrix(IsTropicalMaxPlusMatrix,</span>
<span class="GAPprompt">></span> <span class="GAPinput">[[0, 3, 0, 2],</span>
<span class="GAPprompt">></span> <span class="GAPinput"> [1, 1, 1, 0],</span>
<span class="GAPprompt">></span> <span class="GAPinput"> [-infinity, 1, -infinity, 1],</span>
<span class="GAPprompt">></span> <span class="GAPinput"> [0, -infinity, 2, -infinity]], 10);</span>
Matrix(IsTropicalMaxPlusMatrix, [[0, 3, 0, 2], [1, 1, 1, 0],
  [-infinity, 1, -infinity, 1], [0, -infinity, 2, -infinity]], 10)
<span class="GAPprompt">gap></span> <span class="GAPinput">ThresholdTropicalMatrix(mat);</span>
10
<span class="GAPprompt">gap></span> <span class="GAPinput">mat := Matrix(IsTropicalMaxPlusMatrix,</span>
<span class="GAPprompt">></span> <span class="GAPinput">[[0, 3, 0, 2],</span>
<span class="GAPprompt">></span> <span class="GAPinput"> [1, 1, 1, 0],</span>
<span class="GAPprompt">></span> <span class="GAPinput"> [-infinity, 1, -infinity, 1],</span>
<span class="GAPprompt">></span> <span class="GAPinput"> [0, -infinity, 2, -infinity]], 3);</span>
Matrix(IsTropicalMaxPlusMatrix, [[0, 3, 0, 2], [1, 1, 1, 0],
  [-infinity, 1, -infinity, 1], [0, -infinity, 2, -infinity]], 3)
<span class="GAPprompt">gap></span> <span class="GAPinput">ThresholdTropicalMatrix(mat);</span>
3</pre></div>

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

<h5>5.1-12 ThresholdNTPMatrix</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; ThresholdNTPMatrix</code>( <var class="Arg">mat</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; PeriodNTPMatrix</code>( <var class="Arg">mat</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>Returns: A positive integer.</p>

<p>An <strong class="button">ntp matrix</strong> is a matrix with entries in a semiring <span class="SimpleMath">\(\mathbb{N}_{t,p} = \{0, 1, \ldots, t, t + 1, \ldots, t + p - 1\}\)</span> for some threshold <span class="SimpleMath">\(t\)</span> and period <span class="SimpleMath">\(p\)</span> under addition and multiplication modulo the congruence <span class="SimpleMath">\(t = t + p\)</span>.</p>

<p>If <var class="Arg">mat</var> is a ntp matrix (i.e. belongs to the category <code class="func">IsNTPMatrix</code> (<a href="chap5_mj.html#X782480C686F1A663"><span class="RefLink">5.1-8</span></a>)), then <code class="code">ThresholdNTPMatrix</code> and <code class="code">PeriodNTPMatrix</code> return the threshold and period of the underlying semiring, respectively.</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">mat := Matrix(IsNTPMatrix, [[1, 1, 0],</span>
<span class="GAPprompt">></span> <span class="GAPinput">                               [2, 1, 0],</span>
<span class="GAPprompt">></span> <span class="GAPinput">                               [0, 1, 1]],</span>
<span class="GAPprompt">></span> <span class="GAPinput">                 1, 2);</span>
Matrix(IsNTPMatrix, [[1, 1, 0], [2, 1, 0], [0, 1, 1]], 1, 2)
<span class="GAPprompt">gap></span> <span class="GAPinput">ThresholdNTPMatrix(mat);</span>
1
<span class="GAPprompt">gap></span> <span class="GAPinput">PeriodNTPMatrix(mat);</span>
2
<span class="GAPprompt">gap></span> <span class="GAPinput">mat := Matrix(IsNTPMatrix, [[2, 1, 3],</span>
<span class="GAPprompt">></span> <span class="GAPinput">                               [0, 5, 1],</span>
<span class="GAPprompt">></span> <span class="GAPinput">                               [4, 1, 0]],</span>
<span class="GAPprompt">></span> <span class="GAPinput">                 3, 4);</span>
Matrix(IsNTPMatrix, [[2, 1, 3], [0, 5, 1], [4, 1, 0]], 3, 4)
<span class="GAPprompt">gap></span> <span class="GAPinput">ThresholdNTPMatrix(mat);</span>
3
<span class="GAPprompt">gap></span> <span class="GAPinput">PeriodNTPMatrix(mat);</span>
4</pre></div>

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

<h4>5.2 <span class="Heading">Operators for matrices over semirings</span></h4>


<dl>
<dt><strong class="Mark"><code class="code"><var class="Arg">mat1</var> * <var class="Arg">mat2</var></code></strong></dt>
<dd><p>returns the product of the matrices <var class="Arg">mat1</var> and <var class="Arg">mat2</var> of equal dimension over the same semiring using the usual matrix multiplication with the operations <code class="code">+</code> and <code class="code">*</code> from the underlying semiring.</p>

</dd>
<dt><strong class="Mark"><code class="code"><var class="Arg">mat1</var> < <var class="Arg">mat2</var></code></strong></dt>
<dd><p>returns <code class="keyw">true</code> if when considered as a list of rows, the matrix <var class="Arg">mat1</var> is short-lex less than the matrix <var class="Arg">mat2</var>, and <code class="keyw">false</code> if this is not the case. This means that a matrix of lower dimension is less than a matrix of higher dimension.</p>

</dd>
<dt><strong class="Mark"><code class="code"><var class="Arg">mat1</var> = <var class="Arg">mat2</var></code></strong></dt>
<dd><p>returns <code class="keyw">true</code> if the matrix <var class="Arg">mat1</var> equals the matrix <var class="Arg">mat2</var> (i.e. the entries are equal and the underlying semirings are equal) and returns <code class="keyw">false</code> if it does not.</p>

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

<h4>5.3 <span class="Heading">
      Boolean matrices
    </span></h4>

<p>In this section we describe the operations, properties, and attributes in <strong class="pkg">Semigroups</strong> specifically for Boolean matrices. These include:</p>


<ul>
<li><p><code class="func">NumberBooleanMat</code> (<a href="chap5_mj.html#X7E0FD5878106AB66"><span class="RefLink">5.3-6</span></a>)</p>

</li>
<li><p><code class="func">Successors</code> (<a href="chap5_mj.html#X85E2FD8B82652876"><span class="RefLink">5.3-5</span></a>)</p>

</li>
<li><p><code class="func">IsRowTrimBooleanMat</code> (<a href="chap5_mj.html#X794C91597CC9F784"><span class="RefLink">5.3-9</span></a>), <code class="func">IsColTrimBooleanMat</code> (<a href="chap5_mj.html#X794C91597CC9F784"><span class="RefLink">5.3-9</span></a>), and <code class="func">IsTrimBooleanMat</code> (<a href="chap5_mj.html#X794C91597CC9F784"><span class="RefLink">5.3-9</span></a>),</p>

</li>
<li><p><code class="func">CanonicalBooleanMat</code> (<a href="chap5_mj.html#X7EEA5011862E6298"><span class="RefLink">5.3-8</span></a>)</p>

</li>
<li><p><code class="func">IsSymmetricBooleanMat</code> (<a href="chap5_mj.html#X7D22BA78790EFBC6"><span class="RefLink">5.3-10</span></a>)</p>

</li>
<li><p><code class="func">IsAntiSymmetricBooleanMat</code> (<a href="chap5_mj.html#X8570C8A08549383D"><span class="RefLink">5.3-13</span></a>)</p>

</li>
<li><p><code class="func">IsTransitiveBooleanMat</code> (<a href="chap5_mj.html#X7CDAD39B856AC3E5"><span class="RefLink">5.3-12</span></a>)</p>

</li>
<li><p><code class="func">IsReflexiveBooleanMat</code> (<a href="chap5_mj.html#X7C373B7D87044050"><span class="RefLink">5.3-11</span></a>)</p>

</li>
<li><p><code class="func">IsTotalBooleanMat</code> (<a href="chap5_mj.html#X7A68D87982A07C6F"><span class="RefLink">5.3-14</span></a>)</p>

</li>
<li><p><code class="func">IsOntoBooleanMat</code> (<a href="chap5_mj.html#X7A68D87982A07C6F"><span class="RefLink">5.3-14</span></a>)</p>

</li>
<li><p><code class="func">IsPartialOrderBooleanMat</code> (<a href="chap5_mj.html#X7D9BECEA7E9B72A7"><span class="RefLink">5.3-15</span></a>)</p>

</li>
<li><p><code class="func">IsEquivalenceBooleanMat</code> (<a href="chap5_mj.html#X82EA957982B79827"><span class="RefLink">5.3-16</span></a>)</p>

</li>
</ul>
<p><a id="X84A16D4D7D015885" name="X84A16D4D7D015885"></a></p>

<h5>5.3-1 BooleanMat</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; BooleanMat</code>( <var class="Arg">arg</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: A boolean matrix.</p>

<p><code class="code">BooleanMat</code> returns the boolean matrix <code class="code">mat</code> defined by its argument. The argument can be any of the following:</p>


<dl>
<dt><strong class="Mark">a matrix with entries <code class="code">0</code> and/or <code class="code">1</code></strong></dt>
<dd><p>the argument <var class="Arg">arg</var> is list of <code class="code">n</code> lists of length <code class="code">n</code> consisting of the values <code class="code">0</code> and <code class="code">1</code>;</p>

</dd>
<dt><strong class="Mark">a matrix with entries <code class="keyw">true</code> and/or <code class="keyw">false</code></strong></dt>
<dd><p>the argument <var class="Arg">arg</var> is list of <code class="code">n</code> lists of length <code class="code">n</code> consisting of the values <code class="keyw">true</code> and <code class="keyw">false</code>;</p>

</dd>
<dt><strong class="Mark">successors</strong></dt>
<dd><p>the argument <var class="Arg">arg</var> is list of <code class="code">n</code> sublists of consisting of positive integers not greater than <code class="code">n</code>. In this case, the entry <code class="code">j</code> in the sublist in position <code class="code">i</code> of <var class="Arg">arg</var> indicates that the entry in position <code class="code">(i, j)</code> of the created boolean matrix is <code class="keyw">true</code>.</p>

</dd>
</dl>
<p><code class="code">BooleanMat</code> returns an error if the argument is not one of the above types.</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">x := BooleanMat([[true, false], [true, true]]);</span>
Matrix(IsBooleanMat, [[1, 0], [1, 1]])
<span class="GAPprompt">gap></span> <span class="GAPinput">y := BooleanMat([[1, 0], [1, 1]]);</span>
Matrix(IsBooleanMat, [[1, 0], [1, 1]])
<span class="GAPprompt">gap></span> <span class="GAPinput">z := BooleanMat([[1], [1, 2]]);</span>
Matrix(IsBooleanMat, [[1, 0], [1, 1]])
<span class="GAPprompt">gap></span> <span class="GAPinput">x = y;</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">y = z;</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">Display(x);</span>
1 0
1 1</pre></div>

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

<h5>5.3-2 AsBooleanMat</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; AsBooleanMat</code>( <var class="Arg">x</var>[, <var class="Arg">n</var>] )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Returns: A boolean matrix.</p>

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

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


<dl>
<dt><strong class="Mark">permutations</strong></dt>
<dd><p>If <var class="Arg">x</var> is a permutation and <var class="Arg">n</var> is a positive integer, then <code class="code">AsBooleanMat(<var class="Arg">x</var>, <var class="Arg">n</var>)</code> returns the boolean matrix <code class="code">mat</code> of dimension <var class="Arg">n</var> such that <code class="code">mat[i][j] = true</code> if and only if <code class="code">j = i ^ x</code>.</p>

<p>If no positive integer <var class="Arg">n</var> is specified, then the largest moved point of <var class="Arg">x</var> is used as the value for <var class="Arg">n</var>; see <code class="func">LargestMovedPoint</code> (<a href="../../../doc/ref/chap42_mj.html#X84AA603987C94AC0"><span class="RefLink">Reference: LargestMovedPoint for a permutation</span></a>).</p>

</dd>
<dt><strong class="Mark">transformations</strong></dt>
<dd><p>If <var class="Arg">x</var> is a transformation and <var class="Arg">n</var> is a positive integer such that <var class="Arg">x</var> is a transformation of <code class="code">[1 .. <var class="Arg">n</var>]</code>, then <code class="code">AsTransformation</code> returns the boolean matrix <code class="code">mat</code> of dimension <var class="Arg">n</var> such that <code class="code">mat[i][j] = true</code> if and only if <code class="code">j = i ^ x</code>.</p>

<p>If the positive integer <var class="Arg">n</var> is not specified, then the degree of <var class="Arg">f</var> is used as the value for <var class="Arg">n</var>.</p>

</dd>
<dt><strong class="Mark">partial permutations</strong></dt>
<dd><p>If <var class="Arg">x</var> is a partial permutation and <var class="Arg">n</var> is a positive integer such that <code class="code">i ^ <var class="Arg">x</var> <= n</code> for all <code class="code">i</code> in <code class="code">[1 .. <var class="Arg">n</var>]</code>, then <code class="code">AsBooleanMat</code> returns the boolean matrix <code class="code">mat</code> of dimension <var class="Arg">n</var> such that <code class="code">mat[i][j] = true</code> if and only if <code class="code">j = i ^ x</code>.</p>

<p>If the optional argument <var class="Arg">n</var> is not present, then the default value of the maximum of degree and the codegree of <var class="Arg">x</var> is used.</p>

</dd>
<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 any non-negative integer, then <code class="code">AsBooleanMat</code> returns the boolean matrix <code class="code">mat</code> of dimension <var class="Arg">n</var> such that <code class="code">mat[i][j] = true</code> if and only if <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 argument <var class="Arg">n</var> is not present, then twice the degree of <var class="Arg">x</var> is used by default.</p>

</dd>
<dt><strong class="Mark">pbrs</strong></dt>
<dd><p>If <var class="Arg">x</var> is a pbr and <var class="Arg">n</var> is any non-negative integer, then <code class="code">AsBooleanMat</code> returns the boolean matrix <code class="code">mat</code> of dimension <var class="Arg">n</var> such that <code class="code">mat[i][j] = true</code> if and only if <code class="code">i</code> and <code class="code">j</code> are related in <var class="Arg">x</var>.</p>

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

</dd>
</dl>

<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">Display(AsBooleanMat((1, 2), 5));</span>
0 1 0 0 0
1 0 0 0 0
0 0 1 0 0
0 0 0 1 0
0 0 0 0 1
<span class="GAPprompt">gap></span> <span class="GAPinput">Display(AsBooleanMat((1, 2)));</span>
0 1
1 0
<span class="GAPprompt">gap></span> <span class="GAPinput">x := Transformation([1, 3, 4, 1, 3]);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">Display(AsBooleanMat(x));</span>
1 0 0 0 0
0 0 1 0 0
0 0 0 1 0
1 0 0 0 0
0 0 1 0 0
<span class="GAPprompt">gap></span> <span class="GAPinput">Display(AsBooleanMat(x, 4));</span>
1 0 0 0
0 0 1 0
0 0 0 1
1 0 0 0
<span class="GAPprompt">gap></span> <span class="GAPinput">x := PartialPerm([1, 2, 3, 6, 8, 10],</span>
<span class="GAPprompt">></span> <span class="GAPinput">                    [2, 6, 7, 9, 1, 5]);</span>
[3,7][8,1,2,6,9][10,5]
<span class="GAPprompt">gap></span> <span class="GAPinput">Display(AsBooleanMat(x));</span>
0 1 0 0 0 0 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 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 1 0 0 0 0 0
<span class="GAPprompt">gap></span> <span class="GAPinput">x := Bipartition([[1, 4, -2, -3], [2, 3, 5, -5], [-1, -4]]);</span>
<bipartition: [ 1, 4, -2, -3 ], [ 2, 3, 5, -5 ], [ -1, -4 ]>
<span class="GAPprompt">gap></span> <span class="GAPinput">y := AsBooleanMat(x);</span>
<10x10 boolean matrix>
<span class="GAPprompt">gap></span> <span class="GAPinput">Display(y);</span>
1 0 0 1 0 0 1 1 0 0
0 1 1 0 1 0 0 0 0 1
0 1 1 0 1 0 0 0 0 1
1 0 0 1 0 0 1 1 0 0
0 1 1 0 1 0 0 0 0 1
0 0 0 0 0 1 0 0 1 0
1 0 0 1 0 0 1 1 0 0
1 0 0 1 0 0 1 1 0 0
0 0 0 0 0 1 0 0 1 0
0 1 1 0 1 0 0 0 0 1
<span class="GAPprompt">gap></span> <span class="GAPinput">IsEquivalenceBooleanMat(y);</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">AsBooleanMat(x, 1);</span>
Matrix(IsBooleanMat, [[1]])
<span class="GAPprompt">gap></span> <span class="GAPinput">Display(AsBooleanMat(x, 1));</span>
1
<span class="GAPprompt">gap></span> <span class="GAPinput">Display(AsBooleanMat(x, 2));</span>
1 0
0 1
<span class="GAPprompt">gap></span> <span class="GAPinput">Display(AsBooleanMat(x, 3));</span>
1 0 0
0 1 1
0 1 1
<span class="GAPprompt">gap></span> <span class="GAPinput">Display(AsBooleanMat(x, 11));</span>
1 0 0 1 0 0 1 1 0 0 0
0 1 1 0 1 0 0 0 0 1 0
0 1 1 0 1 0 0 0 0 1 0
1 0 0 1 0 0 1 1 0 0 0
0 1 1 0 1 0 0 0 0 1 0
0 0 0 0 0 1 0 0 1 0 0
1 0 0 1 0 0 1 1 0 0 0
1 0 0 1 0 0 1 1 0 0 0
0 0 0 0 0 1 0 0 1 0 0
0 1 1 0 1 0 0 0 0 1 0
0 0 0 0 0 0 0 0 0 0 0
<span class="GAPprompt">gap></span> <span class="GAPinput">x := PBR(</span>
<span class="GAPprompt">></span> <span class="GAPinput">[[-1, 1], [2, 3], [-3, 2, 3]],</span>
<span class="GAPprompt">></span> <span class="GAPinput">[[-1, 1, 2], [-3, -1, 1, 3], [-3, -1, 1, 2, 3]]);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">AsBooleanMat(x);</span>
Matrix(IsBooleanMat, [[1, 0, 0, 1, 0, 0], [0, 1, 1, 0, 0, 0],
  [0, 1, 1, 0, 0, 1], [1, 1, 0, 1, 0, 0], [1, 0, 1, 1, 0, 1],
  [1, 1, 1, 1, 0, 1]])
<span class="GAPprompt">gap></span> <span class="GAPinput">Display(AsBooleanMat(x));</span>
1 0 0 1 0 0
0 1 1 0 0 0
0 1 1 0 0 1
1 1 0 1 0 0
1 0 1 1 0 1
1 1 1 1 0 1</pre></div>

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

<h5><code>5.3-3 \in</code></h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; \in</code>( <var class="Arg">mat1</var>, <var class="Arg">mat2</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Returns: <code class="keyw">true</code> or <code class="keyw">false</code>.</p>

<p>If <var class="Arg">mat1</var> and <var class="Arg">mat2</var> are boolean matrices, then <code class="code"><var class="Arg">mat1</var> in <var class="Arg">mat2</var></code> returns <code class="keyw">true</code> if the binary relation defined by <var class="Arg">mat1</var> is a subset of that defined by <var class="Arg">mat2</var>.</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">x := BooleanMat([[1, 0, 0, 1], [0, 0, 0, 0],</span>
<span class="GAPprompt">></span> <span class="GAPinput">                    [1, 0, 1, 1], [0, 1, 1, 1]]);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">y := BooleanMat([[1, 0, 1, 0], [1, 1, 1, 0],</span>
<span class="GAPprompt">></span> <span class="GAPinput">                    [0, 1, 1, 0], [1, 1, 1, 1]]);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">x in y;</span>
false
<span class="GAPprompt">gap></span> <span class="GAPinput">y in y;</span>
true</pre></div>

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

<h5>5.3-4 OnBlist</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; OnBlist</code>( <var class="Arg">blist</var>, <var class="Arg">mat</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: A boolean list.</p>

<p>If <var class="Arg">blist</var> is a boolean list of length <code class="code">n</code> and <var class="Arg">mat</var> is boolean matrices of dimension <code class="code">n</code>, then <code class="code">OnBlist</code> returns the product of <var class="Arg">blist</var> (thought of as a row vector over the boolean semiring) and <var class="Arg">mat</var>.</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">mat := BooleanMat([[1, 0, 0, 1],</span>
<span class="GAPprompt">></span> <span class="GAPinput">                      [0, 0, 0, 0],</span>
<span class="GAPprompt">></span> <span class="GAPinput">                      [1, 0, 1, 1],</span>
<span class="GAPprompt">></span> <span class="GAPinput">                      [0, 1, 1, 1]]);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">blist := BlistList([1 .. 4], [1, 2]);</span>
[ true, true, false, false ]
<span class="GAPprompt">gap></span> <span class="GAPinput">OnBlist(blist, mat);</span>
[ true, false, false, true ]</pre></div>

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

<h5>5.3-5 Successors</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; Successors</code>( <var class="Arg">mat</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>Returns: A list of lists of positive integers.</p>

<p>A row of a boolean matrix of dimension <code class="code">n</code> can be thought of of as the characteristic function of a subset <code class="code">S</code> of <code class="code">[1 .. n]</code>, i.e. <code class="code">i in S</code> if and only if the <code class="code">i</code>th component of the row equals <span class="SimpleMath">\(1\)</span>. We refer to the subset <code class="code">S</code> as the <strong class="button">successors</strong> of the row.</p>

<p>If <var class="Arg">mat</var> is a boolean matrix, then <code class="code">Successors</code> returns the list of successors of the rows of <var class="Arg">mat</var>.</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">mat := BooleanMat([[1, 0, 1, 1],</span>
<span class="GAPprompt">></span> <span class="GAPinput">                      [1, 0, 0, 0],</span>
<span class="GAPprompt">></span> <span class="GAPinput">                      [0, 0, 1, 0],</span>
<span class="GAPprompt">></span> <span class="GAPinput">                      [1, 1, 0, 0]]);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">Successors(mat);</span>
[ [ 1, 3, 4 ], [ 1 ], [ 3 ], [ 1, 2 ] ]</pre></div>

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

<h5>5.3-6 BooleanMatNumber</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; BooleanMatNumber</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">&#an style='color: green'>8227; NumberBooleanMat</code>( <var class="Arg">mat</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Returns: A boolean matrix, or a positive integer.</p>

<p>These functions implement a bijection from the set of all boolean matrices of dimension <var class="Arg">n</var> and the numbers <code class="code">[1 .. 2 ^ (<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 ^ (<var class="Arg">n</var> ^ 2)</code>, then <code class="code">BooleanMatNumber</code> returns the <var class="Arg">m</var>th <var class="Arg">n</var> by <var class="Arg">n</var> boolean matrix.</p>

<p>If <var class="Arg">mat</var> is an <var class="Arg">n</var> by <var class="Arg">n</var> boolean matrix, then <code class="code">NumberBooleanMat</code> returns the number in <code class="code">[1 .. 2 ^ (<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">mat := BooleanMat([[0, 1, 1, 0],</span>
<span class="GAPprompt">></span> <span class="GAPinput">                      [1, 0, 1, 1],</span>
<span class="GAPprompt">></span> <span class="GAPinput">                      [1, 1, 0, 1],</span>
<span class="GAPprompt">></span> <span class="GAPinput">                      [0, 1, 0, 1]]);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">NumberBooleanMat(mat);</span>
27606
<span class="GAPprompt">gap></span> <span class="GAPinput">Display(BooleanMatNumber(27606, 4));</span>
0 1 1 0
1 0 1 1
1 1 0 1
0 1 0 1</pre></div>

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

<h5>5.3-7 BlistNumber</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; BlistNumber</code>( <var class="Arg">m</var>, <var class="Arg">n</var> )</td><td class="tdright">( function )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; NumberBlist</code>( <var class="Arg">blist</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: A boolean list, or a positive integer.</p>

<p>These functions implement a bijection from the set of all boolean lists of length <var class="Arg">n</var> and the numbers <code class="code">[1 .. 2 ^ <var class="Arg">n</var>]</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 ^ <var class="Arg">n</var></code>, then <code class="code">BlistNumber</code> returns the <var class="Arg">m</var>th boolean list of length <var class="Arg">n</var>.</p>

<p>If <var class="Arg">blist</var> is a boolean list of length <var class="Arg">n</var>, then <code class="code">NumberBlist</code> returns the number in <code class="code">[1 .. 2 ^ <var class="Arg">n</var>]</code> that corresponds to <var class="Arg">blist</var>.</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">blist := BlistList([1 .. 10], []);</span>
[ false, false, false, false, false, false, false, false, false,
  false ]
<span class="GAPprompt">gap></span> <span class="GAPinput">NumberBlist(blist);</span>
1
<span class="GAPprompt">gap></span> <span class="GAPinput">blist := BlistList([1 .. 10], [10]);</span>
[ false, false, false, false, false, false, false, false, false, true
 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">NumberBlist(blist);</span>
2
<span class="GAPprompt">gap></span> <span class="GAPinput">BlistNumber(1, 10);</span>
[ false, false, false, false, false, false, false, false, false,
  false ]
<span class="GAPprompt">gap></span> <span class="GAPinput">BlistNumber(2, 10);</span>
[ false, false, false, false, false, false, false, false, false, true
 ]</pre></div>

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

<h5>5.3-8 CanonicalBooleanMat</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; CanonicalBooleanMat</code>( <var class="Arg">G</var>, <var class="Arg">H</var>, <var class="Arg">mat</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; CanonicalBooleanMat</code>( <var class="Arg">G</var>, <var class="Arg">mat</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; CanonicalBooleanMat</code>( <var class="Arg">mat</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>Returns: A boolean matrix.</p>

<p>This operation returns a fixed representative of the orbit of the boolean matrix <var class="Arg">mat</var> under the action of the permutation group <var class="Arg">G</var> on its rows and the permutation group <var class="Arg">H</var> on its columns.</p>

<p>In its second form, when only a single permutation group <var class="Arg">G</var> is specified, <var class="Arg">G</var> acts on the rows and columns of <var class="Arg">mat</var> independently.</p>

<p>In its third form, when only a boolean matrix is specified, <code class="code">CanonicalBooleanMat</code> returns a fixed representative of the orbit of <var class="Arg">mat</var> under the action of the symmetric group on its rows, and, independently, on its columns. In other words, <code class="code">CanonicalBooleanMat</code> returns a canonical boolean matrix equivalent to <var class="Arg">mat</var> up to rearranging rows and columns. This version of <code class="code">CanonicalBooleanMat</code> uses <strong class="pkg">digraphs</strong> and its interface with the <span class="URL"><a href="http://www.tcs.tkk.fi/Software/bliss/">bliss</a></span> library for computing automorphism groups and canonical forms of graphs <a href="chapBib_mj.html#biBJunttilaKaski">[JK07]</a>. As a consequence, <code class="code">CanonicalBooleanMat</code> with a single argument is significantly faster than the versions with 2 or 3 arguments.</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">mat := BooleanMat([[1, 1, 1, 0, 0, 0],</span>
<span class="GAPprompt">></span> <span class="GAPinput">                      [0, 0, 0, 1, 0, 1],</span>
<span class="GAPprompt">></span> <span class="GAPinput">                      [1, 0, 0, 1, 0, 1],</span>
<span class="GAPprompt">></span> <span class="GAPinput">                      [0, 0, 0, 0, 0, 0],</span>
<span class="GAPprompt">></span> <span class="GAPinput">                      [0, 1, 1, 1, 1, 1],</span>
<span class="GAPprompt">></span> <span class="GAPinput">                      [0, 1, 1, 0, 1, 0]]);</span>
Matrix(IsBooleanMat, [[1, 1, 1, 0, 0, 0], [0, 0, 0, 1, 0, 1],
  [1, 0, 0, 1, 0, 1], [0, 0, 0, 0, 0, 0], [0, 1, 1, 1, 1, 1],
  [0, 1, 1, 0, 1, 0]])
<span class="GAPprompt">gap></span> <span class="GAPinput">CanonicalBooleanMat(mat);</span>
Matrix(IsBooleanMat, [[0, 0, 0, 0, 0, 0], [1, 1, 0, 0, 0, 0],
  [0, 0, 1, 1, 1, 0], [1, 1, 0, 0, 1, 0], [0, 0, 1, 1, 0, 1],
  [1, 1, 1, 1, 0, 1]])
<span class="GAPprompt">gap></span> <span class="GAPinput">Display(CanonicalBooleanMat(mat));</span>
0 0 0 0 0 0
1 1 0 0 0 0
0 0 1 1 1 0
1 1 0 0 1 0
0 0 1 1 0 1
1 1 1 1 0 1
<span class="GAPprompt">gap></span> <span class="GAPinput">Display(CanonicalBooleanMat(Group((1, 3)), mat));</span>
0 1 1 0 0 1
0 0 1 0 0 1
1 1 0 1 0 0
0 0 0 0 0 0
1 0 1 1 1 1
1 0 0 1 1 0
<span class="GAPprompt">gap></span> <span class="GAPinput">Display(CanonicalBooleanMat(Group((1, 3)), Group(()), mat));</span>
1 1 1 0 0 0
0 0 0 1 0 1
0 1 0 1 0 1
0 0 0 0 0 0
1 0 1 1 1 1
1 0 1 0 1 0</pre></div>

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

<h5>5.3-9 IsRowTrimBooleanMat</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; IsRowTrimBooleanMat</code>( <var class="Arg">mat</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">&#an style='color: green'>8227; IsColTrimBooleanMat</code>( <var class="Arg">mat</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">&#an style='color: green'>8227; IsTrimBooleanMat</code>( <var class="Arg">mat</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 row or column of a boolean matrix of dimension <code class="code">n</code> can be thought of of as the characteristic function of a subset <code class="code">S</code> of <code class="code">[1 .. n]</code>, i.e. <code class="code">i in S</code> if and only if the <code class="code">i</code>th component of the row or column equals <code class="code">1</code>.</p>

<p>A boolean matrix is <strong class="button">row trim</strong> if no subset induced by a row of <var class="Arg">mat</var> is contained in the subset induced by any other row of <var class="Arg">mat</var>. <strong class="button">Column trim</strong> is defined analogously. A boolean matrix is <strong class="button">trim</strong> if it is both row and column trim.</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">mat := BooleanMat([[0, 0, 1, 1],</span>
<span class="GAPprompt">></span> <span class="GAPinput">                      [1, 0, 1, 0],</span>
<span class="GAPprompt">></span> <span class="GAPinput">                      [1, 1, 0, 0],</span>
<span class="GAPprompt">></span> <span class="GAPinput">                      [0, 1, 0, 1]]);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">IsTrimBooleanMat(mat);</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">mat := BooleanMat([[0, 1, 1, 0],</span>
<span class="GAPprompt">></span> <span class="GAPinput">                      [0, 0, 1, 0],</span>
<span class="GAPprompt">></span> <span class="GAPinput">                      [1, 0, 0, 1],</span>
<span class="GAPprompt">></span> <span class="GAPinput">                      [1, 0, 1, 0]]);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">IsRowTrimBooleanMat(mat);</span>
false
<span class="GAPprompt">gap></span> <span class="GAPinput">IsColTrimBooleanMat(mat);</span>
false</pre></div>

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

<h5>5.3-10 IsSymmetricBooleanMat</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; IsSymmetricBooleanMat</code>( <var class="Arg">mat</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 boolean matrix is <strong class="button">symmetric</strong> if it is symmetric about the main diagonal, i.e. <code class="code"><var class="Arg">mat</var>[i][j] = <var class="Arg">mat</var>[j][i]</code> for all <code class="code">i, j</code> in the range <code class="code">[1 .. n]</code> where <code class="code">n</code> is the dimension of <var class="Arg">mat</var>.</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">mat := BooleanMat([[0, 1, 1, 0],</span>
<span class="GAPprompt">></span> <span class="GAPinput">                      [1, 0, 1, 1],</span>
<span class="GAPprompt">></span> <span class="GAPinput">                      [1, 1, 0, 1],</span>
<span class="GAPprompt">></span> <span class="GAPinput">                      [0, 1, 0, 1]]);</span>
Matrix(IsBooleanMat, [[0, 1, 1, 0], [1, 0, 1, 1], [1, 1, 0, 1],
  [0, 1, 0, 1]])
<span class="GAPprompt">gap></span> <span class="GAPinput">IsSymmetricBooleanMat(mat);</span>
false
<span class="GAPprompt">gap></span> <span class="GAPinput">mat := BooleanMat([[0, 1, 1, 0],</span>
<span class="GAPprompt">></span> <span class="GAPinput">                      [1, 0, 1, 1],</span>
<span class="GAPprompt">></span> <span class="GAPinput">                      [1, 1, 0, 1],</span>
<span class="GAPprompt">></span> <span class="GAPinput">                      [0, 1, 1, 1]]);</span>
Matrix(IsBooleanMat, [[0, 1, 1, 0], [1, 0, 1, 1], [1, 1, 0, 1],
  [0, 1, 1, 1]])
<span class="GAPprompt">gap></span> <span class="GAPinput">IsSymmetricBooleanMat(mat);</span>
true</pre></div>

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

<h5>5.3-11 IsReflexiveBooleanMat</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; IsReflexiveBooleanMat</code>( <var class="Arg">mat</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 boolean matrix is <strong class="button">reflexive</strong> if every entry in the main diagonal is <code class="keyw">true</code>, i.e. <code class="code"><var class="Arg">mat</var>[i][i] = true</code> for all <code class="code">i</code> in the range <code class="code">[1 .. n]</code> where <code class="code">n</code> is the dimension of <var class="Arg">mat</var>.</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">mat := BooleanMat([[1, 0, 0, 0],</span>
<span class="GAPprompt">></span> <span class="GAPinput">                      [1, 1, 0, 0],</span>
<span class="GAPprompt">></span> <span class="GAPinput">                      [0, 1, 0, 1],</span>
<span class="GAPprompt">></span> <span class="GAPinput">                      [1, 1, 1, 1]]);</span>
Matrix(IsBooleanMat, [[1, 0, 0, 0], [1, 1, 0, 0], [0, 1, 0, 1],
  [1, 1, 1, 1]])
<span class="GAPprompt">gap></span> <span class="GAPinput">IsReflexiveBooleanMat(mat);</span>
false
<span class="GAPprompt">gap></span> <span class="GAPinput">mat := BooleanMat([[1, 1, 1, 0],</span>
<span class="GAPprompt">></span> <span class="GAPinput">                      [1, 1, 1, 1],</span>
<span class="GAPprompt">></span> <span class="GAPinput">                      [1, 1, 1, 1],</span>
<span class="GAPprompt">></span> <span class="GAPinput">                      [0, 1, 1, 1]]);</span>
Matrix(IsBooleanMat, [[1, 1, 1, 0], [1, 1, 1, 1], [1, 1, 1, 1],
  [0, 1, 1, 1]])
<span class="GAPprompt">gap></span> <span class="GAPinput">IsReflexiveBooleanMat(mat);</span>
true</pre></div>

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

<h5>5.3-12 IsTransitiveBooleanMat</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; IsTransitiveBooleanMat</code>( <var class="Arg">mat</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 boolean matrix is <strong class="button">transitive</strong> if whenever <code class="code"><var class="Arg">mat</var>[i][j] = true</code> and <code class="code"><var class="Arg">mat</var>[j][k] = true</code> then <code class="code"><var class="Arg">mat</var>[i][k] = true</code>.</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">x := BooleanMat([[1, 0, 0, 1],</span>
<span class="GAPprompt">></span> <span class="GAPinput">                    [1, 0, 1, 1],</span>
<span class="GAPprompt">></span> <span class="GAPinput">                    [1, 1, 1, 0],</span>
<span class="GAPprompt">></span> <span class="GAPinput">                    [0, 1, 1, 0]]);</span>
Matrix(IsBooleanMat, [[1, 0, 0, 1], [1, 0, 1, 1], [1, 1, 1, 0],
  [0, 1, 1, 0]])
<span class="GAPprompt">gap></span> <span class="GAPinput">IsTransitiveBooleanMat(x);</span>
false
<span class="GAPprompt">gap></span> <span class="GAPinput">x := BooleanMat([[1, 1, 1, 1],</span>
<span class="GAPprompt">></span> <span class="GAPinput">                    [1, 1, 1, 1],</span>
<span class="GAPprompt">></span> <span class="GAPinput">                    [1, 1, 1, 1],</span>
<span class="GAPprompt">></span> <span class="GAPinput">                    [1, 1, 1, 1]]);</span>
Matrix(IsBooleanMat, [[1, 1, 1, 1], [1, 1, 1, 1], [1, 1, 1, 1],
  [1, 1, 1, 1]])
<span class="GAPprompt">gap></span> <span class="GAPinput">IsTransitiveBooleanMat(x);</span>
true</pre></div>

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

<h5>5.3-13 IsAntiSymmetricBooleanMat</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; IsAntiSymmetricBooleanMat</code>( <var class="Arg">mat</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 boolean matrix is <strong class="button">anti-symmetric</strong> if whenever <code class="code"><var class="Arg">mat</var>[i][j] = true</code> and <code class="code"><var class="Arg">mat</var>[j][i] = true</code> then <code class="code">i = j</code>.</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">x := BooleanMat([[1, 0, 0, 1],</span>
<span class="GAPprompt">></span> <span class="GAPinput">                    [1, 0, 1, 1],</span>
<span class="GAPprompt">></span> <span class="GAPinput">                    [1, 1, 1, 0],</span>
<span class="GAPprompt">></span> <span class="GAPinput">                    [0, 1, 1, 0]]);</span>
Matrix(IsBooleanMat, [[1, 0, 0, 1], [1, 0, 1, 1], [1, 1, 1, 0],
  [0, 1, 1, 0]])
<span class="GAPprompt">gap></span> <span class="GAPinput">IsAntiSymmetricBooleanMat(x);</span>
false
<span class="GAPprompt">gap></span> <span class="GAPinput">x := BooleanMat([[1, 0, 0, 1],</span>
<span class="GAPprompt">></span> <span class="GAPinput">                    [1, 0, 1, 0],</span>
<span class="GAPprompt">></span> <span class="GAPinput">                    [1, 0, 1, 0],</span>
<span class="GAPprompt">></span> <span class="GAPinput">                    [0, 1, 1, 0]]);</span>
Matrix(IsBooleanMat, [[1, 0, 0, 1], [1, 0, 1, 0], [1, 0, 1, 0],
  [0, 1, 1, 0]])
<span class="GAPprompt">gap></span> <span class="GAPinput">IsAntiSymmetricBooleanMat(x);</span>
true</pre></div>

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

<h5>5.3-14 IsTotalBooleanMat</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; IsTotalBooleanMat</code>( <var class="Arg">mat</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">&#an style='color: green'>8227; IsOntoBooleanMat</code>( <var class="Arg">mat</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 boolean matrix is <strong class="button">total</strong> if there is at least one entry in every row is <code class="keyw">true</code>. Similarly, a boolean matrix is <strong class="button">onto</strong> if at least one entry in every column is <code class="keyw">true</code>.</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">x := BooleanMat([[1, 0, 0, 1],</span>
<span class="GAPprompt">></span> <span class="GAPinput">                    [1, 0, 1, 1],</span>
<span class="GAPprompt">></span> <span class="GAPinput">                    [1, 1, 1, 0],</span>
<span class="GAPprompt">></span> <span class="GAPinput">                    [0, 1, 1, 0]]);</span>
Matrix(IsBooleanMat, [[1, 0, 0, 1], [1, 0, 1, 1], [1, 1, 1, 0],
  [0, 1, 1, 0]])
<span class="GAPprompt">gap></span> <span class="GAPinput">IsTotalBooleanMat(x);</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">IsOntoBooleanMat(x);</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">x := BooleanMat([[1, 0, 0, 1],</span>
<span class="GAPprompt">></span> <span class="GAPinput">                    [1, 0, 1, 0],</span>
<span class="GAPprompt">></span> <span class="GAPinput">                    [0, 0, 0, 0],</span>
<span class="GAPprompt">></span> <span class="GAPinput">                    [0, 1, 1, 0]]);</span>
Matrix(IsBooleanMat, [[1, 0, 0, 1], [1, 0, 1, 0], [0, 0, 0, 0],
  [0, 1, 1, 0]])
<span class="GAPprompt">gap></span> <span class="GAPinput">IsTotalBooleanMat(x);</span>
false
<span class="GAPprompt">gap></span> <span class="GAPinput">IsOntoBooleanMat(x);</span>
true</pre></div>

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

<h5>5.3-15 IsPartialOrderBooleanMat</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; IsPartialOrderBooleanMat</code>( <var class="Arg">mat</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 boolean matrix is a <strong class="button">partial order</strong> if it is reflexive, transitive, and anti-symmetric.</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">Number(FullBooleanMatMonoid(3), IsPartialOrderBooleanMat);</span>
19</pre></div>

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

<h5>5.3-16 IsEquivalenceBooleanMat</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; IsEquivalenceBooleanMat</code>( <var class="Arg">mat</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 boolean matrix is an <strong class="button">equivalence</strong> if it is reflexive, transitive, and symmetric.</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">Number(FullBooleanMatMonoid(3), IsEquivalenceBooleanMat);</span>
5
<span class="GAPprompt">gap></span> <span class="GAPinput">Bell(3);</span>
5</pre></div>

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

<h5>5.3-17 IsTransformationBooleanMat</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; IsTransformationBooleanMat</code>( <var class="Arg">mat</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 boolean matrix is a <strong class="button">transformation</strong> if every row contains precisely one <code class="keyw">true</code> value.</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">Number(FullBooleanMatMonoid(3), IsTransformationBooleanMat);</span>
27</pre></div>

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

<h4>5.4 <span class="Heading">
      Matrices over finite fields
    </span></h4>

<p>In this section we describe some operations in <strong class="pkg">Semigroups</strong> for matrices over finite fields that are required for such matrices to form semigroups satisfying <code class="func">IsActingSemigroup</code> (<a href="chap6_mj.html#X7F69D8FC7D578A0C"><span class="RefLink">6.1-2</span></a>).</p>

<p>From v5.0.0, <strong class="pkg">Semigroups</strong> uses the <strong class="pkg">GAP</strong> library implementation of matrices over finite fields belonging to the category <code class="func">IsMatrixObj</code> (<a href="../../../doc/ref/chap26_mj.html#X7E7617A0781D1E4B"><span class="RefLink">Reference: IsMatrixObj</span></a>) rather than the previous implementation in the <strong class="pkg">Semigroups</strong> package. This means that from v5.0.0, matrices over a finite field no longer belong to the category <code class="func">IsMatrixOverSemiring</code> (<a href="chap5_mj.html#X8711618C7A8A1B60"><span class="RefLink">5.1-1</span></a>).</p>

<p>The following methods are implemented in <strong class="pkg">Semigroups</strong> for matrix objects over finite fields.</p>

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

<h5>5.4-1 RowSpaceBasis</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; RowSpaceBasis</code>( <var class="Arg">m</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; RowSpaceTransformation</code>( <var class="Arg">m</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; RowSpaceTransformationInv</code>( <var class="Arg">m</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>If <var class="Arg">m</var> is a matrix object over a finite field, then to compute the value of any of the above attributes, a canonical basis for the row space of <var class="Arg">m</var> is computed along with an invertible matrix <code class="code">RowSpaceTransformation</code> such that <code class="code">m * RowSpaceTransformation(m) = RowSpaceBasis(m)</code>. <code class="code">RowSpaceTransformationInv(m)</code> is the inverse of <code class="code">RowSpaceTransformation(m)</code>.</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">x := Matrix(GF(4), Z(4) ^ 0 * [[1, 1, 0], [0, 1, 1], [1, 1, 1]]);</span>
[ [ Z(2)^0, Z(2)^0, 0*Z(2) ], [ 0*Z(2), Z(2)^0, Z(2)^0 ],
  [ Z(2)^0, Z(2)^0, Z(2)^0 ] ]
<span class="GAPprompt">gap></span> <span class="GAPinput">RowSpaceBasis(x);</span>
<rowbasis of rank 3 over GF(2^2)>
<span class="GAPprompt">gap></span> <span class="GAPinput">RowSpaceTransformation(x);</span>
[ [ 0*Z(2), Z(2)^0, Z(2)^0 ], [ Z(2)^0, Z(2)^0, Z(2)^0 ],
  [ Z(2)^0, 0*Z(2), Z(2)^0 ] ]</pre></div>

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

<h5>5.4-2 RightInverse</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; RightInverse</code>( <var class="Arg">m</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; LeftInverse</code>( <var class="Arg">m</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>Returns: A matrix over a finite field.</p>

<p>These attributes contain a semigroup left-inverse, and a semigroup right-inverse of the matrix <var class="Arg">m</var> respectively.</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">x := Matrix(GF(4), Z(4) ^ 0 * [[1, 1, 0], [0, 0, 0], [1, 1, 1]]);</span>
[ [ Z(2)^0, Z(2)^0, 0*Z(2) ], [ 0*Z(2), 0*Z(2), 0*Z(2) ],
  [ Z(2)^0, Z(2)^0, Z(2)^0 ] ]
<span class="GAPprompt">gap></span> <span class="GAPinput">LeftInverse(x);</span>
[ [ Z(2)^0, Z(2)^0, 0*Z(2) ], [ 0*Z(2), 0*Z(2), 0*Z(2) ],
  [ Z(2)^0, 0*Z(2), Z(2)^0 ] ]
<span class="GAPprompt">gap></span> <span class="GAPinput">Display(LeftInverse(x) * x);</span>
 1 1 .
 . . .
 . . 1
</pre></div>

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

<h4>5.5 <span class="Heading">
      Matrices over the integers
    </span></h4>

<p>In this section we describe operations in <strong class="pkg">Semigroups</strong> specifically for integer matrices.</p>

<p>From v5.0.0, <strong class="pkg">Semigroups</strong> uses the <strong class="pkg">GAP</strong> library implementation of matrices over the integers belonging to the category <code class="func">IsMatrixObj</code> (<a href="../../../doc/ref/chap26_mj.html#X7E7617A0781D1E4B"><span class="RefLink">Reference: IsMatrixObj</span></a>) rather than the previous implementation in the <strong class="pkg">Semigroups</strong> package. This means that from v5.0.0, matrices over the integers no longer belong to the category <code class="func">IsMatrixOverSemiring</code> (<a href="chap5_mj.html#X8711618C7A8A1B60"><span class="RefLink">5.1-1</span></a>).</p>

<p>The following methods are implemented in <strong class="pkg">Semigroups</strong> for matrix objects over the integers.</p>

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

<h5>5.5-1 InverseOp</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; InverseOp</code>( <var class="Arg">mat</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Returns: An integer matrix.</p>

<p>If <var class="Arg">mat</var> is an integer matrix (i.e. belongs to the category <code class="func">Integers</code> (<a href="chap5_mj.html#X782480C686F1A663"><span class="RefLink">5.1-8</span></a>)) whose inverse (if it exists) is also an integer matrix, then <code class="code">InverseOp</code> returns the inverse of <var class="Arg">mat</var>.</p>

<p>An integer matrix has an integer matrix inverse if and only if it has determinant one.</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">mat := Matrix(Integers, [[0, 0, -1],</span>
<span class="GAPprompt">></span> <span class="GAPinput">                            [0, 1, 0],</span>
<span class="GAPprompt">></span> <span class="GAPinput">                            [1, 0, 0]]);</span>
<3x3-matrix over Integers>
<span class="GAPprompt">gap></span> <span class="GAPinput">InverseOp(mat);</span>
<3x3-matrix over Integers>
<span class="GAPprompt">gap></span> <span class="GAPinput">mat * InverseOp(mat) = One(mat);</span>
true
</pre></div>

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

<h5>5.5-2 IsTorsion</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; IsTorsion</code>( <var class="Arg">mat</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>Returns: <code class="keyw">true</code> or <code class="keyw">false</code></p>

<p>If <var class="Arg">mat</var> is an integer matrix (i.e. belongs to the category <code class="func">Integers</code> (<a href="chap5_mj.html#X782480C686F1A663"><span class="RefLink">5.1-8</span></a>)), then <code class="code">IsTorsion</code> returns <code class="keyw">true</code> if <var class="Arg">mat</var> is torsion and <code class="keyw">false</code> otherwise.</p>

<p>An integer matrix <var class="Arg">mat</var> is torsion if and only if there exists an integer <code class="code">n</code> such that <var class="Arg">mat</var> to the power of <code class="code">n</code> is equal to the identity matrix.</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">mat := Matrix(Integers, [[0, 0, -1],</span>
<span class="GAPprompt">></span> <span class="GAPinput">                            [0, 1, 0],</span>
<span class="GAPprompt">></span> <span class="GAPinput">                            [1, 0, 0]]);</span>
<3x3-matrix over Integers>
<span class="GAPprompt">gap></span> <span class="GAPinput">IsTorsion(mat);</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">mat := Matrix(Integers, [[0, 0, -1, 0],</span>
<span class="GAPprompt">></span> <span class="GAPinput">                            [0, -1, 0, 0],</span>
<span class="GAPprompt">></span> <span class="GAPinput">                            [4, 4, 2, -1],</span>
<span class="GAPprompt">></span> <span class="GAPinput">                            [1, 1, 0, 3]]);</span>
<4x4-matrix over Integers>
<span class="GAPprompt">gap></span> <span class="GAPinput">IsTorsion(mat);</span>
false
</pre></div>

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

<h5>5.5-3 Order</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; Order</code>( <var class="Arg">mat</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>Returns: An integer or <code class="code">infinity</code>.</p>

<p>If <var class="Arg">mat</var> is an integer matrix, then <code class="code">InverseOp</code> returns the order of <var class="Arg">mat</var>. The order of <var class="Arg">mat</var> is the smallest integer power of <var class="Arg">mat</var> equal to the identity. If no such integer exists, the order is equal to <code class="code">infinity</code>.</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">mat := Matrix(Integers, [[0, 0, -1, 0],</span>
<span class="GAPprompt">></span> <span class="GAPinput">                            [0, -1, 0, 0],</span>
<span class="GAPprompt">></span> <span class="GAPinput">                            [4, 4, 2, -1],</span>
<span class="GAPprompt">></span> <span class="GAPinput">                            [1, 1, 0, 3]]);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">Order(mat);</span>
infinity
<span class="GAPprompt">gap></span> <span class="GAPinput">mat := Matrix(Integers, [[0, 0, -1],</span>
<span class="GAPprompt">></span> <span class="GAPinput">                            [0, 1, 0],</span>
<span class="GAPprompt">></span> <span class="GAPinput">                            [1, 0, 0]]);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">Order(mat);</span>
4
</pre></div>

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

<h4>5.6 <span class="Heading">
      Max-plus and min-plus matrices
    </span></h4>

<p>In this section we describe operations in <strong class="pkg">Semigroups</strong> specifically for max-plus and min-plus matrices. These are in addition to those given elsewhere in this chapter for arbitrary matrices over semirings. These include:</p>


<ul>
<li><p><code class="func">InverseOp</code> (<a href="chap5_mj.html#X82EC4F49877D6EB1"><span class="RefLink">5.6-1</span></a>)</p>

</li>
<li><p><code class="func">RadialEigenvector</code> (<a href="chap5_mj.html#X83663A5387042B69"><span class="RefLink">5.6-2</span></a>)</p>

</li>
<li><p><code class="func">SpectralRadius</code> (<a href="chap5_mj.html#X83FCFB368743E4BA"><span class="RefLink">5.6-3</span></a>)</p>

</li>
<li><p><code class="func">UnweightedPrecedenceDigraph</code> (<a href="chap5_mj.html#X869F60527C2B9328"><span class="RefLink">5.6-4</span></a>)</p>

</li>
</ul>
<p><a id="X82EC4F49877D6EB1" name="X82EC4F49877D6EB1"></a></p>

<h5>5.6-1 InverseOp</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; InverseOp</code>( <var class="Arg">mat</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Returns: A max-plus matrix.</p>

<p>If <var class="Arg">mat</var> is an invertible max-plus matrix (i.e. belongs to the category <code class="func">IsMaxPlusMatrix</code> (<a href="chap5_mj.html#X782480C686F1A663"><span class="RefLink">5.1-8</span></a>) and is a row permutation applied to the identity), then <code class="code">InverseOp</code> returns the inverse of <var class="Arg">mat</var>. This method is described in <a href="chapBib_mj.html#biBKacie2009aa">[Far09]</a>.</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">InverseOp(Matrix(IsMaxPlusMatrix, [[-infinity, -infinity, 0],</span>
<span class="GAPprompt">></span> <span class="GAPinput">                                      [0, -infinity, -infinity],</span>
<span class="GAPprompt">></span> <span class="GAPinput">                                      [-infinity, 0, -infinity]]));</span>
Matrix(IsMaxPlusMatrix, [[-infinity, 0, -infinity],
  [-infinity, -infinity, 0], [0, -infinity, -infinity]])
</pre></div>

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

<h5>5.6-2 RadialEigenvector</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; RadialEigenvector</code>( <var class="Arg">mat</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Returns: A vector.</p>

<p>If <var class="Arg">mat</var> is a <code class="code">n</code> by <code class="code">n</code> max-plus matrix (i.e. belongs to the category <code class="func">IsMaxPlusMatrix</code> (<a href="chap5_mj.html#X782480C686F1A663"><span class="RefLink">5.1-8</span></a>)), then <code class="code">RadialEigenvector</code> returns an eigenvector corresponding to the eigenvalue equal to the spectral radius of <var class="Arg">mat</var>. This method is described in <a href="chapBib_mj.html#biBKacie2009aa">[Far09]</a>.</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">RadialEigenvector(Matrix(IsMaxPlusMatrix, [[0, -3], [-2, -10]]));</span>
[ 0, -2 ]
</pre></div>

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

<h5>5.6-3 SpectralRadius</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; SpectralRadius</code>( <var class="Arg">mat</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Returns: A rational number.</p>

<p>If <var class="Arg">mat</var> is a max-plus matrix (i.e. belongs to the category <code class="func">IsMaxPlusMatrix</code> (<a href="chap5_mj.html#X782480C686F1A663"><span class="RefLink">5.1-8</span></a>)), then <code class="code">SpectralRadius</code> returns the supremum of the set of eigenvalues of <var class="Arg">mat</var>. This method is described in <a href="chapBib_mj.html#biBBacelli1992aa">[BFCGOGJ92]</a>.</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">SpectralRadius(Matrix(IsMaxPlusMatrix, [[-infinity, 1, -4],</span>
<span class="GAPprompt">></span> <span class="GAPinput">                                           [2, -infinity, 0],</span>
<span class="GAPprompt">></span> <span class="GAPinput">                                           [0, 1, 1]]));</span>
3/2</pre></div>

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

<h5>5.6-4 UnweightedPrecedenceDigraph</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; UnweightedPrecedenceDigraph</code>( <var class="Arg">mat</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Returns: A digraph.</p>

<p>If <var class="Arg">mat</var> is a max-plus matrix (i.e. belongs to the category <code class="func">IsMaxPlusMatrix</code> (<a href="chap5_mj.html#X782480C686F1A663"><span class="RefLink">5.1-8</span></a>)), then <code class="code">UnweightedPrecedenceDigraph</code> returns the unweighted precedence digraph corresponding to <var class="Arg">mat</var>.</p>

<p>For an <code class="code">n</code> by <code class="code">n</code> matrix <var class="Arg">mat</var>, the unweighted precedence digraph is defined as the digraph with <code class="code">n</code> vertices where vertex <code class="code">i</code> is adjacent to vertex <code class="code">j</code> if and only if <var class="Arg">mat</var><code class="code">[i][j]</code> is not equal to <code class="keyw">-infinity</code>.</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">UnweightedPrecedenceDigraph(Matrix(IsMaxPlusMatrix, [[2, -2, 0],</span>
<span class="GAPprompt">></span> <span class="GAPinput">[-infinity, 10, -2], [-infinity, 2, 1]]));</span>
<immutable digraph with 3 vertices, 7 edges>
</pre></div>

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

<h4>5.7 <span class="Heading">
      Matrix semigroups
    </span></h4>

<p>In this section we describe operations and attributes in <strong class="pkg">Semigroups</strong> specifically for matrix semigroups. These are in addition to those given elsewhere in this chapter for arbitrary matrices over semirings. These include:</p>


<ul>
<li><p><code class="func">IsXMatrixSemigroup</code> (<a href="chap5_mj.html#X7DC6EB0680B3E4DD"><span class="RefLink">5.7-1</span></a>)</p>

</li>
<li><p><code class="func">IsFinite</code> (<a href="chap5_mj.html#X808A4061809A6E67"><span class="RefLink">5.7-3</span></a>)</p>

</li>
<li><p><code class="func">IsTorsion</code> (<a href="chap5_mj.html#X80C6B26284721409"><span class="RefLink">5.7-4</span></a>)</p>

</li>
<li><p><code class="func">NormalizeSemigroup</code> (<a href="chap5_mj.html#X873DE466868DA849"><span class="RefLink">5.7-5</span></a>)</p>

</li>
</ul>
<p>Random matrix semigroups can be created by using the function <code class="func">RandomSemigroup</code> (<a href="chap6_mj.html#X789DE9AB79FCFEB5"><span class="RefLink">6.6-1</span></a>). We can also create a matrix semigroup isomorphic to a given semigroup by using <code class="func">IsomorphismSemigroup</code> (<a href="chap6_mj.html#X838F18E87F765697"><span class="RefLink">6.5-1</span></a>) and <code class="func">AsSemigroup</code> (<a href="chap6_mj.html#X80ED104F85AE5134"><span class="RefLink">6.5-3</span></a>). These functions require a filter, and accept any of the filters in Section <a href="chap5_mj.html#X7DC6EB0680B3E4DD"><span class="RefLink">5.7-1</span></a>.</p>

<p>There are corresponding functions which can be used for matrix monoids: <code class="func">RandomMonoid</code> (<a href="chap6_mj.html#X789DE9AB79FCFEB5"><span class="RefLink">6.6-1</span></a>), <code class="func">IsomorphismMonoid</code> (<a href="chap6_mj.html#X83D03BE678C9974F"><span class="RefLink">6.5-2</span></a>), and <code class="func">AsMonoid</code> (<a href="chap6_mj.html#X7B22038F832B9C0F"><span class="RefLink">6.5-4</span></a>). These can be used with the filters in Section <a href="chap5_mj.html#X8616225581BC7414"><span class="RefLink">5.7-2</span></a>.</p>

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

<h5>5.7-1 <span class="Heading">Matrix semigroup filters</span></h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; IsMatrixOverSemiringSemigroup</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">&#an style='color: green'>8227; IsBooleanMatSemigroup</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">&#an style='color: green'>8227; IsMatrixOverFiniteFieldSemigroup</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">&#an style='color: green'>8227; IsMaxPlusMatrixSemigroup</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">&#an style='color: green'>8227; IsMinPlusMatrixSemigroup</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">&#an style='color: green'>8227; IsTropicalMatrixSemigroup</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">&#an style='color: green'>8227; IsTropicalMaxPlusMatrixSemigroup</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">&#an style='color: green'>8227; IsTropicalMinPlusMatrixSemigroup</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">&#an style='color: green'>8227; IsNTPMatrixSemigroup</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">&#an style='color: green'>8227; IsIntegerMatrixSemigroup</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>The above are the currently supported types of matrix semigroups. For monoids see Section <a href="chap5_mj.html#X8616225581BC7414"><span class="RefLink">5.7-2</span></a>.</p>

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

<h5>5.7-2 <span class="Heading">Matrix monoid filters</span></h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; IsMatrixOverSemiringMonoid</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">&#an style='color: green'>8227; IsBooleanMatMonoid</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">&#an style='color: green'>8227; IsMatrixOverFiniteFieldMonoid</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">&#an style='color: green'>8227; IsMaxPlusMatrixMonoid</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">&#an style='color: green'>8227; IsMinPlusMatrixMonoid</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">&#an style='color: green'>8227; IsTropicalMatrixMonoid</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">&#an style='color: green'>8227; IsTropicalMaxPlusMatrixMonoid</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">&#an style='color: green'>8227; IsTropicalMinPlusMatrixMonoid</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">&#an style='color: green'>8227; IsNTPMatrixMonoid</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">&#an style='color: green'>8227; IsIntegerMatrixMonoid</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>The above are the currently supported types of matrix monoids. They correspond to the matrix semigroup types in Section <a href="chap5_mj.html#X7DC6EB0680B3E4DD"><span class="RefLink">5.7-1</span></a>.</p>

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

<h5>5.7-3 IsFinite</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; IsFinite</code>( <var class="Arg">S</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 <var class="Arg">S</var> is a max-plus or min-plus matrix semigroup (i.e. belongs to the category <code class="func">IsMaxPlusMatrixSemigroup</code> (<a href="chap5_mj.html#X7DC6EB0680B3E4DD"><span class="RefLink">5.7-1</span></a>)), then <code class="code">IsFinite</code> returns <code class="keyw">true</code> if <var class="Arg">S</var> is finite and <code class="keyw">false</code> otherwise. This method is based on <a href="chapBib_mj.html#biBGaubert1996aa">[Gau96]</a> (max-plus) and <a href="chapBib_mj.html#biBSimon1978aa">[Sim78]</a> (min-plus). For min-plus matrix semigroups, this method is only valid if each min-plus matrix in the semigroup contains only non-negative integers. Note, this method is terminating and does not involve enumerating semigroups.</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">IsFinite(Semigroup(Matrix(IsMaxPlusMatrix,</span>
<span class="GAPprompt">></span> <span class="GAPinput">                             [[0, -3],</span>
<span class="GAPprompt">></span> <span class="GAPinput">                              [-2, -10]])));</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">IsFinite(Semigroup(Matrix(IsMaxPlusMatrix,</span>
<span class="GAPprompt">></span> <span class="GAPinput">                             [[1, -infinity, 2],</span>
<span class="GAPprompt">></span> <span class="GAPinput">                              [-2, 4, -infinity],</span>
<span class="GAPprompt">></span> <span class="GAPinput">                              [1, 0, 3]])));</span>
false
<span class="GAPprompt">gap></span> <span class="GAPinput">IsFinite(Semigroup(Matrix(IsMinPlusMatrix,</span>
<span class="GAPprompt">></span> <span class="GAPinput">                             [[infinity, 0],</span>
<span class="GAPprompt">></span> <span class="GAPinput">                              [5, 4]])));</span>
false
<span class="GAPprompt">gap></span> <span class="GAPinput">IsFinite(Semigroup(Matrix(IsMinPlusMatrix,</span>
<span class="GAPprompt">></span> <span class="GAPinput">                             [[1, 0],</span>
<span class="GAPprompt">></span> <span class="GAPinput">                              [0, infinity]])));</span>
true
</pre></div>

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

<h5>5.7-4 IsTorsion</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; IsTorsion</code>( <var class="Arg">S</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>Returns: <code class="keyw">true</code> or <code class="keyw">false</code>.</p>

<p>If <var class="Arg">S</var> is a max-plus matrix semigroup (i.e. belongs to the category <code class="func">IsMaxPlusMatrixSemigroup</code> (<a href="chap5_mj.html#X7DC6EB0680B3E4DD"><span class="RefLink">5.7-1</span></a>)), then <code class="code">IsTorsion</code> returns <code class="keyw">true</code> if <var class="Arg">S</var> is torsion and <code class="keyw">false</code> otherwise. This method is based on <a href="chapBib_mj.html#biBGaubert1996aa">[Gau96]</a> and draws on <a href="chapBib_mj.html#biBBurrell2016aa">[Bur16]</a>, <a href="chapBib_mj.html#biBBacelli1992aa">[BFCGOGJ92]</a> and <a href="chapBib_mj.html#biBKacie2009aa">[Far09]</a>.</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">IsTorsion(Semigroup(Matrix(IsMaxPlusMatrix,</span>
<span class="GAPprompt">></span> <span class="GAPinput">                             [[0, -3],</span>
<span class="GAPprompt">></span> <span class="GAPinput">                              [-2, -10]])));</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">IsTorsion(Semigroup(Matrix(IsMaxPlusMatrix,</span>
<span class="GAPprompt">></span> <span class="GAPinput">                              [[1, -infinity, 2],</span>
<span class="GAPprompt">></span> <span class="GAPinput">                               [-2, 4, -infinity],</span>
<span class="GAPprompt">></span> <span class="GAPinput">                               [1, 0, 3]])));</span>
false
</pre></div>

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

<h5>5.7-5 NormalizeSemigroup</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; NormalizeSemigroup</code>( <var class="Arg">S</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Returns: A semigroup.</p>

<p>This method applies to max-plus matrix semigroups (i.e. those belonging to the category <code class="func">IsMaxPlusMatrixSemigroup</code> (<a href="chap5_mj.html#X7DC6EB0680B3E4DD"><span class="RefLink">5.7-1</span></a>)) that are finitely generated, such that the spectral radius of the matrix equal to the sum of the generators (with respect to the max-plus semiring) is zero. <code class="code">NormalizeSemigroup</code> returns a semigroup of matrices all with strictly non-positive entries. Note that the output is isomorphic to a min-plus matrix semigroup. This method is based on <a href="chapBib_mj.html#biBGaubert1996aa">[Gau96]</a> and <a href="chapBib_mj.html#biBBurrell2016aa">[Bur16]</a>.</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">NormalizeSemigroup(Semigroup(Matrix(IsMaxPlusMatrix,</span>
<span class="GAPprompt">></span> <span class="GAPinput">                                       [[0, -3],</span>
<span class="GAPprompt">></span> <span class="GAPinput">                                        [-2, -10]])));</span>
<commutative semigroup of 2x2 max-plus matrices with 1 generator>
</pre></div>


<div class="chlinkprevnextbot"> <a href="chap0_mj.html">[Top of Book]</a>   <a href="chap0_mj.html#contents">[Contents]</a>    <a href="chap4_mj.html">[Previous Chapter]</a>    <a href="chap6_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="chap12_mj.html">12</a>  <a href="chap13_mj.html">13</a>  <a href="chap14_mj.html">14</a>  <a href="chap15_mj.html">15</a>  <a href="chap16_mj.html">16</a>  <a href="chap17_mj.html">17</a>  <a href="chap18_mj.html">18</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>

Messung V0.5 in Prozent
C=100 H=100 G=100

[0.88QuellennavigatorsProjekt 2026-06-18]