8
Standard examples

In this chapter we describe some standard examples of semigroups which are available in the **Semigroups** package.

In this section, we describe the operations in **Semigroups** that can be used to create transformation semigroups belonging to several standard classes of example. See Reference: Transformations for more information about transformations.

`‣ CatalanMonoid` ( n ) | ( operation ) |

Returns: A transformation monoid.

If `n` is a positive integer, then this operation returns the Catalan monoid of degree `n`. The *Catalan monoid* is the semigroup of the order-preserving and order-decreasing transformations of `[1 .. n]`

with the usual ordering.

The Catalan monoid is generated by the \(\textit{n - 1}\) transformations \(f_i\):

\[ \left( \begin{array}{cccccccccc} 1&2&3&\cdots& i &i + 1& i + 2 & \cdots & n\\ 1&2&3&\cdots& i &i & i + 2 & \cdots & n \end{array}\right), \qquad \]

where \(i = 1, \ldots, n - 1\) and has size equal to the \(n\)th Catalan number.

gap> S := CatalanMonoid(6); <transformation monoid of degree 6 with 5 generators> gap> Size(S); 132

`‣ EndomorphismsPartition` ( list ) | ( operation ) |

Returns: A transformation monoid.

If `list` is a list of positive integers, then `EndomorphismsPartition`

returns a monoid of endomorphisms preserving a partition of `[1 .. Sum(`

with a part of length `list`)]

for every `list`[i]`i`

. For example, if

, then `list` = [1, 2, 3]`EndomorphismsPartition`

returns the monoid of endomorphisms of the partition `[[1], [2, 3], [4, 5, 6]]`

.

If `f`

is a transformation of `[1 .. n]`

, then it is an **endomorphism** of a partition `P`

on `[1 .. n]`

if `(i, j)`

in `P`

implies that `(i ^ f, j ^ f)`

is in `P`

.

`EndomorphismsPartition`

returns a monoid with a minimal size generating set, as described in [ABMS15].

gap> S := EndomorphismsPartition([3, 3, 3]); <transformation semigroup of degree 9 with 4 generators> gap> Size(S); 531441

`‣ PartialTransformationMonoid` ( n ) | ( operation ) |

Returns: A transformation monoid.

If `n` is a positive integer, then this function returns a semigroup of transformations on

points which is isomorphic to the semigroup consisting of all partial transformation on `n` + 1`n` points. This monoid has `(`

elements.`n` + 1) ^ `n`

gap> S := PartialTransformationMonoid(5); <regular transformation monoid of degree 6 with 4 generators> gap> Size(S); 7776

`‣ SingularTransformationSemigroup` ( n ) | ( operation ) |

`‣ SingularTransformationMonoid` ( n ) | ( operation ) |

Returns: The semigroup of non-invertible transformations.

If `n` is a integer greater than 1, then this function returns the semigroup of non-invertible transformations, which is generated by the

idempotents of degree `n`(`n` - 1)`n` and rank

and has \(n ^ n - n!\) elements.`n` - 1

gap> S := SingularTransformationSemigroup(4); <regular transformation semigroup ideal of degree 4 with 1 generator> gap> Size(S); 232

`‣ OrderEndomorphisms` ( n ) | ( operation ) |

`‣ SingularOrderEndomorphisms` ( n ) | ( operation ) |

`‣ OrderAntiEndomorphisms` ( n ) | ( operation ) |

`‣ PartialOrderEndomorphisms` ( n ) | ( operation ) |

`‣ PartialOrderAntiEndomorphisms` ( n ) | ( operation ) |

Returns: A semigroup of transformations related to a linear order.

`OrderEndomorphisms(`

`n`)`OrderEndomorphisms(`

returns the monoid of transformations that preserve the usual order on \(\{1, 2, \ldots, n\}\), where`n`)`n`is a positive integer.`OrderEndomorphisms(`

is generated by the \(\textit{n + 1}\) transformations:`n`)\[ \left( \begin{array}{ccccccccc} 1&2&3&\cdots&n-1& n\\ 1&1&2&\cdots&n-2&n-1 \end{array}\right), \qquad \left( \begin{array}{ccccccccc} 1&2&\cdots&i-1& i& i+1&i+2&\cdots &n\\ 1&2&\cdots&i-1& i+1&i+1&i+2&\cdots &n\\ \end{array}\right) \]

where \(i=0,\ldots,n-1\), and has \({2n-1\choose n-1}\) elements.

`SingularOrderEndomorphisms(`

`n`)`SingularOrderEndomorphisms(`

returns the ideal of`n`)`OrderEndomorphisms(`

consisting of the non-invertible elements, when`n`)`n`is at least`2`

. The only invertible element in`OrderEndomorphisms(`

