Quellcode-Bibliothek chap5.html
Sprache: HTML
|
|
| products/Sources/formale Sprachen/GAP/pkg/semigroups/doc/chap5.html |
 |
<?xml version="1.0" encoding="UTF-8"?>
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN"
"http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en">
<head>
<title>GAP (Semigroups) - Chapter 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.html">Top</a> <a href="chap1.html">1</a> <a href="chap2.html">2</a> <a href="chap3.html">3</a> <a href="chap4.html">4</a> <a href="chap5.html">5</a> <a href="chap6.html">6</a> <a href="chap7.html">7</a> <a href="chap8.html">8</a> <a href="chap9.html">9</a> <a href="chap10.html">10</a> <a href="chap11.html">11</a> <a href="chap12.html">12</a> <a href="chap13.html">13</a> <a href="chap14.html">14</a> <a href="chap15.html">15</a> <a href="chap16.html">16</a> <a href="chap17.html">17</a> <a href="chap18.html">18</a> <a href="chapBib.html">Bib</a> <a href="chapInd.html">Ind</a> </div>
<div class="chlinkprevnexttop"> <a href="chap0.html">[Top of Book]</a> <a href="chap0.html#contents">[Contents]</a> <a href="chap4.html">[Previous Chapter]</a> <a href="chap6.html">[Next Chapter]</a> </div>
<p id="mathjaxlink" class="pcenter"><a href="chap5_mj.html">[MathJax on]</a></p>
<p><a id="X82D6B7FE7CAC0AFA" name="X82D6B7FE7CAC0AFA"></a></p>
<div class="ChapSects"><a href="chap5.html#X82D6B7FE7CAC0AFA">5 <span class="Heading">
Matrices over semirings
</span></a>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap5.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.html#X8711618C7A8A1B60">5.1-1 IsMatrixOverSemiring</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap5.html#X86F696B883677D6B">5.1-2 IsMatrixOverSemiringCollection</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap5.html#X7C1CDA817CE076FD">5.1-3 DimensionOfMatrixOverSemiring</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap5.html#X7FF0B2A783BA2D06">5.1-4 DimensionOfMatrixOverSemiringCollection</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap5.html#X7DCA234C86ED8BD3">5.1-5 Matrix</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap5.html#X85426D8885431ECE">5.1-6 AsMatrix</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap5.html#X82172D747D66C8CC">5.1-7 RandomMatrix</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap5.html#X782480C686F1A663">5.1-8 <span class="Heading">Matrix filters</span></a>
</span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap5.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.html#X8289FCCC8274C89D">5.1-10 AsList</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap5.html#X7D21408E845E4648">5.1-11 ThresholdTropicalMatrix</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap5.html#X7874559881FE8779">5.1-12 ThresholdNTPMatrix</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap5.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.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.html#X84A16D4D7D015885">5.3-1 BooleanMat</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap5.html#X7DA524567E0E7E16">5.3-2 AsBooleanMat</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap5.html#X87BDB89B7AAFE8AD"><code>5.3-3 \in</code></a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap5.html#X8629FA5F7B682078">5.3-4 OnBlist</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap5.html#X85E2FD8B82652876">5.3-5 Successors</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap5.html#X7E0FD5878106AB66">5.3-6 BooleanMatNumber</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap5.html#X793A1C277C1D7D6D">5.3-7 BlistNumber</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap5.html#X7EEA5011862E6298">5.3-8 CanonicalBooleanMat</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap5.html#X794C91597CC9F784">5.3-9 IsRowTrimBooleanMat</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap5.html#X7D22BA78790EFBC6">5.3-10 IsSymmetricBooleanMat</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap5.html#X7C373B7D87044050">5.3-11 IsReflexiveBooleanMat</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap5.html#X7CDAD39B856AC3E5">5.3-12 IsTransitiveBooleanMat</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap5.html#X8570C8A08549383D">5.3-13 IsAntiSymmetricBooleanMat</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap5.html#X7A68D87982A07C6F">5.3-14 IsTotalBooleanMat</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap5.html#X7D9BECEA7E9B72A7">5.3-15 IsPartialOrderBooleanMat</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap5.html#X82EA957982B79827">5.3-16 IsEquivalenceBooleanMat</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap5.html#X7E6B588887D34A0A">5.3-17 IsTransformationBooleanMat</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap5.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.html#X857E626783CCF766">5.4-1 RowSpaceBasis</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap5.html#X8733B04781B682E5">5.4-2 RightInverse</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap5.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.html#X7BC66ECE8378068E">5.5-1 InverseOp</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap5.html#X7CA636F080777C36">5.5-2 IsTorsion</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap5.html#X84F59A2687C62763">5.5-3 Order</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap5.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.html#X82EC4F49877D6EB1">5.6-1 InverseOp</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap5.html#X83663A5387042B69">5.6-2 RadialEigenvector</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap5.html#X83FCFB368743E4BA">5.6-3 SpectralRadius</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap5.html#X869F60527C2B9328">5.6-4 UnweightedPrecedenceDigraph</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap5.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.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.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.html#X808A4061809A6E67">5.7-3 IsFinite</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap5.html#X80C6B26284721409">5.7-4 IsTorsion</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap5.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⋅ 0 = 0 ⋅ 0 = 0 ⋅ 1 = 0</span>, and <span class="SimpleMath">1⋅ 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">Z∪ {-∞}</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">Z∪ {∞}</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">{-∞, 0, 1, ..., 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, ..., t, ∞}</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">N_t,p</span></strong></dt>
<dd><p>the semiring <span class="SimpleMath">N_t,p = {0, 1, ..., t, t + 1, ..., 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.html#X7A19D22B7A05CC2F"><span class="RefLink">6.1</span></a>. In other words, a version of the Froidure-Pin Algorithm <a href="chapBib.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.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.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.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.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.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.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">∞</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.html#X782480C686F1A663"><span class="RefLink">5.1-8</span></a>), <code class="func">IsTropicalMinPlusMatrix</code> (<a href="chap5.html#X782480C686F1A663"><span class="RefLink">5.1-8</span></a>), or <code class="func">IsNTPMatrix</code> (<a href="chap5.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.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.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.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.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.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.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.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.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.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.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.html#X782480C686F1A663"><span class="RefLink">5.1-8</span></a>), <code class="func">IsTropicalMinPlusMatrix</code> (<a href="chap5.html#X782480C686F1A663"><span class="RefLink">5.1-8</span></a>), or <code class="func">IsNTPMatrix</code> (<a href="chap5.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.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.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.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.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.html#X7D21408E845E4648"><span class="RefLink">5.1-11</span></a>); for ntp matrices <code class="func">ThresholdNTPMatrix</code> (<a href="chap5.html#X7874559881FE8779"><span class="RefLink">5.1-12</span></a>) and <code class="func">PeriodNTPMatrix</code> (<a href="chap5.html#X7874559881FE8779"><span class="RefLink">5.1-12</span></a>).</p>
<p>For matrices over finite fields see Section <a href="chap5.html#X873822B6830CE367"><span class="RefLink">5.4</span></a>; for Boolean matrices more details can be found in Section <a href="chap5.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.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.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">N_t,p = {0, 1, ..., t, t + 1, ..., 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.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.html#X7E0FD5878106AB66"><span class="RefLink">5.3-6</span></a>)</p>
</li>
<li><p><code class="func">Successors</code> (<a href="chap5.html#X85E2FD8B82652876"><span class="RefLink">5.3-5</span></a>)</p>
</li>
<li><p><code class="func">IsRowTrimBooleanMat</code> (<a href="chap5.html#X794C91597CC9F784"><span class="RefLink">5.3-9</span></a>), <code class="func">IsColTrimBooleanMat</code> (<a href="chap5.html#X794C91597CC9F784"><span class="RefLink">5.3-9</span></a>), and <code class="func">IsTrimBooleanMat</code> (<a href="chap5.html#X794C91597CC9F784"><span class="RefLink">5.3-9</span></a>),</p>
</li>
<li><p><code class="func">CanonicalBooleanMat</code> (<a href="chap5.html#X7EEA5011862E6298"><span class="RefLink">5.3-8</span></a>)</p>
</li>
<li><p><code class="func">IsSymmetricBooleanMat</code> (<a href="chap5.html#X7D22BA78790EFBC6"><span class="RefLink">5.3-10</span></a>)</p>
</li>
<li><p><code class="func">IsAntiSymmetricBooleanMat</code> (<a href="chap5.html#X8570C8A08549383D"><span class="RefLink">5.3-13</span></a>)</p>
</li>
<li><p><code class="func">IsTransitiveBooleanMat</code> (<a href="chap5.html#X7CDAD39B856AC3E5"><span class="RefLink">5.3-12</span></a>)</p>
</li>
<li><p><code class="func">IsReflexiveBooleanMat</code> (<a href="chap5.html#X7C373B7D87044050"><span class="RefLink">5.3-11</span></a>)</p>
</li>
<li><p><code class="func">IsTotalBooleanMat</code> (<a href="chap5.html#X7A68D87982A07C6F"><span class="RefLink">5.3-14</span></a>)</p>
</li>
<li><p><code class="func">IsOntoBooleanMat</code> (<a href="chap5.html#X7A68D87982A07C6F"><span class="RefLink">5.3-14</span></a>)</p>
</li>
<li><p><code class="func">IsPartialOrderBooleanMat</code> (<a href="chap5.html#X7D9BECEA7E9B72A7"><span class="RefLink">5.3-15</span></a>)</p>
</li>
<li><p><code class="func">IsEquivalenceBooleanMat</code> (<a href="chap5.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</ | |
