Quellcodebibliothek Statistik Leitseite products/Sources/formale Sprachen/GAP/pkg/semigroups/doc/   (Algebra von RWTH Aachen Version 4.15.1©)  Datei vom 29.7.2025 mit Größe 126 kB image not shown  

Quelle  chap5_mj.html   Sprache: HTML

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


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

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

<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en">
<head>
<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">‣ 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">‣ 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">‣ 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">‣ 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">‣ 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">‣ 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">‣ 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">‣ 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">‣ 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">‣ 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">‣ 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">‣ 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">‣ 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">‣ 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">‣ 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">‣ 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">‣ 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">‣ 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">‣ 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">‣ 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">‣ 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">‣ 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">‣ 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">‣ 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">‣ 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">‣ 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">‣ 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">‣ 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">‣ 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">‣ 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">‣ 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">‣ 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">‣ 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">‣ 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">‣ 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">‣ 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">‣ 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">‣ 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">‣ 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">‣ 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">‣ 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">‣ 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">‣ 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>
--> --------------------

--> maximum size reached

--> --------------------

100%


¤ Dauer der Verarbeitung: 0.91 Sekunden  (vorverarbeitet)  ¤

*© Formatika GbR, Deutschland




Wurzel

Suchen

Beweissystem der NASA

Beweissystem Isabelle

NIST Cobol Testsuite

Cephes Mathematical Library

Wiener Entwicklungsmethode

Haftungshinweis

Die Informationen auf dieser Webseite wurden nach bestem Wissen sorgfältig zusammengestellt. Es wird jedoch weder Vollständigkeit, noch Richtigkeit, noch Qualität der bereit gestellten Informationen zugesichert.

Bemerkung:

Die farbliche Syntaxdarstellung ist noch experimentell.