is the identity transformation. Therefore`n`)`SingularOrderEndomorphisms(`

has \({2n-1\choose n-1} - 1\) elements.`n`)`OrderAntiEndomorphisms(`

`n`)`OrderAntiEndomorphisms(`

returns the monoid of transformations that preserve or reverse the usual order on \(\{1, 2, \ldots, n\}\), where`n`)`n`is a positive integer.`OrderAntiEndomorphisms(`

is generated by the generators of`n`)`OrderEndomorphisms(`

along with the bijective transformation that reverses the order on \(\{1, 2, \ldots, n\}\). The monoid`n`)`OrderAntiEndomorphisms(`

has \({2n-1\choose n-1} - n\) elements.`n`)`PartialOrderEndomorphisms(`

`n`)`PartialOrderEndomorphisms(`

returns a monoid of transformations on`n`)

points that is isomorphic to the monoid consisting of all partial transformations that preserve the usual order on \(\{1, 2, \ldots, n\}\).`n`+ 1`PartialOrderAntiEndomorphisms(`

`n`)`PartialAntiOrderEndomorphisms(`

returns a monoid of transformations on`n`)

points that is isomorphic to the monoid consisting of all partial transformations that preserve or reverse the usual order on \(\{1, 2, \ldots, n\}\).`n`+ 1

gap> S := OrderEndomorphisms(5); <regular transformation monoid of degree 5 with 5 generators> gap> IsIdempotentGenerated(S); true gap> Size(S) = Binomial(2 * 5 - 1, 5 - 1); true gap> Difference(S, SingularOrderEndomorphisms(5)); [ IdentityTransformation ] gap> SingularOrderEndomorphisms(10); <regular transformation semigroup ideal of degree 10 with 1 generator> gap> T := OrderAntiEndomorphisms(4); <regular transformation monoid of degree 4 with 5 generators> gap> Transformation([4, 2, 2, 1]) in T; true gap> U := PartialOrderEndomorphisms(6); <regular transformation monoid of degree 7 with 12 generators> gap> V := PartialOrderAntiEndomorphisms(6); <regular transformation monoid of degree 7 with 13 generators> gap> IsSubsemigroup(V, U); true

In this section, we describe the operations in **Semigroups** that can be used to create semigroups of partial permutations belonging to several standard classes of example. See Reference: Partial permutations for more information about partial permutations.

`‣ MunnSemigroup` ( S ) | ( attribute ) |

Returns: The Munn semigroup of a semilattice.

If `S` is a semilattice, then `MunnSemigroup`

returns the inverse semigroup of partial permutations of isomorphisms of principal ideals of `S`; called the *Munn semigroup* of `S`.

This function was written jointly by J. D. Mitchell, Yann Péresse (St Andrews), Yanhui Wang (York).

gap> S := InverseSemigroup([ > PartialPerm([1, 2, 3, 4, 5, 6, 7, 10], [4, 6, 7, 3, 8, 2, 9, 5]), > PartialPerm([1, 2, 7, 9], [5, 6, 4, 3])]); <inverse partial perm semigroup of rank 10 with 2 generators> gap> T := IdempotentGeneratedSubsemigroup(S);; gap> M := MunnSemigroup(T); <inverse partial perm semigroup of rank 60 with 7 generators> gap> NrIdempotents(M); 60 gap> NrIdempotents(S); 60

`‣ RookMonoid` ( n ) | ( operation ) |

Returns: An inverse monoid of partial permutations.

`RookMonoid`

is a synonym for `SymmetricInverseMonoid`

(Reference: SymmetricInverseMonoid).

gap> S := RookMonoid(4); <symmetric inverse monoid of degree 4> gap> S = SymmetricInverseMonoid(4); true

`‣ POI` ( n ) | ( operation ) |

`‣ PODI` ( n ) | ( operation ) |

`‣ POPI` ( n ) | ( operation ) |

`‣ PORI` ( n ) | ( operation ) |

Returns: An inverse monoid of partial permutations related to a linear order.

`POI(`

`n`)`POI(`

returns the inverse monoid of partial permutations that preserve the usual order on \(\{1, 2, \ldots, n\}\), where`n`)`n`is a positive integer.`POI(`

is generated by the \(\textit{n}\) partial permutations:`n`)\[ \left( \begin{array}{ccccc} 1&2&3&\cdots&n\\ -&1&2&\cdots&n-1 \end{array}\right), \qquad \left( \begin{array}{ccccccccc} 1&2&\cdots&i-1& i& i+1&i+2&\cdots &n\\ 1&2&\cdots&i-1& i+1&-&i+2&\cdots&n\\ \end{array}\right) \]

where \(i = 1, \ldots, n - 1\), and has \({2n\choose n}\) elements.

`PODI(`

`n`)`PODI(`

