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(list)] with a part of length list[i] for every i. For example, if list = [1, 2, 3], then 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 n + 1 points which is isomorphic to the semigroup consisting of all partial transformation on n points. This monoid has (n + 1) ^ n elements.
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 n(n - 1) idempotents of degree n and rank n - 1 and has \(n ^ n - n!\) elements.
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(n) returns the monoid of transformations that preserve the usual order on \(\{1, 2, \ldots, n\}\), where n is a positive integer. OrderEndomorphisms(n) is generated by the \(\textit{n + 1}\) transformations:
\[ \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(n) returns the ideal of OrderEndomorphisms(n) consisting of the non-invertible elements, when n is at least 2. The only invertible element in OrderEndomorphisms(n) is the identity transformation. Therefore SingularOrderEndomorphisms(n) has \({2n-1\choose n-1} - 1\) elements.
OrderAntiEndomorphisms(n)OrderAntiEndomorphisms(n) returns the monoid of transformations that preserve or reverse the usual order on \(\{1, 2, \ldots, n\}\), where n is a positive integer. OrderAntiEndomorphisms(n) is generated by the generators of OrderEndomorphisms(n) along with the bijective transformation that reverses the order on \(\{1, 2, \ldots, n\}\). The monoid OrderAntiEndomorphisms(n) has \({2n-1\choose n-1} - n\) elements.
PartialOrderEndomorphisms(n)PartialOrderEndomorphisms(n) returns a monoid of transformations on n + 1 points that is isomorphic to the monoid consisting of all partial transformations that preserve the usual order on \(\{1, 2, \ldots, n\}\).
PartialOrderAntiEndomorphisms(n)PartialAntiOrderEndomorphisms(n) returns a monoid of transformations on n + 1 points that is isomorphic to the monoid consisting of all partial transformations that preserve or reverse the usual order on \(\{1, 2, \ldots, n\}\).
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(n) returns the inverse monoid of partial permutations that preserve the usual order on \(\{1, 2, \ldots, n\}\), where n is a positive integer. POI(n) is generated by the \(\textit{n}\) partial permutations:
\[ \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(n) returns the inverse monoid of partial permutations that preserve or reverse the usual order on \(\{1, 2, \ldots, n\}\), where n is a positive integer. PODI(n) is generated by the generators of POI(n), along with the permutation that reverses the usual order on \(\{1, 2, \ldots, n\}\). PODI(n) has \({2n\choose n} - n^{2} - 1\) elements.
POPI(n)POPI(n) returns the inverse monoid of partial permutations that preserve the orientation of \(\{1,2,\ldots, n\}\), where \(n\) is a positive integer. POPI(n) is generated by the partial permutations:
\[ \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(n) returns the inverse monoid of partial permutations that preserve or reverse the orientation of \(\{1, 2, \ldots, n\}\), where \(n\) is a positive integer. PORI(n) is generated by the generators of POPI(n), along with the permutation that reverses the usual order on \(\{1, 2, \ldots, n\}\). PORI(n) has \(\frac{n}{2}{2n\choose n} - n(n + 1)\) elements.
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 n.
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 n + 1 consisting of those bipartitions with n + 1 and -n - 1 in the same block; see [HR05], [Gro06], and [Eas19].
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 n + 1 consisting of those block bijections with n + 1 and -n - 1 in the same block; see [KM11] and [KMU15].
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 n + 1 consisting of those uniform block bijection with n + 1 and -n - 1 in the same block.
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(q). This monoid has q ^ (d ^ 2) elements.
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(q) that have determinant 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 d by d boolean matrices, and has 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(d) is generated by the four boolean matrices 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(d) 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 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(d) is known for some small values of 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 d = 2 and 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 (t + 2) ^ (d ^ 2) elements.
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 (t + 2) ^ (d ^ 2) elements.
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