[MathJax off]

7 Standard examples

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

7.1 Transformation semigroups

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.

7.1-1 CatalanMonoid

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

7.1-2 EndomorphismsPartition

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

7.1-3 PartialTransformationMonoid

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

7.1-4 SingularTransformationSemigroup

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

7.1-5 Semigroups of order-preserving transformations

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

7.1-6 EndomorphismMonoid

Returns: A monoid.

An endomorphism of digraph is a homomorphism DigraphHomomorphism (Digraphs: DigraphHomomorphism) from digraph back to itself.

EndomorphismMonoid, called with a single argument, returns the monoid of all endomorphisms of digraph.

If the colors argument is specified, then it will return the monoid of endomorphisms which respect the given colouring. The colouring colors can be in one of two forms:

• A list of positive integers of size the number of vertices of digraph, where colors[i] is the colour of vertex i.

• A list of lists, such that colors[i] is a list of all vertices with colour i.

See also GeneratorsOfEndomorphismMonoid (Digraphs: GeneratorsOfEndomorphismMonoid). Note that the performance of EndomorphismMonoid may differ from that of GeneratorsOfEndomorphismMonoid (Digraphs: GeneratorsOfEndomorphismMonoid) since the former incrementally adds newly discovered endomorphisms to the monoid using ClosureMonoid (6.4-1).

gap> gr := Digraph(List([1 .. 3], x -> [1 .. 3]));;
gap> EndomorphismMonoid(gr);
<transformation monoid of degree 3 with 3 generators>
gap> gr := CompleteDigraph(3);;
gap> EndomorphismMonoid(gr);
<transformation group of size 6, degree 3 with 2 generators>
gap> S := EndomorphismMonoid(gr, [1, 2, 2]);;
gap> IsGroupAsSemigroup(S);
true
gap> Size(S);
2
gap> S := EndomorphismMonoid(gr, [[1], [2, 3]]);;
gap> S := EndomorphismMonoid(gr, [1, 2, 2]);;
gap> IsGroupAsSemigroup(S);
true

7.2 Semigroups of partial permutations

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.

7.2-1 MunnSemigroup

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

7.2-2 RookMonoid

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

7.2-3 Inverse monoids of order-preserving partial permutations

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

7.3 Semigroups of bipartitions

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.

7.3-1 PartitionMonoid

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

7.3-2 BrauerMonoid

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 consisting 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