returns the inverse monoid of partial permutations that preserve or reverse the usual order on \(\{1, 2, \ldots, n\}\), where`n`)`n`is a positive integer.`PODI(`

is generated by the generators of`n`)`POI(`

, along with the permutation that reverses the usual order on \(\{1, 2, \ldots, n\}\).`n`)`PODI(`

has \({2n\choose n} - n^{2} - 1\) elements.`n`)`POPI(`

`n`)`POPI(`

returns the inverse monoid of partial permutations that preserve the orientation of \(\{1,2,\ldots, n\}\), where \(n\) is a positive integer.`n`)`POPI(`

is generated by the partial permutations:`n`)\[ \left( \begin{array}{ccccc} 1&2&\cdots&n-1&n\\ 2&3&\cdots&n&1 \end{array}\right),\qquad \left( \begin{array}{cccccc} 1&2&\cdots&n-2&n-1&n\\ 1&2&\cdots&n-2&n&- \end{array}\right), \]

and has \(1+\frac{n}{2}{2n\choose n}\) elements.

`PORI(`

`n`)`PORI(`

returns the inverse monoid of partial permutations that preserve or reverse the orientation of \(\{1, 2, \ldots, n\}\), where \(n\) is a positive integer.`n`)`PORI(`

is generated by the generators of`n`)`POPI(`

, along with the permutation that reverses the usual order on \(\{1, 2, \ldots, n\}\).`n`)`PORI(`

has \(\frac{n}{2}{2n\choose n} - n(n + 1)\) elements.`n`)

gap> S := PORI(10); <inverse partial perm monoid of rank 10 with 3 generators> gap> S := POPI(10); <inverse partial perm monoid of rank 10 with 2 generators> gap> Size(S) = 1 + 5 * Binomial(20, 10); true gap> S := PODI(10); <inverse partial perm monoid of rank 10 with 11 generators> gap> S := POI(10); <inverse partial perm monoid of rank 10 with 10 generators> gap> Size(S) = Binomial(20, 10); true gap> IsSubsemigroup(PORI(10), PODI(10)) > and IsSubsemigroup(PORI(10), POPI(10)) > and IsSubsemigroup(PODI(10), POI(10)) > and IsSubsemigroup(POPI(10), POI(10)); true

In this section, we describe the operations in **Semigroups** that can be used to create bipartition semigroups belonging to several standard classes of example. See Chapter 3 for more information about bipartitions.

`‣ PartitionMonoid` ( n ) | ( operation ) |

`‣ RookPartitionMonoid` ( n ) | ( operation ) |

`‣ SingularPartitionMonoid` ( n ) | ( operation ) |

Returns: A bipartition monoid.

If `n` is a non-negative integer, then this operation returns the partition monoid of degree `n`. The *partition monoid of degree n* is the monoid consisting of all the bipartitions of degree

`SingularPartitionMonoid`

returns the ideal of the partition monoid consisting of the non-invertible elements (i.e. those not in the group of units), when `n` is positive.

If `n` is positive, then `RookPartitionMonoid`

returns submonoid of the partition monoid of degree

consisting of those bipartitions with `n` + 1

and `n` + 1`-`

in the same block; see [HR05], [Gro06], and [Eas19].`n` - 1

gap> S := PartitionMonoid(4); <regular bipartition *-monoid of size 4140, degree 4 with 4 generators> gap> Size(S); 4140 gap> T := SingularPartitionMonoid(4); <regular bipartition *-semigroup ideal of degree 4 with 1 generator> gap> Size(S) - Size(T) = Factorial(4); true gap> S := RookPartitionMonoid(4); <regular bipartition *-monoid of degree 5 with 5 generators> gap> Size(S); 21147

`‣ BrauerMonoid` ( n ) | ( operation ) |

`‣ PartialBrauerMonoid` ( n ) | ( operation ) |

`‣ SingularBrauerMonoid` ( n ) | ( operation ) |

Returns: A bipartition monoid.

If `n` is a non-negative integer, then this operation returns the Brauer monoid of degree `n`. The *Brauer monoid* is the submonoid of the partition monoid consisiting of those bipartitions where the size of every block is 2.

`PartialBrauerMonoid`

returns the partial Brauer monoid, which is the submonoid of the partition monoid consisting of those bipartitions where the size of every block is *at most* 2. The partial Brauer monoid contains the Brauer monoid as a submonoid.

`SingularBrauerMonoid`

returns the ideal of the Brauer monoid consisting of the non-invertible elements (i.e. those not in the group of units), when `n` is at least 2.

gap> S := BrauerMonoid(4); <regular bipartition *-monoid of degree 4 with 3 generators> gap> IsSubsemigroup(S, JonesMonoid(4)); true gap> Size(S); 105 gap> SingularBrauerMonoid(8); <regular bipartition *-semigroup ideal of degree 8 with 1 generator> gap> S := PartialBrauerMonoid(3); <regular bipartition *-monoid of degree 3 with 8 generators> gap> IsSubsemigroup(S, BrauerMonoid(3)); true gap> Size(S); 76

`‣ JonesMonoid` ( n ) | ( operation ) |

`‣ TemperleyLiebMonoid` ( n ) | ( operation ) |

`‣ SingularJonesMonoid` ( n ) | ( operation ) |

Returns: A bipartition monoid.

If `n` is a non-negative integer, then this operation returns the Jones monoid of degree `n`. The *Jones monoid* is the subsemigroup of the Brauer monoid consisting of those bipartitions that are planar; see `PlanarPartitionMonoid`

(8.3-9). The Jones monoid is sometimes referred to as the **Temperley-Lieb monoid**.

`SingularJonesMonoid`

returns the ideal of the Jones monoid consisting of the non-invertible elements (i.e. those not in the group of units), when `n` is at least 2.

gap> S := JonesMonoid(4); <regular bipartition *-monoid of degree 4 with 3 generators> gap> S = TemperleyLiebMonoid(4); true gap> SingularJonesMonoid(8); <regular bipartition *-semigroup ideal of degree 8 with 1 generator>

`‣ PartialJonesMonoid` ( n ) | ( operation ) |

Returns: A bipartition monoid.

If `n` is a non-negative integer, then `PartialJonesMonoid`

returns the partial Jones monoid of degree `n`. The *partial Jones monoid* is a subsemigroup of the partial Brauer monoid. An element of the partial Brauer monoid is contained in the partial Jones monoid if the partition that it defines is finer than the partition defined by some element of the Jones monoid. In other words, an element of the partial Jones monoid can be formed from some element `x`

of the Jones monoid by replacing some blocks `[a, b]`

of `x`

by singleton blocks `[a], [b]`

.

Note that, in general, the partial Jones monoid of degree `n` is strictly contained in the Motzkin monoid of the same degree.

See `PartialBrauerMonoid`

(8.3-2), `JonesMonoid`

(8.3-3), and `MotzkinMonoid`

(8.3-6).

gap> S := PartialJonesMonoid(4); <regular bipartition *-monoid of degree 4 with 7 generators> gap> T := JonesMonoid(4); <regular bipartition *-monoid of degree 4 with 3 generators> gap> U := MotzkinMonoid(4); <regular bipartition *-monoid of degree 4 with 8 generators> gap> IsSubsemigroup(U, S); true gap> IsSubsemigroup(S, T); true gap> Size(U); 323 gap> Size(S); 143 gap> Size(T); 14

`‣ AnnularJonesMonoid` ( n ) | ( operation ) |

Returns: A bipartition monoid.

If `n` is a non-negative integer, then `AnnularJonesMonoid`

returns the annular Jones monoid of degree `n`. The *annular Jones monoid* is the subsemigroup of the partition monoid consisting of all annular bipartitions whose blocks have size 2 (annular bipartitions are defined in Chapter 3). See `BrauerMonoid`

(8.3-2).

gap> S := AnnularJonesMonoid(4); <regular bipartition *-monoid of degree 4 with 2 generators>

`‣ MotzkinMonoid` ( n ) | ( operation ) |

Returns: A bipartition monoid.

If `n` is a non-negative integer, then this operation returns the Motzkin monoid of degree `n`. The *Motzkin monoid* is the subsemigroup of the partial Brauer monoid consisting of those bipartitions that are planar (planar bipartitions are defined in Chapter 3).

Note that the Motzkin monoid of degree `n` contains the partial Jones monoid of degree `n`, but in general, these monoids are not equal; see `PartialJonesMonoid`

(8.3-4).

gap> S := MotzkinMonoid(4); <regular bipartition *-monoid of degree 4 with 8 generators> gap> T := PartialJonesMonoid(4); <regular bipartition *-monoid of degree 4 with 7 generators> gap> IsSubsemigroup(S, T); true gap> Size(S); 323 gap> Size(T); 143

`‣ DualSymmetricInverseSemigroup` ( n ) | ( operation ) |

`‣ DualSymmetricInverseMonoid` ( n ) | ( operation ) |

`‣ SingularDualSymmetricInverseMonoid` ( n ) | ( operation ) |

`‣ PartialDualSymmetricInverseMonoid` ( n ) | ( operation ) |

Returns: An inverse bipartition monoid.

If `n` is a positive integer, then the operations `DualSymmetricInverseSemigroup`

and `DualSymmetricInverseMonoid`

return the dual symmetric inverse monoid of degree `n`, which is the subsemigroup of the partition monoid consisting of the block bijections of degree `n`.