7.3-3 JonesMonoid

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 (7.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>

7.3-4 PartialJonesMonoid

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 (7.3-2), JonesMonoid (7.3-3), and MotzkinMonoid (7.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

7.3-5 AnnularJonesMonoid

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 (7.3-2).

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

7.3-6 MotzkinMonoid

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 (7.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

7.3-7 DualSymmetricInverseSemigroup

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

7.3-8 UniformBlockBijectionMonoid

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 (7.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

7.3-9 PlanarPartitionMonoid

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 ]> ]

7.3-10 ModularPartitionMonoid

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 (7.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

7.3-11 ApsisMonoid

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>

7.4 Standard PBR semigroups

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.

7.4-1 FullPBRMonoid

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>

7.5 Semigroups of matrices over a finite field

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.

7.5-1 FullMatrixMonoid

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)>

7.5-2 SpecialLinearMonoid

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

7.5-3 IsFullMatrixMonoid

IsFullMatrixMonoid and IsGeneralLinearMonoid return true if the semigroup S was created using either of the commands FullMatrixMonoid (7.5-1) or GeneralLinearMonoid (7.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

7.6 Semigroups of boolean matrices

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.

7.6-1 FullBooleanMatMonoid

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

7.6-2 RegularBooleanMatMonoid

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.

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

7.6-3 ReflexiveBooleanMatMonoid

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

7.6-4 HallMonoid

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

7.6-5 GossipMonoid

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

7.6-6 TriangularBooleanMatMonoid

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 (7.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

7.7 Semigroups of matrices over a semiring

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.

7.7-1 FullTropicalMaxPlusMonoid

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

7.7-2 FullTropicalMinPlusMonoid

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

7.8 Examples in various representations

In this section, we describe the functions in Semigroups that can be used to create standard semigroups in various representations. For all of these examples, the default representation is as a semigroup of transformations. In general, these functions do not return a representation of minimal degree.

7.8-1 TrivialSemigroup

Returns: A trivial semigroup.

A trivial semigroup is a semigroup with precisely one element. This function returns a trivial semigroup in the representation given by the filter filter, and (if possible) with the degree of the representation given by the non-negative integer deg.

The optional argument filt may be one of the following:

• IsTransformationSemigroup (the default, if filt is not specified),

• IsPartialPermSemigroup,

• IsBipartitionSemigroup,

• IsBlockBijectionSemigroup,

• IsPBRSemigroup,

• IsBooleanMatSemigroup.

If the optional argument deg is not specified, then the smallest possible degree will be used.

gap> S := TrivialSemigroup();
<trivial transformation group of degree 0 with 1 generator>
gap> Size(S);
1
gap> S := TrivialSemigroup(3);
<trivial transformation group of degree 3 with 1 generator>
gap> S := TrivialSemigroup(IsBipartitionSemigroup, 2);
<trivial block bijection group of degree 2 with 1 generator>
gap> Elements(S);
[ <block bijection: [ 1, 2, -1, -2 ]> ]

7.8-2 MonogenicSemigroup

Returns: A monogenic semigroup with index m and period r.

If m and r are positive integers, then this function returns a monogenic semigroup S with index m and period r in the representation given by the filter filt.

The optional argument filt may be one of the following:

• IsTransformationSemigroup (the default, if filt is not specified),

• IsPartialPermSemigroup,

• IsBipartitionSemigroup,

• IsBlockBijectionSemigroup,

• IsPBRSemigroup,

• IsBooleanMatSemigroup.

The semigroup S is generated by a single element, \(f\). S consists of the elements \(f, f ^ {2}, \ldots, f ^ {m}, \ldots, f ^ {m + r - 1}\). The minimal ideal of S consists of the elements \(f ^ {m}, \ldots, f ^ {m + r - 1}\) and is isomorphic to the cyclic group of order \(r\).

See IsMonogenicSemigroup (12.1-11) for more information about monogenic semigroups.

gap> S := MonogenicSemigroup(5, 3);
<commutative non-regular transformation semigroup of size 7, degree 8
 with 1 generator>
gap> IsMonogenicSemigroup(S);
true
gap> I := MinimalIdeal(S);;
gap> IsGroupAsSemigroup(I);
true
gap> StructureDescription(I);
"C3"
gap> S := MonogenicSemigroup(IsBlockBijectionSemigroup, 9, 1);
<commutative non-regular block bijection semigroup of size 9,
 degree 10 with 1 generator>

7.8-3 RectangularBand

Returns: An m by n rectangular band.

If m and n are positive integers, then this function returns a semigroup isomorphic to an m by n rectangular band, in the representation given by the filter filt.

The optional argument filt may be one of the following:

• IsTransformationSemigroup (the default, if filt is not specified),

• IsBipartitionSemigroup,

• IsPBRSemigroup,

• IsBooleanMatSemigroup,

• IsReesMatrixSemigroup.

See IsRectangularBand (12.1-15) for more information about rectangular bands.

gap> T := RectangularBand(5, 6);
<regular transformation semigroup of size 30, degree 10 with 6
 generators>
gap> IsRectangularBand(T);
true
gap> S := RectangularBand(IsReesMatrixSemigroup, 4, 8);
<Rees matrix semigroup 4x8 over Group(())>
gap> IsRectangularBand(S);
true
gap> IsCompletelySimpleSemigroup(S) and IsHTrivial(S);
true

7.8-4 FreeSemilattice

Returns: A free semilattice with n generators.

If n is a positive integer, then this function returns a free semilattice with n generators in the representation given by the filter filt. The optional argument filt may be one of the following:

• IsTransformationSemigroup (the default, if filt is not specified),

• IsTransformationMonoid,

• IsPartialPermSemigroup,

• IsPartialPermMonoid,

• IsFpSemigroup,

• IsFpMonoid,

• IsBipartitionSemigroup,

• IsBipartitionMonoid,

• IsPBRSemigroup,

• IsPBRMonoid,

• IsBooleanMatSemigroup,

• IsBooleanMatMonoid,

• IsNTPMatrixSemigroup,

• IsNTPMatrixMonoid,

• IsMaxPlusMatrixSemigroup,

• IsMaxPlusMatrixMonoid,

• IsMinPlusMatrixSemigroup,

• IsMinPlusMatrixMonoid,

• IsTropicalMaxPlusMatrixSemigroup,

• IsTropicalMaxPlusMatrixMonoid,

• IsTropicalMinPlusMatrixSemigroup,

• IsTropicalMinPlusMatrixMonoid,

• IsProjectiveMaxPlusMatrixSemigroup,

• IsProjectiveMaxPlusMatrixMonoid,

• IsIntegerMatrixSemigroup.

• IsIntegerMatrixMonoid.

gap> S := FreeSemilattice(IsTransformationSemigroup, 5);
<inverse transformation semigroup of size 31, degree 6 with 5 
 generators>
gap> T := FreeSemilattice(IsPartialPermSemigroup, 3);
<inverse partial perm semigroup of size 7, rank 3 with 3 generators>
gap> U := FreeSemilattice(IsBooleanMatSemigroup, 4);
<inverse semigroup of size 15, 5x5 boolean matrices with 4 generators>

7.8-5 ZeroSemigroup

Returns: A zero semigroup of order n.

If n is a positive integer, then this function returns a zero semigroup of order n in the representation given by the filter filt.

The optional argument filt may be one of the following:

• IsTransformationSemigroup (the default, if filt is not specified),

• IsPartialPermSemigroup,

• IsBipartitionSemigroup,

• IsBlockBijectionSemigroup,

• IsPBRSemigroup,

• IsBooleanMatSemigroup,

• IsReesZeroMatrixSemigroup (provided that n > 1).

See IsZeroSemigroup (12.1-27) for more information about zero semigroups.

gap> S := ZeroSemigroup(5);
<commutative non-regular transformation semigroup of size 5, degree 5
 with 4 generators>
gap> IsZeroSemigroup(S);
true
gap> S := ZeroSemigroup(IsPartialPermSemigroup, 15);
<commutative non-regular partial perm semigroup of size 15, rank 14
 with 14 generators>
gap> Size(S);
15
gap> z := MultiplicativeZero(S);
<empty partial perm>
gap> IsZeroSemigroup(S);
true
gap> ForAll(S, x -> ForAll(S, y -> x * y = z));
true

7.8-6 LeftZeroSemigroup

Returns: A left zero (or right zero) semigroup of order n.

If n is a positive integer, then this function returns a left zero (or right zero, as appropriate) semigroup of order n in the representation given by the filter filt. If filt is not specified then the default representation is IsTransformationSemigroup.

The function LeftZeroSemigroup([filt,] n) simply calls RectangularBand([filt,] n, 1) and the function RightZeroSemigroup([filt,] n) simply calls RectangularBand([filt,] 1, n).

For more information about RectangularBand, including its permitted values of filt, see RectangularBand (7.8-3). See IsLeftZeroSemigroup (12.1-10) and IsRightZeroSemigroup (12.1-18) for more information about left zero and right zero semigroups.

gap> S := LeftZeroSemigroup(20);
<transformation semigroup of degree 6 with 20 generators>
gap> IsLeftZeroSemigroup(S);
true
gap> ForAll(Tuples(S, 2), p -> p[1] * p[2] = p[1]);
true
gap> S := RightZeroSemigroup(IsBipartitionSemigroup, 5);
<regular bipartition semigroup of size 5, degree 3 with 5 generators>
gap> IsRightZeroSemigroup(S);
true

7.8-7 BrandtSemigroup

Returns: An n by n Brandt semigroup over the group G.

If n is a positive integer, then this function returns an n by n Brandt semigroup over the group G in the representation given by the filter filt.

The optional argument filt can be any of the following:

• IsPartialPermSemigroup (the default, if filt is not specified),

• IsReesZeroMatrixSemigroup,

• IsTransformationSemigroup,

• IsBipartitionSemigroup,

• IsPBRSemigroup,

• IsBooleanMatSemigroup,

• IsNTPMatrixSemigroup,

• IsMaxPlusMatrixSemigroup,

• IsMinPlusMatrixSemigroup,

• IsTropicalMaxPlusMatrixSemigroup,

• IsTropicalMinPlusMatrixSemigroup,

• IsProjectiveMaxPlusMatrixSemigroup,

• IsIntegerMatrixSemigroup.

The optional argument G defaults to a trivial permutation group. If present G must be a permutation group, unless filt is IsReesZeroMatrixSemigroup when G may be any type of finite group.

See IsBrandtSemigroup (12.2-2) for more information about Brandt semigroups.

gap> S := BrandtSemigroup(5);
<0-simple inverse partial perm semigroup of rank 5 with 4 generators>
gap> IsBrandtSemigroup(S);
true
gap> S := BrandtSemigroup(IsTransformationSemigroup, 15);
<0-simple transformation semigroup of degree 16 with 28 generators>
gap> Size(S);
226
gap> MultiplicativeZero(S);
Transformation( [ 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16,
  16, 16, 16 ] )
gap> S := BrandtSemigroup(Group((1, 2)), 3);
<0-simple inverse partial perm semigroup of rank 6 with 3 generators>
gap> S := BrandtSemigroup(IsTransformationSemigroup, Group((1, 2)), 3);
<0-simple transformation semigroup of degree 7 with 5 generators>
gap> S := BrandtSemigroup(IsReesZeroMatrixSemigroup,
>                         DihedralGroup(4),
>                         2);
<Rees 0-matrix semigroup 2x2 over <pc group of size 4 with
 2 generators>>

7.9 Free bands

This chapter describes the functions in Semigroups for dealing with free bands. This part of the manual and the functions described herein were originally written by Julius Jonušas, with later additions by Reinis Cirpons, Tom Conti-Leslie, and Murray Whyte

A semigroup \(B\) is a free band on a non-empty set \(X\) if \(B\) is a band with a map \( f \) from \( B \) to \(X\) such that for every band \( S \) and every map \( g \) from \(X\) to \( B \) there exists a unique homomorphism \( g'\) from \(B\) to \(S\) such that \(fg' = g\). The free band on a set \(X\) is unique up to isomorphism. Moreover, by the universal property, every band can be expressed as a quotient of a free band.

For an alternative description of a free band. Suppose that \( X \) is a non-empty set and \( X ^ + \) a free semigroup on \( X \). Also suppose that \( b \) is the smallest congurance on \( X ^ + \) containing the set

\[ \{(w ^ 2, w) : w \in X ^ + \}. \]

Then the free band on \( X \) is isomorphic to the quotient of \( X ^ + \) by \( b \). See Section 4.5 of [How95] for more information on free bands.

7.9-1 FreeBand

Returns: A free band.

Returns a free band on rank generators, for a positive integer rank. If rank is not specified, the number of names is used. The resulting semigroup is always finite.

gap> FreeBand(6);
<free band on the generators [ x1, x2, x3, x4, x5, x6 ]>
gap> FreeBand(6, "b");
<free band on the generators [ b1, b2, b3, b4, b5, b6 ]>
gap> FreeBand("a", "b", "c");
<free band on the generators [ a, b, c ]>
gap> FreeBand("a", "b", "c");
<free band on the generators [ a, b, c ]>
gap> S := FreeBand(["a", "b", "c"]);
<free band on the generators [ a, b, c ]>
gap> Size(S);
159
gap> gens := Generators(S);
[ a, b, c ]
gap> S.1 * S.2;
ab

7.9-2 IsFreeBandCategory

IsFreeBandCategory is the category of semigroups created using FreeBand (7.9-1).

gap> IsFreeBandCategory(FreeBand(3));
true
gap> IsFreeBand(SymmetricGroup(6));
false

7.9-3 IsFreeBand

Returns: true or false.

IsFreeBand returns true if the given semigroup S is a free band.

gap> IsFreeBand(FreeBand(3));
true
gap> IsFreeBand(SymmetricGroup(6));
false
gap> IsFreeBand(FullTransformationMonoid(7));
false

7.9-4 IsFreeBandElement

IsFreeBandElement is a Category containing the elements of a free band.

gap> IsFreeBandElement(Generators(FreeBand(4))[1]);
true
gap> IsFreeBandElement(Transformation([1, 3, 4, 1]));
false
gap> IsFreeBandElement((1, 2, 3, 4));
false

7.9-5 IsFreeBandElementCollection

Every collection of elements of a free band belongs to the category IsFreeBandElementCollection. For example, every free band belongs to IsFreeBandElementCollection.

7.9-6 IsFreeBandSubsemigroup

IsFreeBandSubsemigroup is a synonym for IsSemigroup and IsFreeBandElementCollection.

gap> S := FreeBand(2);
<free band on the generators [ x1, x2 ]>
gap> x := S.1;
x1
gap> y := S.2;
x2
gap> new := Semigroup([x * y, x]);
<semigroup with 2 generators>
gap> IsFreeBand(new);
false
gap> IsFreeBandSubsemigroup(new);
true

7.9-7 ContentOfFreeBandElement

Returns: A list of integers

The content of a free band element x is the set of generators appearing in the word representing the element x of the free band.

The function ContentOfFreeBandElement returns the content of free band element x represented as a list of integers, where 1 represents the first generator, 2 the second generator, and so on.

The function ContentOfFreeBandElementCollection returns the the least list C for the collection of free band elements coll such that the content of every element in coll is contained in C.

gap> S := FreeBand(2);
<free band on the generators [ x1, x2 ]>
gap> x := S.1;
x1
gap> y := S.2;
x2
gap> ContentOfFreeBandElement(x);
[ 1 ]
gap> ContentOfFreeBandElement(x * y);
[ 1, 2 ]
gap> ContentOfFreeBandElement(x * y * x);
[ 1, 2 ]
gap> ContentOfFreeBandElementCollection([x, y]);
[ 1, 2 ]

7.9-8 EqualInFreeBand

This operation takes a pair u and v of lists of positive integers or strings, representing words in a free semigroup.

Where F is a free band over some alphabet containing the letters occurring in u and v, this operation returns true if u and v are equal in F, and false otherwise.

Note that this operation is for lists and strings, as opposed to FreeBandElement objects.

This is an implementation of an algorithm described by Jakub Radoszewski and Wojciech Rytter in [RR10].

gap> EqualInFreeBand("aa", "a");
true
gap> EqualInFreeBand("abcacba", "abcba");
true
gap> EqualInFreeBand("aab", "aac");
false
gap> EqualInFreeBand([1, 3, 3], [2]);
false

7.9-9 GreensDClassOfElement

Returns: A Green's \(\mathscr{D}\)-class

Let S be a free band. Two elements of S are \(\mathscr{D}\)-related if and only if they have the same content i.e. the set of generators appearing in any factorization of the elements. Therefore, a \(\mathscr{D}\)-class of a free band element x is the set of elements of S which have the same content as x .

gap> S := FreeBand(3, "b");
<free band on the generators [ b1, b2, b3 ]>
gap> x := S.1 * S.2;
b1b2
gap> D := GreensDClassOfElement(S, x);
<Green's D-class: b1b2>
gap> IsGreensDClass(D);
true

7.9-10 Operators

The following operators are also included for free band elements:

u * v

returns the product of two free band elements u and v.

u = v

checks if two free band elements are equal.

u < v

compares the sizes of the internal representations of two free band elements.

7.10 Graph inverse semigroups

In this chapter we describe a class of semigroups arising from directed graphs.

The functionality in Semigroups for graph inverse semigroups was written jointly by Zak Mesyan (UCCS) and J. D. Mitchell (St Andrews). The functionality for graph inverse semigroup congruences was written by Marina Anagnostopoulou-Merkouri (St Andrews).

7.10-1 GraphInverseSemigroup

Returns: A graph inverse semigroup.

If E is a digraph (i.e. it satisfies IsDigraph (Digraphs: IsDigraph)), then GraphInverseSemigroup returns the graph inverse semigroup \(G(\textit{E})\) where, roughly speaking, elements correspond to paths in the graph E.

Let us describe E as a digraph \(\textit{E} = (E ^ 0, E ^ 1, r, s)\), where \(E^0\) is the set of vertices, \(E^1\) is the set of edges, and \(r\) and \(s\) are functions \(E^1 \to E^0\) giving the range and source of an edge, respectively. The graph inverse semigroup \(G(\textit{E})\) of \(E\) is the semigroup-with-zero generated by the sets \(\textit{E} ^ 0\) and \(\textit{E} ^ 1\), together with a set of variables \(\{e ^ {-1} \mid e \in \textit{E} ^ 1\}\), satisfying the following relations for all \(v, w \in \textit{E} ^ 0\) and \(e, f \in \textit{E} ^ 1\):

(V)

\(vw = \delta_{v,w} \cdot v\),

(E1)

\(s(e) \cdot e=e \cdot r(e)=e\),

(E2)

\(r(e) \cdot e^{-1} = e^{-1} \cdot s(e) =e^{-1}\),

(CK1)

\(e^{-1} \cdot f = \delta_{e,f} \cdot r(e)\).

(Here \(\delta\) is the Kronecker delta.) We define \(v^{-1}=v\) for each \(v \in E^0\), and for any path \(y=e_1\dots e_n\) (\(e_1\dots e_n \in E^1\)) we let \(y^{-1} = e_n^{-1} \dots e_1^{-1}\). With this notation, every nonzero element of \(G(E)\) can be written uniquely as \(xy^{-1}\) for some paths \(x, y\) in \(E\), by the CK1 relation.

For a more complete description, see [MM16].

gap> gr := Digraph([[2, 5, 8, 10], [2, 3, 4, 5, 6, 8, 9, 10], [1],
>                   [3, 5, 7, 8, 10], [2, 5, 7], [3, 6, 7, 9, 10],
>                   [1, 4], [1, 5, 9], [1, 2, 7, 8], [3, 5]]);
<immutable digraph with 10 vertices, 37 edges>
gap> S := GraphInverseSemigroup(gr);
<infinite graph inverse semigroup with 10 vertices, 37 edges>
gap> GeneratorsOfInverseSemigroup(S);
[ e_1, e_2, e_3, e_4, e_5, e_6, e_7, e_8, e_9, e_10, e_11, e_12,
  e_13, e_14, e_15, e_16, e_17, e_18, e_19, e_20, e_21, e_22, e_23,
  e_24, e_25, e_26, e_27, e_28, e_29, e_30, e_31, e_32, e_33, e_34,
  e_35, e_36, e_37, v_1, v_2, v_3, v_4, v_5, v_6, v_7, v_8, v_9, v_10
 ]
gap> AssignGeneratorVariables(S);
gap> e_1 * e_1 ^ -1;
e_1e_1^-1
gap> e_1 ^ -1 * e_1 ^ -1;
0
gap> e_1 ^ -1 * e_1;
v_2

7.10-2 Range

Returns: A graph inverse semigroup element.

If x is an element of a graph inverse semigroup (i.e. it satisfies IsGraphInverseSemigroupElement (7.10-4)), then Range and Source give, respectively, the start and end vertices of x when viewed as a path in the digraph over which the semigroup is defined.

For a fuller description, see GraphInverseSemigroup (7.10-1).

gap> gr := Digraph([[], [1], [3]]);;
gap> S := GraphInverseSemigroup(gr);;
gap> e := S.1;
e_1
gap> Source(e);
v_2
gap> Range(e);
v_1

7.10-3 IsVertex

Returns: true or false.

If x is an element of a graph inverse semigroup (i.e. it satisfies IsGraphInverseSemigroupElement (7.10-4)), then this attribute returns true if x corresponds to a vertex in the digraph over which the semigroup is defined, and false otherwise.

For a fuller description, see GraphInverseSemigroup (7.10-1).

gap> gr := Digraph([[], [1], [3]]);;
gap> S := GraphInverseSemigroup(gr);;
gap> e := S.1;
e_1
gap> IsVertex(e);
false
gap> v := S.3;
v_1
gap> IsVertex(v);
true
gap> z := v * e;
0
gap> IsVertex(z);
false

7.10-4 IsGraphInverseSemigroup

Returns: true or false.

The category IsGraphInverseSemigroup contains any semigroup defined over a digraph using the GraphInverseSemigroup (7.10-1) operation. The category IsGraphInverseSemigroupElement contains any element contained in such a semigroup.

gap> gr := Digraph([[], [1], [3]]);;
gap> S := GraphInverseSemigroup(gr);
<infinite graph inverse semigroup with 3 vertices, 2 edges>
gap> IsGraphInverseSemigroup(S);
true
gap> x := GeneratorsOfSemigroup(S)[1];
e_1
gap> IsGraphInverseSemigroupElement(x);
true

7.10-5 GraphOfGraphInverseSemigroup

Returns: A digraph.

If S is a graph inverse semigroup (i.e. it satisfies IsGraphInverseSemigroup (7.10-4)), then this attribute returns the original digraph over which S was defined (most likely the argument given to GraphInverseSemigroup (7.10-1) to create S).

gap> gr := Digraph([[], [1], [3]]);
<immutable digraph with 3 vertices, 2 edges>
gap> S := GraphInverseSemigroup(gr);;
gap> GraphOfGraphInverseSemigroup(S);
<immutable digraph with 3 vertices, 2 edges>

7.10-6 IsGraphInverseSemigroupElementCollection

Every collection of elements of a graph inverse semigroup belongs to the category IsGraphInverseSemigroupElementCollection. For example, every graph inverse semigroup belongs to IsGraphInverseSemigroupElementCollection.

7.10-7 IsGraphInverseSubsemigroup

IsGraphInverseSubsemigroup is a synonym for IsSemigroup and IsInverseSemigroup and IsGraphInverseSemigroupElementCollection.

See IsGraphInverseSemigroupElementCollection (7.10-6) and IsInverseSemigroup (Reference: IsInverseSemigroup).

gap> gr := Digraph([[], [1], [2]]);
<immutable digraph with 3 vertices, 2 edges>
gap> S := GraphInverseSemigroup(gr);
<finite graph inverse semigroup with 3 vertices, 2 edges>
gap> Elements(S);
[ e_2^-1, e_1^-1, e_1^-1e_2^-1, 0, e_1, e_1e_1^-1, e_1e_1^-1e_2^-1,
  e_2, e_2e_2^-1, e_2e_1, e_2e_1e_1^-1, e_2e_1e_1^-1e_2^-1, v_1, v_2,
  v_3 ]
gap> T := InverseSemigroup(Elements(S){[3, 5]});;
gap> IsGraphInverseSubsemigroup(T);
true

7.10-8 VerticesOfGraphInverseSemigroup

Returns: A list.

If S is a graph inverse semigroup (i.e. it satisfies IsGraphInverseSemigroup (7.10-4)), then this attribute returns the list of vertices of S.

gap> D := Digraph([[3, 4], [3, 4], [4], []]);
<immutable digraph with 4 vertices, 5 edges>
gap> S := GraphInverseSemigroup(D);
<finite graph inverse semigroup with 4 vertices, 5 edges>
gap> VerticesOfGraphInverseSemigroup(S);
[ v_1, v_2, v_3, v_4 ]
gap> D := ChainDigraph(12);
<immutable chain digraph with 12 vertices>
gap> S := GraphInverseSemigroup(D);
<finite graph inverse semigroup with 12 vertices, 11 edges>
gap> VerticesOfGraphInverseSemigroup(S);
[ v_1, v_2, v_3, v_4, v_5, v_6, v_7, v_8, v_9, v_10, v_11, v_12 ]

7.10-9 IndexOfVertexOfGraphInverseSemigroup

Returns: A positive integer.

If v is a vertex of a graph inverse semigroup (i.e. it satisfies IsGraphInverseSemigroup (7.10-4)), then this attribute returns the index of this vertex in S.

gap> D := Digraph([[3, 4], [3, 4], [4], []]);
<immutable digraph with 4 vertices, 5 edges>
gap> S := GraphInverseSemigroup(D);
<finite graph inverse semigroup with 4 vertices, 5 edges>
gap> IndexOfVertexOfGraphInverseSemigroup(v_1);
1
gap> IndexOfVertexOfGraphInverseSemigroup(v_3);
3

7.11 Free inverse semigroups

This chapter describes the functions in Semigroups for dealing with free inverse semigroups. This part of the manual and the functions described herein were written by Julius Jonušas.

An inverse semigroup \(F\) is said to be free on a non-empty set \(X\) if there is a map \(f\) from \(F\) to \(X\) such that for every inverse semigroup \(S\) and a map \(g\) from \(X\) to \(S\) there exists a unique homomorphism \(g'\) from \(F\) to \(S\) such that \(fg' = g\). Moreover, by this universal property, every inverse semigroup can be expressed as a quotient of a free inverse semigroup.

The internal representation of an element of a free inverse semigroup uses a Munn tree. A Munn tree is a directed tree with distinguished start and terminal vertices and where the edges are labeled by generators so that two edges labeled by the same generator are only incident to the same vertex if one of the edges is coming in and the other is leaving the vertex. For more information regarding free inverse semigroups and the Munn representations see Section 5.10 of [How95].

See also Reference: Inverse semigroups and monoids, Reference: Partial permutations and Reference: Free Groups, Monoids and Semigroups.

An element of a free inverse semigroup in Semigroups is displayed, by default, as a shortest word corresponding to the element. However, there might be more than one word of the minimum length. For example, if \(x\) and \(y\) are generators of a free inverse semigroups, then

\[xyy ^ {-1}xx ^ {-1}x ^ {-1} = xxx ^ {-1}yy ^ {-1}x ^ {-1}.\]

See MinimalWord (7.11-7). Therefore we provide a another method for printing elements of a free inverse semigroup: a unique canonical form. Suppose an element of a free inverse semigroup is given as a Munn tree. Let \(L\) be the set of words corresponding to the shortest paths from the start vertex to the leaves of the tree. Also let \(w\) be the word corresponding to the shortest path from the start vertex to the terminal vertex. The word \(vv ^ {-1}\) is an idempotent for every \(v\) in \(L\). The canonical form is given by multiplying these idempotents, in shortlex order, and then postmultiplying by \(w\). For example, consider the word \(xyy ^ {-1}xx ^ {-1}x ^ {-1}\) again. The words corresponding to the paths to the leaves are in this case \(xx\) and \(xy\). And \(w\) is an empty word since start and terminal vertices are the same. Therefore, the canonical form is

\[xxx ^ {-1}x ^ {-1}xyy ^ {-1}x ^ {-1}.\]

See CanonicalForm (7.11-6).

7.11-1 FreeInverseSemigroup

Returns: A free inverse semigroup.

Returns a free inverse semigroup on rank generators, where rank is a positive integer. If rank is not specified, the number of names is used. If S is a free inverse semigroup, then the generators can be accessed by S.1, S.2 and so on.

gap> S := FreeInverseSemigroup(7);
<free inverse semigroup on the generators
[ x1, x2, x3, x4, x5, x6, x7 ]>
gap> S := FreeInverseSemigroup(7, "s");
<free inverse semigroup on the generators
[ s1, s2, s3, s4, s5, s6, s7 ]>
gap> S := FreeInverseSemigroup("a", "b", "c");
<free inverse semigroup on the generators [ a, b, c ]>
gap> S := FreeInverseSemigroup(["a", "b", "c"]);
<free inverse semigroup on the generators [ a, b, c ]>
gap> S.1;
a
gap> S.2;
b

7.11-2 IsFreeInverseSemigroupCategory

Every free inverse semigroup in GAP created by FreeInverseSemigroup (7.11-1) belongs to the category IsFreeInverseSemigroup. Basic operations for a free inverse semigroup are: GeneratorsOfInverseSemigroup (Reference: GeneratorsOfInverseSemigroup) and GeneratorsOfSemigroup (Reference: GeneratorsOfSemigroup). Elements of a free inverse semigroup belong to the category IsFreeInverseSemigroupElement (7.11-4).

7.11-3 IsFreeInverseSemigroup

Returns: true or false

Attempts to determine whether the given semigroup S is a free inverse semigroup.

7.11-4 IsFreeInverseSemigroupElement

Every element of a free inverse semigroup belongs to the category IsFreeInverseSemigroupElement.

7.11-5 IsFreeInverseSemigroupElementCollection

Every collection of elements of a free inverse semigroup belongs to the category IsFreeInverseSemigroupElementCollection. For example, every free inverse semigroup belongs to IsFreeInverseSemigroupElementCollection.

7.11-6 CanonicalForm

Returns: A string.

Every element of a free inverse semigroup has a unique canonical form. If w is such an element, then CanonicalForm returns the canonical form of w as a string.

gap> S := FreeInverseSemigroup(3);
<free inverse semigroup on the generators [ x1, x2, x3 ]>
gap> x := S.1; y := S.2;
x1
x2
gap> CanonicalForm(x ^ 3 * y ^ 3);
"x1x1x1x2x2x2x2^-1x2^-1x2^-1x1^-1x1^-1x1^-1x1x1x1x2x2x2"

7.11-7 MinimalWord

Returns: A string.

For an element w of a free inverse semigroup S, MinimalWord returns a word of minimal length equal to w in S as a string.

Note that there maybe more than one word of minimal length which is equal to w in S.

gap> S := FreeInverseSemigroup(3);
<free inverse semigroup on the generators [ x1, x2, x3 ]>
gap> x := S.1;
x1
gap> y := S.2;
x2
gap> MinimalWord(x ^ 3 * y ^ 3);
"x1*x1*x1*x2*x2*x2"

7.11-8 Displaying free inverse semigroup elements

There is a way to change how GAP displays free inverse semigroup elements using the user preference FreeInverseSemigroupElementDisplay. See UserPreference (Reference: UserPreference) for more information about user preferences.

There are two possible values for FreeInverseSemigroupElementDisplay:

minimal

With this option selected, GAP will display a shortest word corresponding to the free inverse semigroup element. However, this shortest word is not unique. This is a default setting.

canonical

With this option selected, GAP will display a free inverse semigroup element in the canonical form.

gap> SetUserPreference("semigroups",
>                      "FreeInverseSemigroupElementDisplay",
>                      "minimal");
gap> S := FreeInverseSemigroup(2);
<free inverse semigroup on the generators [ x1, x2 ]>
gap> S.1 * S.2;
x1*x2
gap> SetUserPreference("semigroups",
>                      "FreeInverseSemigroupElementDisplay",
>                      "canonical");
gap> S.1 * S.2;
x1x2x2^-1x1^-1x1x2

7.11-9 Operators for free inverse semigroup elements

w ^ -1

returns the semigroup inverse of the free inverse semigroup element w.

u * v

returns the product of two free inverse semigroup elements u and v.

u = v

checks if two free inverse semigroup elements are equal, by comparing their canonical forms.

generated by GAPDoc2HTML