`SingularDualSymmetricInverseMonoid`

returns the ideal of the dual symmetric inverse monoid consisting of the non-invertible elements (i.e. those not in the group of units), when `n` is at least 2.

`PartialDualSymmetricInverseMonoid`

returns the submonoid of the dual symmetric inverse monoid of degree

consisting of those block bijections with `n` + 1

and `n` + 1`-`

in the same block; see [KM11] and [KMU15].`n` - 1

See `IsBlockBijection`

(3.5-16).

gap> Number(PartitionMonoid(3), IsBlockBijection); 25 gap> S := DualSymmetricInverseSemigroup(3); <inverse block bijection monoid of degree 3 with 3 generators> gap> Size(S); 25 gap> S := PartialDualSymmetricInverseMonoid(5); <inverse block bijection monoid of degree 6 with 4 generators> gap> Size(S); 29072

`‣ UniformBlockBijectionMonoid` ( n ) | ( operation ) |

`‣ FactorisableDualSymmetricInverseMonoid` ( n ) | ( operation ) |

`‣ SingularUniformBlockBijectionMonoid` ( n ) | ( operation ) |

`‣ PartialUniformBlockBijectionMonoid` ( n ) | ( operation ) |

`‣ SingularFactorisableDualSymmetricInverseMonoid` ( n ) | ( operation ) |

`‣ PlanarUniformBlockBijectionMonoid` ( n ) | ( operation ) |

`‣ SingularPlanarUniformBlockBijectionMonoid` ( n ) | ( operation ) |

Returns: An inverse bipartition monoid.

If `n` is a positive integer, then this operation returns the uniform block bijection monoid of degree `n`. The *uniform block bijection monoid* is the submonoid of the partition monoid consisting of the block bijections of degree \(n\) where the number of positive integers in a block equals the number of negative integers in that block. The uniform block bijection monoid is also referred to as the *factorisable dual symmetric inverse monoid*.

`SingularUniformBlockBijectionMonoid`

returns the ideal of the uniform block bijection monoid consisting of the non-invertible elements (i.e. those not in the group of units), when `n` is at least 2.

`PlanarUniformBlockBijectionMonoid`

returns the submonoid of the uniform block bijection monoid consisting of the planar elements (i.e. those in the planar partition monoid, see `PlanarPartitionMonoid`

(8.3-9)).

`SingularPlanarUniformBlockBijectionMonoid`

returns the ideal of the planar uniform block bijection monoid consisting of the non-invertible elements (i.e. those not in the group of units), when `n` is at least 2.

`PartialUniformBlockBijectionMonoid`

returns the submonoid of the uniform block bijection monoid of degree

consisting of those uniform block bijection with `n` + 1

and `n` + 1`-`

in the same block.`n` - 1

See `IsUniformBlockBijection`

(3.5-17).

gap> S := UniformBlockBijectionMonoid(4); <inverse block bijection monoid of degree 4 with 3 generators> gap> Size(PlanarUniformBlockBijectionMonoid(8)); 128 gap> S := DualSymmetricInverseMonoid(4); <inverse block bijection monoid of degree 4 with 3 generators> gap> IsFactorisableInverseMonoid(S); false gap> S := UniformBlockBijectionMonoid(4); <inverse block bijection monoid of degree 4 with 3 generators> gap> IsFactorisableInverseMonoid(S); true gap> S := AsSemigroup(IsBipartitionSemigroup, > SymmetricInverseMonoid(5)); <inverse bipartition monoid of degree 5 with 3 generators> gap> IsFactorisableInverseMonoid(S); true gap> S := PartialUniformBlockBijectionMonoid(5); <inverse block bijection monoid of degree 6 with 4 generators> gap> NrIdempotents(S); 203 gap> IsFactorisableInverseMonoid(S); true

`‣ PlanarPartitionMonoid` ( n ) | ( operation ) |

`‣ SingularPlanarPartitionMonoid` ( n ) | ( operation ) |

Returns: A bipartition monoid.

If `n` is a positive integer, then this operation returns the planar partition monoid of degree `n` which is the monoid consisting of all the planar bipartitions of degree `n` (planar bipartitions are defined in Chapter 3).

`SingularPlanarPartitionMonoid`

returns the ideal of the planar partition monoid consisting of the non-invertible elements (i.e. those not in the group of units).

gap> S := PlanarPartitionMonoid(3); <regular bipartition *-monoid of degree 3 with 5 generators> gap> Size(S); 132 gap> T := SingularPlanarPartitionMonoid(3); <regular bipartition *-semigroup ideal of degree 3 with 1 generator> gap> Size(T); 131 gap> Difference(S, T); [ <block bijection: [ 1, -1 ], [ 2, -2 ], [ 3, -3 ]> ]

`‣ ModularPartitionMonoid` ( m, n ) | ( operation ) |

`‣ SingularModularPartitionMonoid` ( m, n ) | ( operation ) |

`‣ PlanarModularPartitionMonoid` ( m, n ) | ( operation ) |

`‣ SingularPlanarModularPartitionMonoid` ( m, n ) | ( operation ) |

Returns: A bipartition monoid.

If `m` and `n` are positive integers, then this operation returns the modular-`m` partition monoid of degree `n`. The *modular-*`m` *partition monoid* is the submonoid of the partition monoid such that the numbers of positive and negative integers contained in each block are congruent mod `m`.

`SingularModularPartitionMonoid`

returns the ideal of the modular partition monoid consisting of the non-invertible elements (i.e. those not in the group of units), when either `m = n = 1` or `m, n > 1`.

`PlanarModularPartitionMonoid`

returns the submonoid of the modular-`m` partition monoid consisting of the planar elements (i.e. those in the planar partition monoid, see `PlanarPartitionMonoid`

(8.3-9)).

`SingularPlanarModularPartitionMonoid`

returns the ideal of the planar modular partition monoid consisting of the non-invertible elements (i.e. those not in the group of units), when either `m = n = 1` or `m, n > 1`.

gap> S := ModularPartitionMonoid(3, 6); <regular bipartition *-monoid of degree 6 with 4 generators> gap> Size(S); 36243 gap> S := SingularModularPartitionMonoid(1, 1); <commutative inverse bipartition semigroup ideal of degree 1 with 1 generator> gap> Size(SingularModularPartitionMonoid(2, 4)); 355 gap> S := PlanarModularPartitionMonoid(4, 9); <regular bipartition *-monoid of degree 9 with 14 generators> gap> Size(S); 1795 gap> S := SingularPlanarModularPartitionMonoid(3, 5); <regular bipartition *-semigroup ideal of degree 5 with 1 generator> gap> Size(SingularPlanarModularPartitionMonoid(1, 2)); 13

`‣ ApsisMonoid` ( m, n ) | ( operation ) |

`‣ SingularApsisMonoid` ( m, n ) | ( operation ) |

`‣ CrossedApsisMonoid` ( m, n ) | ( operation ) |

`‣ SingularCrossedApsisMonoid` ( m, n ) | ( operation ) |

Returns: A bipartition monoid.

If `m` and `n` are positive integers, then this operation returns the `m`-apsis monoid of degree `n`. The `m`*-apsis monoid* is the monoid of bipartitions generated when the diapses in generators of the Jones monoid are replaced with `m`-apses. Note that an `m`*-apsis* is a block that contains precisely `m` consecutive integers.

`SingularApsisMonoid`

returns the ideal of the apsis monoid consisting of the non-invertible elements (i.e. those not in the group of units), when `m` \(\leq\) `n`.

`CrossedApsisGeneratedMonoid`

returns the semigroup generated by the symmetric group of degree `n` and the `m`-apsis monoid of degree `n`.

`SingularCrossedApsisMonoid`

returns the ideal of the crossed apsis monoid consisting of the non-invertible elements (i.e. those not in the group of units), when `m <= n`.

gap> S := ApsisMonoid(3, 7); <regular bipartition *-monoid of degree 7 with 5 generators> gap> Size(S); 320 gap> T := SingularApsisMonoid(3, 7); <regular bipartition *-semigroup ideal of degree 7 with 1 generator> gap> Difference(S, T) = [One(S)]; true gap> Size(CrossedApsisMonoid(2, 5)); 945 gap> SingularCrossedApsisMonoid(4, 6); <regular bipartition *-semigroup ideal of degree 6 with 1 generator>

In this section, we describe the operations in **Semigroups** that can be used to create standard examples of semigroups of partitioned binary relations (PBRs). See Chapter 4 for more information about PBRs.

`‣ FullPBRMonoid` ( n ) | ( operation ) |

Returns: A PBR monoid.

If `n` is a positive integer not greater than `2`

, then this operation returns the monoid consisting of all of the partitioned binary relations (PBRs) of degree `n`; called the *full PBR monoid*. There are `2 ^ ((2 * n) ^ 2)`

PBRs of degree `n`. The full PBR monoid of degree `n` is currently too large to compute when \(\textit{n} \geq 3\).

The full PBR monoid is not regular in general.

gap> S := FullPBRMonoid(1); <pbr monoid of degree 1 with 4 generators> gap> S := FullPBRMonoid(2); <pbr monoid of degree 2 with 10 generators>

In this section, we describe the operations in **Semigroups** that can be used to create semigroups of matrices over a finite field that belonging to several standard classes of example. See the section Matrices over finite fields for more information about matrices over a finite field.

`‣ FullMatrixMonoid` ( d, q ) | ( operation ) |

`‣ GeneralLinearMonoid` ( d, q ) | ( operation ) |

`‣ GLM` ( d, q ) | ( operation ) |

Returns: A matrix monoid.

These operations return the full matrix monoid of `d` by `d` matrices over the field with `q` elements. The *full matrix monoid*, also known as the *general linear monoid*, with these parameters, is the monoid consisting of all `d` by `d` matrices with entries from the field `GF(`

. This monoid has `q`)

elements.`q` ^ (`d` ^ 2)

gap> S := FullMatrixMonoid(2, 4); <general linear monoid 2x2 over GF(2^2)> gap> Size(S); 256 gap> S = GeneralLinearMonoid(2, 4); true gap> GLM(2, 2); <general linear monoid 2x2 over GF(2)>

`‣ SpecialLinearMonoid` ( d, q ) | ( operation ) |

`‣ SLM` ( d, q ) | ( operation ) |

Returns: A matrix monoid.

These operations return the special linear monoid of `d` by `d` matrices over the field with `q` elements. The *special linear monoid* is the monoid consisting of all `d` by `d` matrices with entries from the field `GF(`

that have determinant `q`)`0`

or `1`

. In other words, the special linear monoid is formed from the general linear monoid of the same parameters by replacing its group of units (the general linear group) by the special linear group.

gap> S := SpecialLinearMonoid(2, 4); <regular monoid of 2x2 matrices over GF(2^2) with 3 generators> gap> S = SLM(2, 4); true gap> Size(S); 136

`‣ IsFullMatrixMonoid` ( S ) | ( property ) |

`‣ IsGeneralLinearMonoid` ( S ) | ( property ) |

`IsFullMatrixMonoid`

and `IsGeneralLinearMonoid`

return `true`

if the semigroup `S`

was created using either of the commands `FullMatrixMonoid`

(8.5-1) or `GeneralLinearMonoid`

(8.5-1) and `false`

otherwise.

gap> S := RandomSemigroup(IsTransformationSemigroup, 4, 4);; gap> IsFullMatrixMonoid(S); false gap> S := GeneralLinearMonoid(3, 3); <general linear monoid 3x3 over GF(3)> gap> IsFullMatrixMonoid(S); true

In this section, we describe the operations in **Semigroups** that can be used to create semigroups of boolean matrices belonging to several standard classes of example. See the section Boolean matrices for more information about boolean matrices.

`‣ FullBooleanMatMonoid` ( d ) | ( operation ) |

Returns: The monoid of all boolean matrices of dimension `d`.

If `d` is a positive integer less than or equal to `5`

, then this operation returns the full boolean matrix monoid of dimension `d`. The *full boolean matrix monoid of dimension d* is the monoid consisting of all

`2 ^ (``n` ^ 2)

matrices.`FullBooleanMatMonoid`

returns a monoid with a generating set that is minimal in size. These generating sets are pre-computed.

gap> S := FullBooleanMatMonoid(3); <monoid of 3x3 boolean matrices with 5 generators> gap> Size(S); 512

`‣ RegularBooleanMatMonoid` ( d ) | ( operation ) |

Returns: A monoid of boolean matrices.

If `d` is a positive integer, then `RegularBooleanMatMonoid`

returns the monoid generated by the regular `d` by `d` boolean matrices. Note that this monoid is *not* regular in general. `RegularBooleanMatMonoid(`

is generated by the four boolean matrices `d`)`A, B, C, D`

, whose `true`

entries are:

`A[i][i + 1]`

and`A[n][1]`

, for \(i \in \{1, \ldots, n - 1\}\);`B[1][2]`

,`B[2][1]`

, and`B[i][i]`

for \(i \in \{3, \ldots, n\}\);`C[1][2]`

and`C[i][i]`

, for \(i \in \{2, \ldots, n - 1\}\); and`D[1][2]`

,`D[i][i]`

, for \(i \in \{2, \ldots, n\}\), and`D[n][1]`

.

This monoid has nearly `2 ^ (n ^ 2)`

elements.

`‣ ReflexiveBooleanMatMonoid` ( d ) | ( operation ) |

Returns: A monoid of boolean matrices.

If `d` is a positive integer less than or equal to `5`

, then this operation returns the monoid consisting of all reflexive `d` by `d` boolean matrices. A boolean matrix `mat`

is *reflexive* if each entry of its leading diagonal is `true`

, i.e. if `mat[i][i]`

is `true`

for all \(i \in \{1, \ldots, d\}\).

The generating sets for the monoids returned by `ReflexiveBooleanMatMonoid`

are pre-computed, and read from a file. Small generating sets are not known for \(\textit{d} \geq 6\).

gap> S := ReflexiveBooleanMatMonoid(3); <monoid of 3x3 boolean matrices with 8 generators> gap> Size(S); 64

`‣ HallMonoid` ( d ) | ( operation ) |

Returns: A monoid of boolean matrices.

If `d` is a positive integer less than or equal to `5`

, then this operation returns the monoid consisting Hall matrices of degree `d`. A *Hall matrix* is a boolean matrix in which every column and every row contains at least one `true`

entry. Equivalently, a Hall matrix is a boolean matrix than contains a permutation.

A Hall matrix of dimension `d` corresponds to a solution to Hall's Marriage Problem, when there are two collection of `d` people. Thus the number of solutions to Hall's Marriage Problem in this instance is the number of elements of `HallMonoid(`

.`d`)

The operation `HallMonoid`

returns a monoid with a generating set that is minimal in size. These generating sets are pre-computed, and a minimal generating set is not known for larger dimensions.

gap> S := HallMonoid(3); <monoid of 3x3 boolean matrices with 4 generators> gap> Size(S); 247

`‣ GossipMonoid` ( d ) | ( operation ) |

Returns: A monoid of boolean matrices.

If `d` is a positive integer, then this operation returns the `d` by `d` gossip monoid. The *gossip monoid* is defined to be the monoid generated by the collection of all `d` by `d` boolean matrices that define an equivalence relation; see `IsEquivalenceBooleanMat`

(5.3-16).

For \(\textit{d} \geq 2\), `GossipMonoid(`

returns a monoid with \({d \choose 2}\) generators. The generating set is the collection of boolean matrices that define an equivalence relation that has one equivalence class of size `d`)`2`

, and no other non-trivial equivalence classes. Note that this generating set is strictly contained within the collection of all equivalence relation boolean matrices.

The number of elements of `GossipMonoid(`

is known for some small values of `d`)`d` — see [BDF15] for more information about the gossip monoid, and its size for \(\textit{d} \leq 9\).

gap> S := GossipMonoid(3); <monoid of 3x3 boolean matrices with 3 generators> gap> Size(S); 11

`‣ TriangularBooleanMatMonoid` ( d ) | ( operation ) |

`‣ UnitriangularBooleanMatMonoid` ( d ) | ( operation ) |

Returns: A monoid of boolean matrices.

If `d` is a positive integer, then `TriangularBooleanMatMonoid`

returns the monoid consisting of the upper-triangular `d` by `d` boolean matrices. A boolean matrix is *upper-triangular* if the entry in row `i`

, column `j`

is `false`

whenever `i > j`

.

`UnitriangularBooleanMatMonoid`

returns the subsemigroup of the `TriangularBooleanMatMonoid`

that consists of reflexive upper-triangular boolean matrices; see `ReflexiveBooleanMatMonoid`

(8.6-3).

gap> S := TriangularBooleanMatMonoid(3); <monoid of 3x3 boolean matrices with 6 generators> gap> Size(S); 64 gap> T := UnitriangularBooleanMatMonoid(4); <monoid of 4x4 boolean matrices with 6 generators> gap> Size(T); 64

In this section, we describe the operations in **Semigroups** that can be used to create semigroups of matices over a semiring that belong to several standard classes of example. See Chapter 5 for more information about matrices over a semiring.

`‣ FullTropicalMaxPlusMonoid` ( d, t ) | ( operation ) |

Returns: A monoid of tropical max plus matrices.

If

and `d` = 2`t` is a positive integer, then `FullTropicalMaxPlusMonoid`

returns the monoid consisting of all `d` by `d` matrices with entries from the tropical max-plus semiring with threshold `t`. A small generating set for larger values of `d` is not currently known.

This monoid contains `(`

elements.`t` + 2) ^ (`d` ^ 2)

gap> S := FullTropicalMaxPlusMonoid(2, 5); <monoid of 2x2 tropical max-plus matrices with 24 generators> gap> Size(S); 2401 gap> (5 + 2) ^ (2 ^ 2); 2401

`‣ FullTropicalMinPlusMonoid` ( d, t ) | ( operation ) |

Returns: A monoid of tropical min plus matrices.

If `d` is equal to `2`

or `3`

, and `t` is a positive integer, then `FullTropicalMinPlusMonoid`

returns the monoid consisting of all `d` by `d` matrices with entries from the tropical min-plus semiring with threshold `t`. A small generating set for larger values of `d` is not currently known.

This monoid contains `(`

elements.`t` + 2) ^ (`d` ^ 2)

gap> S := FullTropicalMinPlusMonoid(2, 3); <monoid of 2x2 tropical min-plus matrices with 7 generators> gap> Size(S); 625 gap> (3 + 2) ^ (2 ^ 2); 625

generated by GAPDoc2HTML