Skip to content

Semigroups and monoids defined by generators

This section provides information about how to use the Semigroups package for GAP to compute with a semigroup or monoid defined by a collection of generators. We assume some basic familiarity with the GAP programming language, see the GAP: First Steps section for a basic overview if you do not yet feel comfortable with GAP.

All code examples in this section assume that the Semigroups package is loaded. To do so, simply add 

LoadPackage("Semigroups");
at the start of your gap script, or execute this command at the start of your GAP session.

If Semigroups fails to load

If you encounter an error when loading the Semigroups package, it may be due to the kernel module (the C++ component powering Semigroups) not being compiled. Execute the command SetInfoLevel(InfoPackageLoading, 4); and attempt to load the package again. If you see an error similar to the following: 

gap> SetInfoLevel(InfoPackageLoading, 4);
gap> LoadPackage("Semigroups");
#I  Semigroups: entering LoadPackage 
#I  Semigroups: PackageAvailabilityInfo for version 5.5.4
#I  Semigroups: the kernel module is not compiled, 
#I              the package cannot be loaded.
#I  Semigroups: PackageAvailabilityInfo: the AvailabilityTest function returned false
#I  Semigroups: PackageAvailabilityInfo: no installed version fits
#I  Semigroups: return from LoadPackage, package is not available
fail
This is an indication that you need to compile the kernel module. Please follow Step 7 of the Standard Install instructions to fix this error.

Kinds of elements

Any GAP object equipped with an associative multiplication can in principle be used to construct a semigroup in GAP. However, there are certain kinds of semigroups for which there exist the algorithms that are several orders of magnitude faster than those applicable in the general case. In particular, the Semigroups package implements efficient algorithms for the so called acting semigroups1 and has an efficient implementation of the Froidure-Pin algorithm2 which can be applied to subsemigroups of certain semigroups.

In this section we give a brief description of the main types of elements which can be efficiently computed with via the Semigroups package. See Chapter 6 of the Semigroups package documentation for more details.

Transformations

Recall that a transformation of degree \(n\) is a function \(f: \{1, \ldots, n\} \rightarrow \{1, \ldots, n\}\). In GAP we can construct a transformation using the Transformation function. One way of constructing a transformation \(t\) is to provide a list A such that the \(i\)-th entry A[i] is the image of the point \(i\) under the transformation \(t\). So, for example t := Transformation([1, 3, 3, 4]); defines the transformation \(t\) such that \(t(1) = 1, t(2) = t(3) = 3\) and \(t(4) = 4\). We can multiply transformations using the usual multiplication operator *. Furthermore, we can obtain the image \(t(x)\) of a point \(x \in \{1, \ldots, 4\}\) under \(t\) via the power syntax x ^ t.

Note

The code examples in this section will consist of two tabs: one labelled "GAP REPL" showcasing the output in an example GAP REPL session, and another labelled "GAP script" which contains the same code without the GAP REPL output, for easier copy-pasting into a GAP session.

gap> a := Transformation([1, 3, 3, 4]);
Transformation( [ 1, 3, 3 ] )
gap> b := Transformation([2, 3, 4, 1]);
Transformation( [ 2, 3, 4, 1 ] )
gap> a * b;
Transformation( [ 2, 4, 4, 1 ] )
gap> b * a;
Transformation( [ 3, 3, 4, 1 ] )
gap> 2 ^ a;
3
gap> 3 ^ b;
4
gap> 2 ^ (a * b);
4
gap> 2 ^ (b * a);
3

a := Transformation([1, 3, 3, 4]);
b := Transformation([2, 3, 4, 1]);
a * b;
b * a;
2 ^ a;
3 ^ b;
2 ^ (a * b);
2 ^ (b * a);

As we discussed in the Help system section, to learn more about any GAP function you can use the help operator ? in the GAP REPL, e.g.

gap> ?Transformation
  53.2-1 Transformation

  ‣ Transformation( list ) ─────────────────────────────────────────── operation
  ‣ Transformation( list, func ) ───────────────────────────────────── operation
  ‣ TransformationList( list ) ─────────────────────────────────────── operation
  Returns:  A transformation.

  TransformationList returns the transformation f such that i ^ f = list[i] if i
  is  between  1  and  the  length of list and i ^ f = i if i is larger than the
  length  of  list.  An  error  will  occur in TransformationList if list is not
  dense, if list contains an element which is not a positive integer, or if list
  contains an integer not in [ 1 .. Length( list ) ].

  TransformationList  is  the  analogue  in  the  context  of transformations of
  PermList  (42.5-2). Transformation is a synonym of TransformationList when the
  argument is a list.

  When  the  arguments are a list of positive integers list and a function func,
  Transformation  returns  the  transformation  f  such that list[i] ^ f = func(
  list[i]  )  if i is in the range [ 1 .. Length( list ) ] and f fixes all other
  points.

  ─────────────────────────────────  Example  ──────────────────────────────────
    gap> SetUserPreference( "NotationForTransformations", "input" );
    gap> f := Transformation( [ 11, 10, 2, 11, 4, 4, 7, 6, 9, 10, 1, 11 ] );
    Transformation( [ 11, 10, 2, 11, 4, 4, 7, 6, 9, 10, 1, 11 ] )
    gap> f := TransformationList( [ 2, 3, 3, 1 ] );
    Transformation( [ 2, 3, 3, 1 ] )
    gap> SetUserPreference( "NotationForTransformations", "fr" );
    gap> f := Transformation( [ 10, 11 ], x -> x ^ 2 );
    <transformation: 1,2,3,4,5,6,7,8,9,100,121>
    gap> SetUserPreference( "NotationForTransformations", "input" );
  ──────────────────────────────────────────────────────────────────────────────

This can be especially helpful for understanding the functions we will use going forward. In particular, the documentation shows us another way of constructing a transformation using a list and a function.

Properties of transformations such as their degree, image, kernel and rank are implemented by the DegreeOfTransformation, ImageSetOfTransformation, KernelOfTransformation, and RankOfTransformation functions respectively.

gap> c := Transformation([2, 3, 4, 1, 1]);
Transformation( [ 2, 3, 4, 1, 1 ] )
gap> DegreeOfTransformation(c);
5
gap> ImageSetOfTransformation(c);
[ 1, 2, 3, 4 ]
gap> KernelOfTransformation(c);
[ [ 1 ], [ 2 ], [ 3 ], [ 4, 5 ] ]
gap> RankOfTransformation(c);
4

c := Transformation([2, 3, 4, 1, 1]);
DegreeOfTransformation(c);
ImageSetOfTransformation(c);
KernelOfTransformation(c);
RankOfTransformation(c);

Note

Mathematically, all transformations in GAP belong to the infinite transformation monoid \(\mathcal{T}_\mathbb{N}\) of transformations \(f: \mathbb{N} \rightarrow \mathbb{N}\). GAP simply treats all points after the largest moved point of a transformation \(t\) as fixed. This means that we can multiply two transformations acting on a different number of points, so e.g. Transformation([2, 1]) * Transformation([3, 3, 4, 5]); is valid. Similarly, 10 ^ (Transformation([2, 1])); is valid and returns 10. The degree of a transformation \(t\), as returned by the DegreeOfTransformation function in GAP, is simply the largest moved point of \(t\), i.e. the largest value \(n \in \mathbb{N}\) such that \(t(n) \neq n\).

Note

GAP does not have a distinguished type for partial transformations of degree \(n\), i.e. partial functions with domain and codomain in \(\{1, \ldots, n\}\). However, for any fixed \(n\), the semigroup of all partial transformations of degree \(n\) is isomorphic to the semigroup of all total transformations of degree \(n+1\), which is what the Semigroups package utilizes. See the documentation of the PartialTransformationMonoid for more details.

Info

See Chapter 53 of the GAP reference manual for more details about transformations.

Partial permutations

Recall that a partial permutation of degree \(n\) is a partial function \(f: \{1, \ldots, n\} \rightarrow \{1, \ldots, n\}\) which is a bijection when restricted to its domain, i.e. the set of points on which it is defined. We can construct a partial permutation using the PartialPerm function in GAP by supplying two lists defining the domain and image of the partial permutation. Partial permutations can be multiplied using *, and the image of a point under a partial permutation can be obtained using the ^ operator. Note that points not in the domain get mapped to 0.

gap> a := PartialPerm([1, 2, 5, 20], [2, 3, 5, 50]);
[1,2,3][20,50](5)
gap> b := PartialPerm([3, 4, 5, 6], [4, 3, 8, 7]);
[5,8][6,7](3,4)
gap> a * b;
[2,4][5,8]
gap> b * a;
<empty partial perm>
gap> 2 ^ a;
3
gap> 4 ^ a;
0

a := PartialPerm([1, 2, 5, 20], [2, 3, 5, 50]);
b := PartialPerm([3, 4, 5, 6], [4, 3, 8, 7]);
a * b;
b * a;
2 ^ a;
4 ^ a;

Partial permutations in GAP are displayed in disjoint cycle and chain notation. Recall that a cycle of a partial permutation \(p\) is a sequence of points \(x_1, \ldots, x_k\) such that

  • \(x_1 \in \text{dom}(p)\),
  • \(p(x_i) = p(x_{i+1})\) for all \(i \in \{1, \ldots, k - 1\}\) and
  • \(p(x_k) = x_1\).

A chain of \(p\) is a sequence of points \(x_1, \ldots, x_k\) such that

  • \(x_1 \in \text{dom}(p) \setminus \text{im}(p)\),
  • \(p(x_i) = p(x_{i+1})\) for all \(i \in \{1, \ldots, k - 1\}\) and
  • \(p(x_k) \in \text{im}(p)\setminus \text{dom}(p)\).

Just as permutations can be written in disjoint cycle notation, partial permutations can be written in disjoint cycle and chain notation. Cycles are displayed using round brackets () and chains using square brackets []. See Section 54.6 of the reference manual for more details.

Warning

A Set in GAP is a strictly sorted list of elements. GAP expects the domain of PartialPerm to be a set, so in particular, this means that giving the elements of the domain of a PartialPerm out of order will result in a GAP error:

gap> PartialPerm([1, 2, 20, 5], [2, 3, 4, 50]); # 5 and 20 need to be swapped
Error, usage: the 1st argument must be a set of positive integers and the 2nd
argument must be a duplicate-free list of positive integers of equal length
to the first
*[1] ErrorNoReturn( "usage: the 1st argument must be a set of positive ", 
"integers and the 2nd argument must be a duplicate-free ", 
"list of positive integers of equal length to the first" );
@ /Users/rcirpons/Desktop/Source/gap/lib/pperm.gi:527
<function "PartialPerm">( <arguments> )
called from read-eval loop at *stdin*:44
type 'quit;' to quit to outer loop
brk>

The image must not contain duplicates (as otherwise the element would not be a partial bijection), but otherwise there is no restriction on the order of elements.

Properties of transformations such as their degree, codegree, domain, image, and rank are implemented by the DegreeOfPartialPerm, CodegreeOfPartialPerm, DomainOfPartialPerm, ImageSetOfPartialPerm and RankOfPartialPerm functions respectively.

gap> c := PartialPerm([1, 2, 5, 20, 22], [2, 3, 5, 50, 6]);
[1,2,3][20,50][22,6](5)
gap> DegreeOfPartialPerm(c);
22
gap> CodegreeOfPartialPerm(c);
50
gap> DomainOfPartialPerm(c);
[ 1, 2, 5, 20, 22 ]
gap> ImageSetOfPartialPerm(c);
[ 2, 3, 5, 6, 50 ]
gap> RankOfPartialPerm(c);
5

c := PartialPerm([1, 2, 5, 20, 22], [2, 3, 5, 50, 6]);
DegreeOfPartialPerm(c);
CodegreeOfPartialPerm(c);
DomainOfPartialPerm(c);
ImageSetOfPartialPerm(c);
RankOfPartialPerm(c);

Note

Similar to transformations, all partial permutation in GAP belong to the infinite symmetric inverse monoid \(\mathcal{I}_\mathbb{N}\) of partial bijections \(f: \mathbb{N} \rightarrow \mathbb{N}\). Hence it is always possible to multiply any pair of partial permutations.

Info

See Chapter 54 of the GAP reference manual for more details about partial permutations.

Bipartitions

Recall that a bipartition of degree \(n\) is a partition of the set \(\{1, \ldots, n\} \cup \{-n, \ldots, -1\}\). The parts of a bipartition \(b\) are called blocks. Bipartitions in GAP can be specified using the Bipartition function by specifying the blocks of the bipartition. Bipartitions can be multiplied using the * operator (see Chapter 3 of the Semigroups manual for a definition of bipartition multiplication). Furthermore, bipartitions admit an involution Star, which swaps all the points \(i\) with \(-i\) in the partition.

gap> a := Bipartition([[1, -1, -2], [2, 5], [3, 4, -3], [-4, -5]]);
<bipartition: [ 1, -1, -2 ], [ 2, 5 ], [ 3, 4, -3 ], [ -4, -5 ]>
gap> b := Bipartition([[1, -4], [2], [3, -1], [4], [5, -3], [-2], [-5]]);
<bipartition: [ 1, -4 ], [ 2 ], [ 3, -1 ], [ 4 ], [ 5, -3 ], [ -2 ], [ -5 ]>
gap> a * b;
<bipartition: [ 1, -4 ], [ 2, 5 ], [ 3, 4, -1 ], [ -2 ], [ -3 ], [ -5 ]>
gap> b * a;
<bipartition: [ 1, 5, -3 ], [ 2 ], [ 3, -1, -2 ], [ 4 ], [ -4, -5 ]>
gap> Star(a);
<bipartition: [ 1, 2, -1 ], [ 3, -3, -4 ], [ 4, 5 ], [ -2, -5 ]>

a := Bipartition([[1, -1, -2], [2, 5], [3, 4, -3], [-4, -5]]);
b := Bipartition([[1, -4], [2], [3, -1], [4], [5, -3], [-2], [-5]]);
a * b;
b * a;
Star(a);

The TikzString function can be used to produce code visualizing the presentation using the Latex package tikz. Provided you have a Latex installation on your computer, the Splash function can be used to display the image this code generates.

gap> TikzString(a);
"%latex\n\\documentclass{minimal}\n\\usepackage{tikz}\n\n\\begin{document}\n\\be\
gin{tikzpicture}\n\n  %block number 1\n  %vertices and labels\n  \\fill(1, 2)cir\
cle(.125);\n  \\draw(0.94999999999999996, 2.2) node [above] {$1$};\n  \\fill(1, \
0)circle(.125);\n  \\draw(1, -0.2) node [below] {$-1$};\n  \\fill(2, 0)circle(.1\
25);\n  \\draw(2, -0.2) node [below] {$-2$};\n\n  %lines\n  \\draw(1, 0.125) .. \
controls (1, 0.59999999999999998) and (2, 0.59999999999999998) .. (2, 0.125);\n \
\\draw(1, 2)--(1, 0);\n\n  %block number 2\n  %vertices and labels\n  \\fill(2,\
2)circle(.125);\n  \\draw(1.95, 2.2) node [above] {$2$};\n  \\fill(5, 2)circle(\
.125);\n  \\draw(4.9500000000000002, 2.2) node [above] {$5$};\n\n  %lines\n  \\d\
raw(2, 1.875) .. controls (2, 1.2) and (5, 1.2) .. (5, 1.875);\n\n  %block numbe\
r 3\n  %vertices and labels\n  \\fill(3, 2)circle(.125);\n  \\draw(2.95000000000\
00002, 2.2) node [above] {$3$};\n  \\fill(4, 2)circle(.125);\n  \\draw(3.9500000\
000000002, 2.2) node [above] {$4$};\n  \\fill(3, 0)circle(.125);\n  \\draw(3, -0\
.2) node [below] {$-3$};\n\n  %lines\n  \\draw(3, 1.875) .. controls (3, 1.39999\
99999999999) and (4, 1.3999999999999999) .. (4, 1.875);\n  \\draw(3, 2)--(3, 0);\
\n\n  %block number 4\n  %vertices and labels\n  \\fill(4, 0)circle(.125);\n  \\\
draw(4, -0.2) node [below] {$-4$};\n  \\fill(5, 0)circle(.125);\n  \\draw(5, -0.\
2) node [below] {$-5$};\n\n  %lines\n  \\draw(4, 0.125) .. controls (4, 0.599999\
99999999998) and (5, 0.59999999999999998) .. (5, 0.125);\n\\end{tikzpicture}\n\n\
\\end{document}"
gap> Splash(TikzString(a));
gap> Splash(TikzString(b));

TikzString(a);
Splash(TikzString(a));
Splash(TikzString(b));

A visualization of the bipartition a A visualization of the bipartition a

A visualization of the bipartition a. Result of the Splash(TikzString(a)) call.

A visualization of the bipartition b A visualization of the bipartition b

A visualization of the bipartition b. Result of the Splash(TikzString(b)) call.

Properties of bipartitions such as their degree, domain, codomain and rank are implemented by the DegreeOfBipartition, DomainOfBipartition, CodomainOfBipartition and RankOfBipartition functions respectively.

gap> c := Bipartition([[1, -1, -2], [2, 5], [3, 4, -3], [-4, -5], [6, -6]]);
<bipartition: [ 1, -1, -2 ], [ 2, 5 ], [ 3, 4, -3 ], [ 6, -6 ], [ -4, -5 ]>
gap> DegreeOfBipartition(c);
6
gap> DomainOfBipartition(c);
[ 1, 3, 4, 6 ]
gap> CodomainOfBipartition(c);
[ -1, -2, -3, -6 ]
gap> RankOfBipartition(c);
3

c := Bipartition([[1, -1, -2], [2, 5], [3, 4, -3], [-4, -5], [6, -6]]);
DegreeOfBipartition(c);
DomainOfBipartition(c);
CodomainOfBipartition(c);
RankOfBipartition(c);

Warning

Unlike transformation and partial permutations, bipartitions of distinct degrees cannot be multiplied together, and attempting to do so at the moment will cause erroneous output. This issue will be resolved in a future release of the Semigroups package, a fix was implemented in Pull request #1185.

Info

See Chapter 3 of the Semigroups manual for more details about bipartitions.

Matrices over semirings

Recall that a semiring is a set \(S\) equipped with two binary operations \(+, \cdot: S\times S\rightarrow S\) such that \((S, +)\) is a commutative monoid, \((S, \cdot)\) is a monoid, and \(S\) satisfies three additional axioms:

  1. For all \(x \in S\), \(0_S \cdot x = x \cdot 0_S = 0_S\), where \(0_S\) is the additive identity of \(S\),
  2. For all \(x, y, z\in S\), \(x \cdot (y + z) = x \cdot y + x \cdot z\) and
  3. For all \(x, y, z\in S\), \((x + y) \cdot z = x \cdot z + y \cdot z\).

The set of \(n\times n\) matrices with entries in \(S\) forms a semigroup under matrix multiplication, i.e. if \(A\) and \(B\) are two \(n\times n\) matrices, then \((A \cdot B)_{i, j} = \sum_{k = 1}^n A_{i, k} \cdot B_{k, j}\).

The semigroups package currently supports efficient manipulation of \(n \times n\) matrices over the following semirings:

  • The integers \(\mathbb{Z}\) under the usual addition and multiplication.
  • The finite fields \(\mathbb{F}_{p^d}\) where \(p\) is a prime and \(d\) is a positive integer.
  • The boolean semiring \(\mathbb{B} = \{\texttt{true}, \texttt{false}\}\) with addition given by the boolean \(\texttt{or}\) function and multiplication by the boolean \(\texttt{and}\) function;
  • The max-plus semiring \(\mathbb{Z} \cup \{-\infty\}\) with operations \(\max\) and \(+\);
  • The min-plus semiring \(\mathbb{Z} \cup \{+\infty\}\) with operations \(\min\) and \(+\);
  • The tropical max-plus and tropical min-plus semirings, which are analogues of the max-plus and min-plus semirings, where the underlying set is replaced with \(\{-\infty, 0, \ldots, t\}\) and \(\{0, \ldots, t, \infty\}\), respectively.
  • The semiring \(\mathbb{N}_{t, p} = \{0, \ldots t+p\}\) with addition and multiplication modulo the relation \(t = t + p\).

In general, an \(n\times n\) matrix \(A\) is represented in GAP as a list of lists A such that A[i] is the \(i\)-th row of \(A\) and A[i][j] is the \(i\)-th row and \(j\)-th column entry of \(A\). Matrices can be multiplied using the * operator, provided they have the same dimensions and same underlying semiring. The * operator can also be used to multiply a matrix by a scalar from the underlying semiring. The ^ -1 operator can be used to find the inverse of a matrix. If A is invertible over the semiring, then A^-1 will return the inverse of A, and otherwise A^-1 will return fail. The transpose of a matrix can be found using the TransposedMat function. Matrices can be pretty-printed using the Display function.

In order to make sure a matrix over the correct semiring is constructed, we must use the correct constructor function. We now briefly cover each type of matrix along with its constructors in turn.

Integers

One can construct an integer matrix \(A\) using the Matrix function by specifying the semiring Integers as the first argument and the list of lists representing A as the second argument.

gap> A := Matrix(Integers, [
> [1, 2, 3],
> [4, 3, -1],
> [1, 0, -3]]);
<3x3-matrix over Integers>
gap> B := Matrix(Integers, [
> [1, -1, 0],
> [0, 0, 1],
> [1, 0, 1]]);
<3x3-matrix over Integers>
gap> C := Matrix(Integers, [
> [0, 0, 0],
> [0, 1, -1],
> [1, 0, 1]]);
<3x3-matrix over Integers>
gap> A * B;
<3x3-matrix over Integers>
gap> B * A;
<3x3-matrix over Integers>
gap> Display(A * B);
<3x3-matrix over Integers:
[[ 4, -1, 5 ]
[ 3, -4, 2 ]
[ -2, -1, -3 ]
]>
gap> Display(B * A);
<3x3-matrix over Integers:
[[ -3, -1, 4 ]
[ 1, 0, -3 ]
[ 2, 2, 0 ]
]>
gap> Display(A * 2);
<3x3-matrix over Integers:
[[ 2, 4, 6 ]
[ 8, 6, -2 ]
[ 2, 0, -6 ]
]>
gap> Display(3 * A);
<3x3-matrix over Integers:
[[ 3, 6, 9 ]
[ 12, 9, -3 ]
[ 3, 0, -9 ]
]>
gap> Display(TransposedMat(A));
<immutable 3x3-matrix over Integers:
[[ 1, 4, 1 ]
[ 2, 3, 0 ]
[ 3, -1, -3 ]
]>
gap> Display(B ^ -1);
<3x3-matrix over Integers:
[[ 0, -1, 1 ]
[ -1, -1, 1 ]
[ 0, 1, 0 ]
]>
gap> C^-1;
fail

A := Matrix(Integers, [
[1, 2, 3],
[4, 3, -1],
[1, 0, -3]]);
B := Matrix(Integers, [
[1, -1, 0],
[0, 0, 1],
[1, 0, 1]]);
C := Matrix(Integers, [
[0, 0, 0],
[0, 1, -1],
[1, 0, 1]]);
A * B;
B * A;
Display(A * B);
Display(B * A);
Display(A * 2);
Display(3 * A);
Display(TransposedMat(A));
Display(B ^ -1);
C^-1;

Warning

If an integer matrix is invertible over the rationals, but not the integers, then the inversion operator ^ -1 will throw an error instead of returning fail at the moment, e.g. 

gap> A := Matrix(Integers, [
> [1, 2, 3],
> [4, 3, -1],
> [1, 0, -3]]);
<3x3-matrix over Integers>
gap> A^-1;
Error, the elements in <list> must lie in <basedomain>
*[1] Error( "the elements in <list> must lie in <basedomain>" );
  @ /Users/rcirpons/Desktop/Source/gap/lib/matobjplist.gi:90
[2] MakeIsPlistVectorRep( v![1], list, true )
  @ /Users/rcirpons/Desktop/Source/gap/lib/matobjplist.gi:319
[3] Vector( list[i], t )
  @ /Users/rcirpons/Desktop/Source/gap/lib/matobjplist.gi:687
[4] Matrix( n, Length( n ), M )
  @ /Users/rcirpons/Desktop/Source/gap/lib/matobjplist.gi:1215
<function "InverseSameMutability [ IsPlistMatrixRep ]">( <arguments> )
called from read-eval loop at *stdin*:160
you can 'quit;' to quit to outer loop, or
you can 'return;' to continue
brk> quit;
This is because the matrix A is invertible over the rationals but not the integers. This issue will be resolved in a future version of GAP, once Pull request #6342 gets merged.

The order of an integer matrix \(A\) is the smallest positive positive integer \(n\) such that \(A^n\) is the identity matrix, if such an integer exists and \(\infty\) otherwise. We can compute the order using the Order function and we can check if the order is finite using the IsTorsion function. Note that only the order of an invertible matrix can be computed, and the Order function will throw an error if a non-invertible matrix is given as input.

gap> D := Matrix(Integers, [
> [0, 0, -1, 0],
> [0, -1, 0, 0],
> [4, 4, 2, -1],
> [1, 1, 0, 3]]);;
gap> Order(D);
infinity
gap> IsTorsion(D);
false
gap> F := Matrix(Integers, [
> [0, 0, -1],
> [0, 1, 0],
> [1, 0, 0]]);;
gap> Order(F);
4
gap> IsTorsion(F);
true
gap> G := Matrix(Integers, [
> [0, 0, 0],
> [0, 1, -1],
> [1, 0, 1]]);
gap> Order(G);
Error, Order: <mat> must be invertible
*[1] Error( "Order: <mat> must be invertible" );
  @ /Users/rcirpons/Desktop/Source/gap/lib/matrix.gi:1169
[2] Order( Unpack( mat ) )
  @ /Users/rcirpons/Desktop/Source/gap/pkg/Semigroups/gap/elements/maxplusmat.g\
i:759
<function "Order for an integer matrix obj">( <arguments> )
called from read-eval loop at *stdin*:172
you can 'quit;' to quit to outer loop, or
you can 'return;' to continue
brk> quit;

D := Matrix(Integers, [
[0, 0, -1, 0],
[0, -1, 0, 0],
[4, 4, 2, -1],
[1, 1, 0, 3]]);;
Order(D);
IsTorsion(D);
F := Matrix(Integers, [
[0, 0, -1],
[0, 1, 0],
[1, 0, 0]]);;
Order(F);
IsTorsion(F);
G := Matrix(Integers, [
[0, 0, 0],
[0, 1, -1],
[1, 0, 1]]);
Order(G);
quit;

Warning

Certain single letter variables such as E, X and Z are defined as functions in GAP, and therefore cannot be modified. Hence attempting to assign to either E, X or Z will result in an error. This is why we skip E in the example above. 

gap> E := Matrix(Integers, [[1, 0], [0, 1]]);
Error, Variable: 'E' is read only
not in any function at *stdin*:201
type 'quit;' to quit to outer loop

Finite fields

Recall that a field is a semiring which is additionally a commutative group under addition and whose non-zero elements form a commutative group under multiplication. A finite field is a field with finitely many elements, and a \(q\) element field exists precisely when \(q = p^d\) for some prime \(p\) and positive integer \(d\). Furthermore all fields with \(q\) elements are isomorphic, and we denote the finite field of order \(q\) by \(\mathbb{F}_q\). In GAP the finite field of order \(q\) can be constructed via the GF function. The Z function returns the generator Z(p^d) of the multiplicative group of the finite field GF(p^d). As such Z(p^d)^0 is the multiplicative identity of GF(p^d).

To construct a matrix \(A\) over a finite field, we use the Matrix function again, specifying the appropriate finite field GF(p^d) as the first argument and a list of lists of elements of GF(p^d) representing A as the second argument.

gap> A := Matrix(GF(3), Z(3)^0 * [[0, 1, 2], [0, 0, 1], [1, 1, 1]]);
[ [ 0*Z(3), Z(3)^0, Z(3) ], [ 0*Z(3), 0*Z(3), Z(3)^0 ], 
  [ Z(3)^0, Z(3)^0, Z(3)^0 ] ]
gap> B := Matrix(GF(3), Z(3)^0 * [[0, 2, 2], [1, 0, 1], [2, 0, 2]]);
[ [ 0*Z(3), Z(3), Z(3) ], [ Z(3)^0, 0*Z(3), Z(3)^0 ], [ Z(3), 0*Z(3), Z(3) ] ]
gap> A^-1;
[ [ Z(3), Z(3)^0, Z(3)^0 ], [ Z(3)^0, Z(3)^0, 0*Z(3) ], 
  [ 0*Z(3), Z(3)^0, 0*Z(3) ] ]
gap> Display(TransposedMat(A));
. . 1
1 . 1
2 1 1
gap> Display(A^-1);
2 1 1
1 1 .
. 1 .
gap> B^-1;
fail
gap> Display(A * B);
2 . 2
2 . 2
. 2 2
gap> Display(B * A);
2 2 1
1 2 .
2 1 .
gap> C := Matrix(GF(3^3), Z(3^3)^0 * [[0, Z(3^3)^2 + 2 * Z(3^3) + 2, 1], [1, 1, 1], [2, 0, 2]]);
[ [ 0*Z(3), Z(3^3)^7, Z(3)^0 ], [ Z(3)^0, Z(3)^0, Z(3)^0 ], 
  [ Z(3), 0*Z(3), Z(3) ] ]
gap> Display(C);
z = Z(27)
.  z^7    1
1    .    1
2    .    2
gap> Display(C^-1);
z = Z(27)
    2  z^7 z^18
    .    1    1
    1 z^20 z^20
gap> Display(C * C);
z = Z(27)
z^18  z^7 z^18
    .  z^4    1
    1 z^20    .

A := Matrix(GF(3), Z(3)^0 * [[0, 1, 2], [0, 0, 1], [1, 1, 1]]);
B := Matrix(GF(3), Z(3)^0 * [[0, 2, 2], [1, 0, 1], [2, 0, 2]]);
A^-1;
Display(TransposedMat(A));
Display(A^-1);
B^-1;
Display(A * B);
Display(B * A);
C := Matrix(GF(3^3), Z(3^3)^0 * [[0, Z(3^3)^2 + 2 * Z(3^3) + 2, 1], [1, 1, 1], [2, 0, 2]]);
Display(C);
Display(C^-1);
Display(C * C);

Warning

At the moment, passing an integer matrix whose entries are not elements of GF(p^d) as the second argument will cause the conversion to a matrix over a semiring to silently fail, e.g. 

gap> A := Matrix(GF(2), [[1, 1, 1], [0, 1, 1], [0, 0, 1]]);
[ [ 1, 1, 1 ], [ 0, 1, 1 ], [ 0, 0, 1 ] ]
gap> A^-1;
[ [ 1, -1, 0 ], [ 0, 1, -1 ], [ 0, 0, 1 ] ]
gap> A[1][1] in GF(2);
false
Instead, the second argument should be multiplied by the multiplicative identity Z(p^d)^0 to prevent this from happening, i.e. 
gap> B := Matrix(GF(2), Z(2)^0 * [[1, 1, 1], [0, 1, 1], [0, 0, 1]]);
<a 3x3 matrix over GF2>
gap> Display(B^-1);
1 1 .
. 1 1
. . 1
gap> B[1][1] in GF(2);
true
This issue will be fixed in a future release of GAP.

Boolean matrices

One can construct a boolean matrix \(A\) using the BooleanMat functions by providing the list of lists representing A. We allow either matrices that contain entries false and true or 0 and 1. The entries false and true get mapped to 0 and 1 respectively.

gap> A := BooleanMat([[true, true, false], [false, false, false], [true, false, true]]);
Matrix(IsBooleanMat, [[1, 1, 0], [0, 0, 0], [1, 0, 1]])
gap> B := BooleanMat([[1, 1, 0], [0, 1, 0], [0, 0, 1]]);
Matrix(IsBooleanMat, [[1, 1, 0], [0, 1, 0], [0, 0, 1]])
gap> A * B;
Matrix(IsBooleanMat, [[1, 1, 0], [0, 0, 0], [1, 1, 1]])
gap> B * A;
Matrix(IsBooleanMat, [[1, 1, 0], [0, 0, 0], [1, 0, 1]])
gap> Display(A);
1 1 0
0 0 0
1 0 1
gap> Display(B);
1 1 0
0 1 0
0 0 1

A := BooleanMat([[true, true, false], [false, false, false], [true, false, true]]);
B := BooleanMat([[1, 1, 0], [0, 1, 0], [0, 0, 1]]);
A * B;
B * A;
Display(A);
Display(B);

A boolean matrix \(A\) of dimension \(n\) can equivalently be viewed as a binary relation \(R\) of the set \(\{1, \ldots, n\}\), where \((i, j) \in R\) if and only if \(A_{i, j} = 1\). The Semigroups package implements functions for checking if a boolean matrix, when viewed as a binary relation in this manner, is reflexive, symmetric, antisymmetric or transitive via the functions IsReflexiveBooleanMat, IsSymmetricBooleanMat, IsAntiSymmetricBooleanMat and IsTransitiveBooleanMat respectively.

gap> C := BooleanMat([
> [1, 1, 1, 0],
> [1, 1, 1, 1],
> [1, 1, 1, 1],
> [0, 1, 1, 1]]);
Matrix(IsBooleanMat, [[1, 1, 1, 0], [1, 1, 1, 1], [1, 1, 1, 1], [0, 1, 1, 1]])
gap> IsReflexiveBooleanMat(C);
true
gap> IsSymmetricBooleanMat(C);
true
gap> IsAntiSymmetricBooleanMat(C);
false
gap> IsTransitiveBooleanMat(C);
false

C := BooleanMat([
[1, 1, 1, 0],
[1, 1, 1, 1],
[1, 1, 1, 1],
[0, 1, 1, 1]]);
IsReflexiveBooleanMat(C);
IsSymmetricBooleanMat(C);
IsAntiSymmetricBooleanMat(C);
IsTransitiveBooleanMat(C);

Max-plus, min-plus and tropical semirings and the \(\mathbb{N}_{t, p}\) semiring

To construct a matrix \(A\) over a max-plus, min-plus, tropical max-plus, tropical min-plus or \(\mathbb{N}_{t, p}\) semiring, we use the Matrix function and specify, respectively,

  • IsMaxPlusSemiring as the first argument and a list of lists A representing the matrix \(A\) as the second argument. The element \(-\infty\) is expressed by the GAP variable -infinity.
  • IsMinPlusSemiring as the first argument and a list of lists A representing the matrix \(A\) as the second argument. The element \(\infty\) is expressed by the GAP variable infinity.
  • IsTropicalMaxPlusSemiring as the first argument, a list of lists A representing the matrix \(A\) as the second argument, and the parameter \(t\) as the third argument.
  • IsTropicalMinPlusSemiring as the first argument, a list of lists A representing the matrix \(A\) as the second argument, and the parameter \(t\) as the third argument.
  • IsNTPMatrix as the first argument, a list of lists A representing the matrix \(A\) as the second argument, and the parameters \(t\) and \(p\) as the third and fourth argument.
gap> Display(Matrix(IsMaxPlusMatrix, [[4, 0, -2], [1, -3, 0], [5, -1, -4]]));
4  0 -2
1 -3  0
5 -1 -4
gap> Display(Matrix(IsMinPlusMatrix, [[-1, infinity], [1, -1]]));
-1  ∞
1 -1
gap> Display(Matrix(IsTropicalMaxPlusMatrix, [[3, 2, 4], [3, 1, 1], [-infinity, 1, 1]], 9));
3  2  4
3  1  1
-∞  1  1
gap> Display(Matrix(IsTropicalMinPlusMatrix, [[1, 1, 1], [0, 3, 0], [1, 1, 3]], 9));
1 1 1
0 3 0
1 1 3
gap> Display(Matrix(IsNTPMatrix, [[0, 0, 0], [2, 0, 1], [2, 2, 2]], 2, 1));
0 0 0
2 0 1
2 2 2

Display(Matrix(IsMaxPlusMatrix, [[4, 0, -2], [1, -3, 0], [5, -1, -4]]));
Display(Matrix(IsMinPlusMatrix, [[-1, infinity], [1, -1]]));
Display(Matrix(IsTropicalMaxPlusMatrix, [[3, 2, 4], [3, 1, 1], [-infinity, 1, 1]], 9));
Display(Matrix(IsTropicalMinPlusMatrix, [[1, 1, 1], [0, 3, 0], [1, 1, 3]], 9));
Display(Matrix(IsNTPMatrix, [[0, 0, 0], [2, 0, 1], [2, 2, 2]], 2, 1));

Some standard matrices and matrix properties

GAP provides implementations of some standard matrix constructions, such as the

We can wrap these in the appropriate constructor from above to construct respectively the identity, zero, a diagonal and a permutation matrix over the appropriate semiring:

gap> Display(Matrix(Integers, IdentityMat(5)));
<5x5-matrix over Integers:
[[ 1, 0, 0, 0, 0 ]
[ 0, 1, 0, 0, 0 ]
[ 0, 0, 1, 0, 0 ]
[ 0, 0, 0, 1, 0 ]
[ 0, 0, 0, 0, 1 ]
]>
gap> Display(BooleanMat(NullMat(6, 6)));
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
gap> Display(Matrix(GF(16), DiagonalMat([Z(16), Z(16)^0, Z(16)^3 + Z(16), 0*Z(16)])));
z = Z(16)
  z^1    .    .    .
    .    1    .    .
    .    .  z^9    .
    .    .    .    .
gap> Display(Matrix(IsMaxPlusMatrix, PermutationMat((1, 3, 2)(5, 4), 6)));
0 0 1 0 0 0
1 0 0 0 0 0
0 1 0 0 0 0
0 0 0 0 1 0
0 0 0 1 0 0
0 0 0 0 0 1

Display(Matrix(Integers, IdentityMat(5)));
Display(BooleanMat(NullMat(6, 6)));
Display(Matrix(GF(16), DiagonalMat([Z(16), Z(16)^0, Z(16)^3 + Z(16), 0*Z(16)])));
Display(Matrix(IsMaxPlusMatrix, PermutationMat((1, 3, 2)(5, 4), 6)));

One can also compute properties of matrices such as the determinant, trace, rank and eigenvalues, to name a few, using the DeterminantMatrix TraceMatrix, RankMatrix and Eigenvalues functions, though not all semirings support all of these functions.

gap> A := Matrix(Integers, [[1, 2, 3], [4, 3, -1], [1, 0, -3]]);
<3x3-matrix over Integers>
gap> B := Matrix(GF(3^3), Z(3^3)^0 * [[0, Z(3^3)^2 + 2 * Z(3^3) + 2, 1], [1, 1, 1], [2, 0, 2]]);
[ [ 0*Z(3), Z(3^3)^7, Z(3)^0 ], [ Z(3)^0, Z(3)^0, Z(3)^0 ], 
  [ Z(3), 0*Z(3), Z(3) ] ]
gap> DeterminantMatrix(A);
4
gap> TraceMatrix(A);
1
gap> RankMatrix(B);
3
gap> # We need to also specify a field over which to find eigenvalues over
gap> Eigenvalues(GF(3^3), B);
[ Z(3^3)^11 ]

A := Matrix(Integers, [[1, 2, 3], [4, 3, -1], [1, 0, -3]]);
B := Matrix(GF(3^3), Z(3^3)^0 * [[0, Z(3^3)^2 + 2 * Z(3^3) + 2, 1], [1, 1, 1], [2, 0, 2]]);
DeterminantMatrix(A);
TraceMatrix(A);
RankMatrix(B);
# We need to also specify a field over which to find eigenvalues over
Eigenvalues(GF(3^3), B);

Info

See Chapter 5 of the Semigroups manual for more details about matrices over semirings, as well as Chapter 24 of the GAP reference manual for more details about general methods for matrices. Note, however that not all methods may be implemented for semigroups over a semiring.

Constructing semigroups

In this section we briefly outline different methods for constructing semigroups using GAP and the Semigroups package. We will occasionally use some functions to showcase properties of these semigroups, such as Size, Elements, IsRegularSemigroup and so on. These functions will be explained in more detail in the Analyzing semigroups section later on.

Built-in semigroups and monoids

GAP and the Semigroups package provide a range of built-in standard semigroups, such as the

  • full transformation semigroup \(\mathcal{T}_n\) consisting of all degree \(n\) transformations via the FullTransformationSemigroup function.
  • symmetric inverse semigroup \(\mathcal{I}_n\) consisting of all degree \(n\) partial permutation via the SymmetricInverseSemigroup function.
  • partition monoid \(\mathcal{P}_n\) consisting of all degree \(n\) bipartitions via the PartitionMonoid function.
  • full matrix monoid of dimension \(n\) over the finite field \(\mathbb{F}_q\) consisting of all \(n\times n\) matrices with entries in \(\mathbb{F}_q\) via the FullMatrixMonoid function.
  • full boolean matrix monoid of dimension \(n\) consisting of all \(n\times n\) boolean matrices via the FullBooleanMatMonoid.

Here we showcase how to construct each semigroup, and then use the Size and IsRegularSemigroup functions to determine its size and whether or not the semigroup is regular:

gap> T := FullTransformationSemigroup(5);
<full transformation monoid of degree 5>
gap> Size(T);
3125
gap> IsRegularSemigroup(T);
true
gap> I := SymmetricInverseSemigroup(6);
<symmetric inverse monoid of degree 6>
gap> Size(I);
13327
gap> IsRegularSemigroup(I);
true
gap> P := PartitionMonoid(4);
<regular bipartition *-monoid of size 4140, degree 4 with 4 generators>
gap> Size(P);
4140
gap> IsRegularSemigroup(P);
true
gap> MF := FullMatrixMonoid(4, 3^2);
<general linear monoid 4x4 over GF(3^2)>
gap> Size(MF);
1853020188851841
gap> IsRegularSemigroup(MF);
true
gap> MB := FullBooleanMatMonoid(4);
<monoid of 4x4 boolean matrices with 7 generators>
gap> Size(MB);
65536
gap> IsRegularSemigroup(MB);
false

T := FullTransformationSemigroup(5);
Size(T);
IsRegularSemigroup(T);
I := SymmetricInverseSemigroup(6);
Size(I);
IsRegularSemigroup(I);
P := PartitionMonoid(4);
Size(P);
IsRegularSemigroup(P);
MF := FullMatrixMonoid(4, 3^2);
Size(MF);
IsRegularSemigroup(MF);
MB := FullBooleanMatMonoid(4);
Size(MB);
IsRegularSemigroup(MB);

Info

See Chapter 7 of the Semigroups manual for a list of many more standard semigroups and monoids implemented by the Semigroups package.

Finitely generated subsemigroups and submonoids

If A is a list of semigroup generators then we can construct the semigroup generated by A using the Semigroup function:

gap> a := Transformation([9, 5, 10, 8, 1, 4, 1, 4, 5, 2]);;
gap> b := Transformation([8, 8, 6, 5, 8, 9, 1, 3, 6, 6]);;
gap> c := Transformation([2, 8, 5, 4, 10, 4, 5, 4, 10, 10]);;
gap> T := Semigroup([a, b, c]);
<transformation semigroup of degree 10 with 3 generators>
gap> Size(T);
5965
gap> IsRegularSemigroup(T);
false
gap> d := Bipartition([
> [ 1, 2, 4, -5 ], [ 3, -7 ], [ 5, 9, 10, -10 ], [ 6 ], 
> [ 7, -2, -3, -8, -9 ], [ 8 ], [ -1 ], [ -4 ], [ -6 ]]);
<bipartition: [ 1, 2, 4, -5 ], [ 3, -7 ], [ 5, 9, 10, -10 ], [ 6 ], 
[ 7, -2, -3, -8, -9 ], [ 8 ], [ -1 ], [ -4 ], [ -6 ]>
gap> e := Bipartition([
> [ 1, 3, 10, -4, -5, -7, -9 ], [ 2, 4, 5, 7, -1, -3, -8 ], 
> [ 6, 8, 9, -2 ], [ -6 ], [ -10 ]]);
<bipartition: [ 1, 3, 10, -4, -5, -7, -9 ], [ 2, 4, 5, 7, -1, -3, -8 ], 
[ 6, 8, 9, -2 ], [ -6 ], [ -10 ]>
gap> f := Bipartition([
> [ 1, 2, 4, 9, 10, -7 ], [ 3, 6, 7, 8, -1, -2, -8 ], 
> [ 5, -3, -4, -5, -6, -9, -10 ]]);
<block bijection: [ 1, 2, 4, 9, 10, -7 ], [ 3, 6, 7, 8, -1, -2, -8 ], 
[ 5, -3, -4, -5, -6, -9, -10 ]>
gap> g := Bipartition([
> [ 1, 2, -1, -8 ], [ 3, 7, -3, -7, -10 ], [ 4, 5, 9, -5, -6 ], 
> [ 6, 8, -2 ], [ 10 ], [ -4, -9 ]]);
<bipartition: [ 1, 2, -1, -8 ], [ 3, 7, -3, -7, -10 ], [ 4, 5, 9, -5, -6 ], 
[ 6, 8, -2 ], [ 10 ], [ -4, -9 ]>
gap> S := Semigroup([d, e, f, g]);
<bipartition semigroup of degree 10 with 4 generators>
gap> Size(S);
24
gap> IsRegularSemigroup(S);
false

a := Transformation([9, 5, 10, 8, 1, 4, 1, 4, 5, 2]);;
b := Transformation([8, 8, 6, 5, 8, 9, 1, 3, 6, 6]);;
c := Transformation([2, 8, 5, 4, 10, 4, 5, 4, 10, 10]);;
T := Semigroup([a, b, c]);
Size(T);
IsRegularSemigroup(T);
d := Bipartition([
[ 1, 2, 4, -5 ], [ 3, -7 ], [ 5, 9, 10, -10 ], [ 6 ], 
[ 7, -2, -3, -8, -9 ], [ 8 ], [ -1 ], [ -4 ], [ -6 ]]);
e := Bipartition([
[ 1, 3, 10, -4, -5, -7, -9 ], [ 2, 4, 5, 7, -1, -3, -8 ], 
[ 6, 8, 9, -2 ], [ -6 ], [ -10 ]]);
f := Bipartition([
[ 1, 2, 4, 9, 10, -7 ], [ 3, 6, 7, 8, -1, -2, -8 ], 
[ 5, -3, -4, -5, -6, -9, -10 ]]);
g := Bipartition([
[ 1, 2, -1, -8 ], [ 3, 7, -3, -7, -10 ], [ 4, 5, 9, -5, -6 ], 
[ 6, 8, -2 ], [ 10 ], [ -4, -9 ]]);
S := Semigroup([d, e, f, g]);
Size(S);
IsRegularSemigroup(S);

As mention at the start of the Kinds of elements section, in theory any collection of elements with associative multiplication can be used to construct a finitely generated semigroup using the Semigroup function. However, using the kinds of elements described in the Kinds of elements section is guaranteed to utilize the fast algorithms implemented in Semigroups. For an extreme example consider:

gap> gens := [
> Transformation([10, 10, 6, 9, 3, 6, 6, 8, 3, 4]),
> Transformation([10, 10, 6, 9, 3, 6, 6, 8, 3, 4]),
> Transformation([6, 8, 8, 4, 7, 1, 2, 9, 9, 3]),
> Transformation([6, 8, 8, 4, 7, 1, 2, 9, 9, 3]),
> Transformation([9, 9, 1, 3, 4, 10, 5, 6, 3, 3]),
> Transformation([9, 9, 1, 3, 4, 10, 5, 6, 3, 3]),
> Transformation([7, 1, 2, 9, 3, 10, 3, 2, 5, 6])];;
gap> S := Semigroup(gens);
<transformation semigroup of degree 10 with 7 generators>
gap> Size(S);
3063073
gap> time; # The time function outputs the time it took to run the last command in ms
4451

gens := [
Transformation([10, 10, 6, 9, 3, 6, 6, 8, 3, 4]),
Transformation([10, 10, 6, 9, 3, 6, 6, 8, 3, 4]),
Transformation([6, 8, 8, 4, 7, 1, 2, 9, 9, 3]),
Transformation([6, 8, 8, 4, 7, 1, 2, 9, 9, 3]),
Transformation([9, 9, 1, 3, 4, 10, 5, 6, 3, 3]),
Transformation([9, 9, 1, 3, 4, 10, 5, 6, 3, 3]),
Transformation([7, 1, 2, 9, 3, 10, 3, 2, 5, 6])];;
S := Semigroup(gens);
Size(S);
time; # The time function outputs the time it took to run the last command in ms

We are able to enumerate a semigroup of 3 million elements in 4.5 seconds. Of course the runtime will depend on the machine and so on, but the point is that this computation takes seconds instead of days with Semigroups. Trying to run the computation without the Semigroups package loaded will cause the Size computation to run significantly longer (we have not been able to run it to completion without the Semigroups package loaded).

In certain cases, we may even be able to determine that a semigroup is infinite using the Semigroups package:

gap> A := Matrix(Integers, [[1, 1], [0, 1]]);
<2x2-matrix over Integers>
gap> B := Matrix(Integers, [[1, 1], [0, 0]]);
<2x2-matrix over Integers>
gap> S := Semigroup([A, B]);
<semigroup of 2x2 integer matrices with 2 generators>
gap> Size(S);
infinity

A := Matrix(Integers, [[1, 1], [0, 1]]);
B := Matrix(Integers, [[1, 1], [0, 0]]);
S := Semigroup([A, B]);
Size(S);

However, one must be careful, since it is general undecidable if a matrix semigroup is finite or not. Modifying the example just slightly we obtain an infinite semigroup whose size calculation does not terminate:

gap> C := Matrix(Integers, [[1, 1], [0, 1]]);
<2x2-matrix over Integers>
gap> D := Matrix(Integers, [[0, 1], [-1, 0]]);
<2x2-matrix over Integers>
gap> S := Semigroup([C, D]);
<semigroup of 2x2 integer matrices with 2 generators>
gap> # The following computation will run forever, uncomment the next line
gap> # at your own risk:
gap> # Size(S);
gap> # Pressing Ctrl+C twice in your console in rapid succession
gap> # should kill the computation

C := Matrix(Integers, [[1, 1], [0, 1]]);
D := Matrix(Integers, [[0, 1], [-1, 0]]);
S := Semigroup([C, D]);
# The following computation will run forever, uncomment the next line
# at your own risk:
# Size(S);
# Pressing Ctrl+C twice in your console in rapid succession
# should kill the computation

To create a monoid defined by a finite generated set instead of a semigroup, we can use the Monoid function:

gap> a := Transformation([9, 5, 10, 8, 1, 4, 1, 4, 5, 2]);;
gap> b := Transformation([8, 8, 6, 5, 8, 9, 1, 3, 6, 6]);;
gap> c := Transformation([2, 8, 5, 4, 10, 4, 5, 4, 10, 10]);;
gap> T := Monoid([a, b, c]);
<transformation semigroup of degree 10 with 3 generators>
gap> Size(T);
5966
gap> IsRegularSemigroup(T);
false
gap> d := Bipartition([
> [ 1, 2, 4, -5 ], [ 3, -7 ], [ 5, 9, 10, -10 ], [ 6 ], 
> [ 7, -2, -3, -8, -9 ], [ 8 ], [ -1 ], [ -4 ], [ -6 ]]);
<bipartition: [ 1, 2, 4, -5 ], [ 3, -7 ], [ 5, 9, 10, -10 ], [ 6 ], 
[ 7, -2, -3, -8, -9 ], [ 8 ], [ -1 ], [ -4 ], [ -6 ]>
gap> e := Bipartition([
> [ 1, 3, 10, -4, -5, -7, -9 ], [ 2, 4, 5, 7, -1, -3, -8 ], 
> [ 6, 8, 9, -2 ], [ -6 ], [ -10 ]]);
<bipartition: [ 1, 3, 10, -4, -5, -7, -9 ], [ 2, 4, 5, 7, -1, -3, -8 ], 
[ 6, 8, 9, -2 ], [ -6 ], [ -10 ]>
gap> f := Bipartition([
> [ 1, 2, 4, 9, 10, -7 ], [ 3, 6, 7, 8, -1, -2, -8 ], 
> [ 5, -3, -4, -5, -6, -9, -10 ]]);
<block bijection: [ 1, 2, 4, 9, 10, -7 ], [ 3, 6, 7, 8, -1, -2, -8 ], 
[ 5, -3, -4, -5, -6, -9, -10 ]>
gap> g := Bipartition([
> [ 1, 2, -1, -8 ], [ 3, 7, -3, -7, -10 ], [ 4, 5, 9, -5, -6 ], 
> [ 6, 8, -2 ], [ 10 ], [ -4, -9 ]]);
<bipartition: [ 1, 2, -1, -8 ], [ 3, 7, -3, -7, -10 ], [ 4, 5, 9, -5, -6 ], 
[ 6, 8, -2 ], [ 10 ], [ -4, -9 ]>
gap> S := Monoid([d, e, f, g]);
<bipartition semigroup of degree 10 with 4 generators>
gap> Size(S);
25
gap> IsRegularSemigroup(S);
false

a := Transformation([9, 5, 10, 8, 1, 4, 1, 4, 5, 2]);;
b := Transformation([8, 8, 6, 5, 8, 9, 1, 3, 6, 6]);;
c := Transformation([2, 8, 5, 4, 10, 4, 5, 4, 10, 10]);;
T := Monoid([a, b, c]);
Size(T);
IsRegularSemigroup(T);
d := Bipartition([
[ 1, 2, 4, -5 ], [ 3, -7 ], [ 5, 9, 10, -10 ], [ 6 ], 
[ 7, -2, -3, -8, -9 ], [ 8 ], [ -1 ], [ -4 ], [ -6 ]]);
e := Bipartition([
[ 1, 3, 10, -4, -5, -7, -9 ], [ 2, 4, 5, 7, -1, -3, -8 ], 
[ 6, 8, 9, -2 ], [ -6 ], [ -10 ]]);
f := Bipartition([
[ 1, 2, 4, 9, 10, -7 ], [ 3, 6, 7, 8, -1, -2, -8 ], 
[ 5, -3, -4, -5, -6, -9, -10 ]]);
g := Bipartition([
[ 1, 2, -1, -8 ], [ 3, 7, -3, -7, -10 ], [ 4, 5, 9, -5, -6 ], 
[ 6, 8, -2 ], [ 10 ], [ -4, -9 ]]);
S := Monoid([d, e, f, g]);
Size(S);
IsRegularSemigroup(S);

Warning

In GAP monoids are implemented as algebras with two operations: a binary multiplication and a nullary identity. Hence, while every Monoid is a Semigroup in GAP, not every Semigroup that is mathematically a monoid is a Monoid in the GAP sense.

So, if a semigroup constructed with the Semigroup function happens to be a monoid, it will not be recognized by GAP as a monoid. For example we could construct the symmetric group with the Semigroup function and check if it is a monoid using the IsMonoid function:

gap> S := Semigroup([(1, 2), (1, 2, 3)]);
<semigroup with 2 generators>
gap> Elements(M);
[ (), (2,3), (1,2), (1,2,3), (1,3,2), (1,3) ]
gap> IsMonoid(S);
false

There are two solutions to this:

  1. We can construct the semigroup using the Monoid function instead: 
    gap> S := Monoid([(1, 2), (1, 2, 3)]);
<group with 2 generators>
gap> Elements(S);
[ (), (2,3), (1,2), (1,2,3), (1,3,2), (1,3) ]
gap> IsMonoid(S);
true
    The resulting monoid has all the same elements, but it is additionally recognized as a monoid.
  2. We can use the AsMonoid function to convert the semigroup to a monoid: 
    gap> S := Semigroup([(1, 2), (1, 2, 3)]);
<semigroup with 2 generators>
gap> IsMonoid(S);
false
gap> M := AsMonoid(S);
<group with 2 generators>
gap> Elements(M);
[ (), (2,3), (1,2), (1,2,3), (1,3,2), (1,3) ]
gap> IsMonoid(M);
true

Info

See Chapter 6 of the Semigroups manual for more info on how the Semigroups package handles finitely generated subsemigroups as well as Section 51.1 and Section 51.2 of the GAP reference manual for more information on semigroups and monoids in GAP.

Multiplication tables

A multiplication table is an \(n\times n\) table \(A\) whose entries are integers \(\{1, \ldots, n\}\). The table \(A\) defines a semigroup with elements \(\{1, \ldots, n\}\) and the product of \(i, j\in \{1, \ldots, n\}\) is given by the \((i, j)\)-th entry of \(A\). In GAP a multiplication table can be specified by a list of lists whose entries are integers. We can construct a semigroup from such a multiplication table using the SemigroupByMultiplicationTable function. If the given multiplication table does not define a semigroup, i.e. it is not associative, then the function returns fail instead. The MonoidByMultiplicationTable function can be used to construct a monoid from a multiplication table instead.

gap> table1 := [
> [2, 2, 4, 4],
> [3, 2, 3, 3],
> [3, 1, 1, 3],
> [4, 4, 1, 3]];
[ [ 2, 2, 4, 4 ], [ 3, 2, 3, 3 ], [ 3, 1, 1, 3 ], [ 4, 4, 1, 3 ] ]
gap> SemigroupByMultiplicationTable(table1);
fail
gap> table2 := [
> [1, 2, 1, 2],
> [1, 2, 1, 2],
> [3, 4, 3, 4],
> [3, 4, 3, 4]];
[ [ 1, 2, 1, 2 ], [ 1, 2, 1, 2 ], [ 3, 4, 3, 4 ], [ 3, 4, 3, 4 ] ]
gap> SemigroupByMultiplicationTable(table2);
<semigroup of size 4, with 4 generators>
gap> table3 := [
> [1, 1, 4, 4],
> [1, 2, 3, 4],
> [1, 3, 2, 4],
> [1, 4, 1, 4]];
[ [ 1, 1, 4, 4 ], [ 1, 2, 3, 4 ], [ 1, 3, 2, 4 ], [ 1, 4, 1, 4 ] ]
gap> SemigroupByMultiplicationTable(table3);
<semigroup of size 4, with 4 generators>
gap> MonoidByMultiplicationTable(table2);
fail
gap> MonoidByMultiplicationTable(table3);
<monoid of size 4, with 4 generators>

table1 := [
[2, 2, 4, 4],
[3, 2, 3, 3],
[3, 1, 1, 3],
[4, 4, 1, 3]];
SemigroupByMultiplicationTable(table1);
table2 := [
[1, 2, 1, 2],
[1, 2, 1, 2],
[3, 4, 3, 4],
[3, 4, 3, 4]];
SemigroupByMultiplicationTable(table2);
table3 := [
[1, 1, 4, 4],
[1, 2, 3, 4],
[1, 3, 2, 4],
[1, 4, 1, 4]];
SemigroupByMultiplicationTable(table3);
MonoidByMultiplicationTable(table2);
MonoidByMultiplicationTable(table3);

Dually, the MultiplicationTable function can be used to find the multiplication table of any given semigroup or monoid:

gap> T := FullTransformationSemigroup(2);
<full transformation monoid of degree 2>
gap> Display(MultiplicationTable(T));
[ [  1,  1,  4,  4 ],
[  1,  2,  3,  4 ],
[  1,  3,  2,  4 ],
[  1,  4,  1,  4 ] ]
gap> S := Monoid([Transformation([1, 1, 1]), Transformation([1, 2, 3])]);
<commutative transformation monoid of degree 3 with 1 generator>
gap> Display(MultiplicationTable(S));
[ [  1,  1 ],
[  1,  2 ] ]

T := FullTransformationSemigroup(2);
Display(MultiplicationTable(T));
S := Monoid([Transformation([1, 1, 1]), Transformation([1, 2, 3])]);
Display(MultiplicationTable(S));

Warning

Multiplication tables are a very inefficient way of defining a semigroup. Indeed, to define a semigroup \(S\) using a multiplication table we need to give a table of \(|S|^2\) entries. However, if a generating set \(A\) for \(S\) is known, we can construct a transformation representation for \(S\) by taking only those rows in the multiplication table that correspond to the generators in \(A\). This allows us to construct a transformation semigroup \(S^\prime\) that is isomorphic to \(S\), and we only need specify \(|A|\cdot |S|\) many entries.

For example, if \(S\) is a 3-generated semigroup of size 1000, specifying a multiplication table requires a 1000000 entry table, whereas an isomorphic transformation semigroup can be specified with just 3 transformations of degree 1000, for a total of 3000 entries. Furthermore, algorithms for transformation semigroups are generally much faster.

The small semigroups library

The Smallsemi package contains a database of all semigroups of order up to \(8\) up to isomorphism and anti-isomorphism. To use the Smallsemi package we need to load it first, just as we did with the Semigroups package. We can get the \(n\)-th semigroup of order \(m\) using the SmallSemigroup function with arguments m and n.

gap> LoadPackage("Smallsemi");
------------------------------------------------------------------------------------
Smallsemi -   A library of small semigroups
by Andreas Distler & James Mitchell
For contents, type: ?Smallsemi:
Loading Smallsemi 0.7.2 ...
------------------------------------------------------------------------------------
true
gap> Display(MultiplicationTable(S1));
[ [  1,  1,  1,  1 ],
[  1,  1,  1,  1 ],
[  1,  1,  1,  1 ],
[  1,  1,  1,  1 ] ]
gap> S2 := SmallSemigroup(4, 2);
<small semigroup of size 4>
gap> Display(MultiplicationTable(S2));
[ [  1,  1,  1,  1 ],
[  1,  1,  1,  1 ],
[  1,  1,  1,  1 ],
[  1,  1,  2,  1 ] ]
gap> S3 := SmallSemigroup(8, 1000);
<small semigroup of size 8>
gap> Display(MultiplicationTable(S3));
[ [  1,  1,  1,  1,  1,  1,  1,  1 ],
[  1,  1,  1,  1,  1,  1,  1,  1 ],
[  1,  1,  1,  1,  1,  1,  1,  1 ],
[  1,  1,  1,  1,  1,  1,  1,  2 ],
[  1,  1,  1,  1,  1,  1,  1,  2 ],
[  1,  1,  1,  1,  2,  1,  1,  1 ],
[  1,  1,  1,  2,  3,  1,  1,  2 ],
[  1,  1,  2,  2,  2,  1,  6,  1 ] ]

LoadPackage("Smallsemi");
S1 := SmallSemigroup(4, 1);
Display(MultiplicationTable(S1));
S2 := SmallSemigroup(4, 2);
Display(MultiplicationTable(S2));
S3 := SmallSemigroup(8, 1000);
Display(MultiplicationTable(S3));

Info

See the Smallsemi package documentation for more information about the small semigroups library.

Analyzing semigroups

Now that we can construct semigroups in GAP, we consider methods of analyzing them.

Finiteness and enumeration

We already saw that the Size function can be used to determine the order of a semigroup or monoid. The IsFinite function can be used to test if a given semigroup is finite or infinite. The elements of a semigroup can be computed using the Elements function. The idempotents, i.e. elements \(x\) such that \(x^2 = x\), can be found using the Idempotents function.

gap> S := Semigroup([Transformation([1, 1]), Transformation([2, 2]), Transformation([5, 4, 3, 2, 1])]);
<transformation semigroup of degree 5 with 3 generators>
gap> IsFinite(S);
true
gap> Size(S);
18
gap> Elements(S);
[ Transformation( [ 1, 1, 3, 4, 4 ] ), Transformation( [ 1, 1 ] ), 
  Transformation( [ 1, 1, 3, 5, 5 ] ), Transformation( [ 1, 2, 3, 4, 4 ] ), 
  IdentityTransformation, Transformation( [ 1, 2, 3, 5, 5 ] ), 
  Transformation( [ 2, 2, 3, 4, 4 ] ), Transformation( [ 2, 2 ] ), 
  Transformation( [ 2, 2, 3, 5, 5 ] ), Transformation( [ 4, 4, 3, 1, 1 ] ), 
  Transformation( [ 4, 4, 3, 2, 1 ] ), Transformation( [ 4, 4, 3, 2, 2 ] ), 
  Transformation( [ 5, 4, 3, 1, 1 ] ), Transformation( [ 5, 4, 3, 2, 1 ] ), 
  Transformation( [ 5, 4, 3, 2, 2 ] ), Transformation( [ 5, 5, 3, 1, 1 ] ), 
  Transformation( [ 5, 5, 3, 2, 1 ] ), Transformation( [ 5, 5, 3, 2, 2 ] ) ]
gap> Idempotents(S);
[ Transformation( [ 1, 1 ] ), Transformation( [ 2, 2 ] ), IdentityTransformation, 
  Transformation( [ 1, 2, 3, 5, 5 ] ), Transformation( [ 1, 2, 3, 4, 4 ] ), 
  Transformation( [ 1, 1, 3, 5, 5 ] ), Transformation( [ 2, 2, 3, 5, 5 ] ), 
  Transformation( [ 1, 1, 3, 4, 4 ] ), Transformation( [ 2, 2, 3, 4, 4 ] ) ]
gap> T := Semigroup([Matrix(Integers, [[1, 1], [1, 0]]), Matrix(Integers, [[1, 0], [0, 0]])]);
<semigroup of 2x2 integer matrices with 2 generators>
gap> IsFinite(T);
false

S := Semigroup([Transformation([1, 1]), Transformation([2, 2]), Transformation([5, 4, 3, 2, 1])]);
Size(S);
IsFinite(S);
Elements(S);
Idempotents(S);
T := Semigroup([Matrix(Integers, [[1, 1], [1, 0]]), Matrix(Integers, [[1, 0], [0, 0]])]);
IsFinite(T);

Warning

It is in general undecidable if a given finitely generated semigroup is finite. Hence the functions Size, IsFinite and Idempotents may run forever on semigroups that are infinite, as we saw in the Finitely generated subsemigroups and submonoids section. However, the functions Size, IsFinite, Elements and Idempotents are guaranteed to terminate when the underlying semigroup is finite.

Cayley graphs

Recall that the right Cayley graph of a semigroup \(S\) generated by \(A\) is the directed graph \(G\) with vertex set \(V(G) = S\) and edge set \(E(G) = \{(x, a, y)\in S \times A \times S : x\cdot a = y \}\). The left Cayley graph is defined analogously replacing the condition \(x\cdot a = y\) with \(a\cdot x = y\). We can think of these as directed graphs whose edges are colored by elements in \(A\). The RightCayleyDigraph and LeftCayleyDigraph functions can be used to compute, respectively, the right and left Cayley graphs of a semigroup S. The output of these functions is a directed graph represented as a Digraph object.

gap> S := Semigroup([Transformation([1, 1]), Transformation([2, 2]), Transformation([5, 4, 3, 2, 1])]);
<transformation semigroup of degree 5 with 3 generators>
gap> RightCayleyDigraph(S);
<immutable digraph with 18 vertices, 54 edges>
gap> LeftCayleyDigraph(S);
<immutable multidigraph with 18 vertices, 54 edges>

S := Semigroup([Transformation([1, 1]), Transformation([2, 2]), Transformation([5, 4, 3, 2, 1])]);
RightCayleyDigraph(S);
LeftCayleyDigraph(S);

There are two ways of visualizing these graphs using the Semigroups package:

  1. We can visualize these graphs without the edge coloring using the DotRightCayleyDigraph and DotLeftCayleyDigraph functions, which produce graphviz code describing the right and left Cayley graphs, respectively. If you have graphviz installed on your computer, you can render the resulting graphs using the Splash function:

    gap> S := Semigroup([Transformation([1, 1]), Transformation([2, 2]), Transformation([5, 4, 3, 2, 1])]);
<transformation semigroup of degree 5 with 3 generators>
gap> DotRightCayleyDigraph(S);
"//dot\ndigraph hgn{\nnode [shape=circle]\n1 [label=\"a\"]\n2 [label=\"b\"]\n3 [label\
=\"c\"]\n4 [label=\"ac\"]\n5 [label=\"bc\"]\n6 [label=\"ca\"]\n7 [label=\"cb\"]\n8 [l\
abel=\"c ^ 2\"]\n9 [label=\"aca\"]\n10 [label=\"acb\"]\n11 [label=\"bca\"]\n12 [label\
=\"bcb\"]\n13 [label=\"cac\"]\n14 [label=\"cbc\"]\n15 [label=\"acac\"]\n16 [label=\"a\
cbc\"]\n17 [label=\"bcac\"]\n18 [label=\"bcbc\"]\n1 -> 1\n1 -> 2\n1 -> 4\n2 -> 1\n2 -\
> 2\n2 -> 5\n3 -> 6\n3 -> 7\n3 -> 8\n4 -> 9\n4 -> 10\n4 -> 1\n5 -> 11\n5 -> 12\n5 -> \
2\n6 -> 6\n6 -> 7\n6 -> 13\n7 -> 6\n7 -> 7\n7 -> 14\n8 -> 1\n8 -> 2\n8 -> 3\n9 -> 9\n\
9 -> 10\n9 -> 15\n10 -> 9\n10 -> 10\n10 -> 16\n11 -> 11\n11 -> 12\n11 -> 17\n12 -> 11\
\n12 -> 12\n12 -> 18\n13 -> 15\n13 -> 17\n13 -> 6\n14 -> 16\n14 -> 18\n14 -> 7\n15 ->\
15\n15 -> 17\n15 -> 9\n16 -> 16\n16 -> 18\n16 -> 10\n17 -> 15\n17 -> 17\n17 -> 11\n1\
8 -> 16\n18 -> 18\n18 -> 12\n}\n"
gap> Splash(DotLeftCayleyDigraph(S));

    S := Semigroup([Transformation([1, 1]), Transformation([2, 2]), Transformation([5, 4, 3, 2, 1])]);
DotRightCayleyDigraph(S);
Splash(DotLeftCayleyDigraph(S));

    A visualization of the left Cayley digraph of S A visualization of the left Cayley digraph of S

    A visualization of the left Cayley digraph of \(S\). Result of the Splash(DotLeftDigraph(S)) call.

  2. We can visualize these graphs with edge coloring using the DotEdgeColoredDigraph function, applied to the right or left Cayley digraph, and a list describing the edge colors. The Splash function can be used to render this output.

    gap> S := Semigroup([Transformation([1, 1]), Transformation([2, 2]), Transformation([5, 4, 3, 2, 1])]);
<transformation semigroup of degree 5 with 3 generators>
gap> # We need to specify the edge colors at each vertex of the graph
gap> # The following function creates a list of lists, which indicates
gap> # that the outgoing edges at each vertex of the Cayley graph
gap> # should be colored red, green and blue, respectively.
gap> colors := List([1 .. Size(S)], x -> ["red", "green", "blue"]);;
gap> DotEdgeColoredDigraph(LeftCayleyDigraph(S), colors);
"//dot\ndigraph hgn{\nnode [shape=circle]\n1\n2\n3\n4\n5\n6\n7\n8\n9\n10\n11\n12\n13\
\n14\n15\n16\n17\n18\n1 -> 1[color=red]\n1 -> 1[color=green]\n1 -> 6[color=blue]\n2 -\
> 2[color=red]\n2 -> 2[color=green]\n2 -> 7[color=blue]\n3 -> 4[color=red]\n3 -> 5[co\
lor=green]\n3 -> 8[color=blue]\n4 -> 4[color=red]\n4 -> 4[color=green]\n4 -> 13[color\
=blue]\n5 -> 5[color=red]\n5 -> 5[color=green]\n5 -> 14[color=blue]\n6 -> 9[color=red\
]\n6 -> 11[color=green]\n6 -> 1[color=blue]\n7 -> 10[color=red]\n7 -> 12[color=green]\
\n7 -> 2[color=blue]\n8 -> 1[color=red]\n8 -> 2[color=green]\n8 -> 3[color=blue]\n9 -\
> 9[color=red]\n9 -> 9[color=green]\n9 -> 15[color=blue]\n10 -> 10[color=red]\n10 -> \
10[color=green]\n10 -> 17[color=blue]\n11 -> 11[color=red]\n11 -> 11[color=green]\n11\
-> 16[color=blue]\n12 -> 12[color=red]\n12 -> 12[color=green]\n12 -> 18[color=blue]\
\n13 -> 15[color=red]\n13 -> 17[color=green]\n13 -> 4[color=blue]\n14 -> 16[color=red\
]\n14 -> 18[color=green]\n14 -> 5[color=blue]\n15 -> 15[color=red]\n15 -> 15[color=gr\
een]\n15 -> 9[color=blue]\n16 -> 16[color=red]\n16 -> 16[color=green]\n16 -> 11[color\
=blue]\n17 -> 17[color=red]\n17 -> 17[color=green]\n17 -> 10[color=blue]\n18 -> 18[co\
lor=red]\n18 -> 18[color=green]\n18 -> 12[color=blue]\n}\n"
gap> Splash(DotEdgeColoredDigraph(LeftCayleyDigraph(S), colors));

    S := Semigroup([Transformation([1, 1]), Transformation([2, 2]), Transformation([5, 4, 3, 2, 1])]);
# We need to specify the edge colors at each vertex of the graph
# The following function creates a list of lists, which indicates
# that the outgoing edges at each vertex of the Cayley graph
# should be colored red, green and blue, respectively.
colors := List([1 .. Size(S)], x -> ["red", "green", "blue"]);;
DotEdgeColoredDigraph(LeftCayleyDigraph(S), colors);
Splash(DotEdgeColoredDigraph(LeftCayleyDigraph(S), colors));

    A colorful visualization of the left Cayley digraph of S A colorful visualization of the left Cayley digraph of S

    A colorful visualization of the left Cayley digraph of \(S\). Result of the Splash(DotEdgeColoredDigraph(LeftCayleyDigraph(S), colors)) call.

Info

See Chapter 16 of the Semigroups manual for more information about visualizing semigroups and their Cayley graphs, as well as Chapter 9 of the Digraphs package manual.

Properties of semigroups

Recall that an element \(x \in S\) is regular if there exists some \(y\in S\) such that \(xyx = x\) and \(yxy = y\). We say that the element \(y\) is an inverse of \(x\) in this case. A semigroup is regular if every element is regular. A semigroup is inverse if every element has precisely one inverse. A semigroup is a band if the equation \(x^2 = x\) holds for all \(x\in S\). A semigroup is commutative if the equation \(xy = yx\) holds for all \(x, y \in S\). A semigroup is simple if it does not contain a non-trivial two-sided ideal.

We can

gap> S := Semigroup([
> Transformation([3, 1, 4, 2, 5, 2, 1, 6, 1]),
> Transformation([5, 7, 8, 8, 7, 5, 9, 1, 9]),
> Transformation([7, 6, 2, 8, 4, 7, 5, 8, 3])]);
<transformation semigroup of degree 9 with 3 generators>
gap> x := Transformation([3, 1, 4, 2, 5, 2, 1, 6, 1]);;
gap> InversesOfSemigroupElement(S, x);
[  ]
gap> IsRegularSemigroupElement(S, x);
false
gap> y := Transformation([1, 9, 7, 5, 5, 1, 9, 5, 1]);;
gap> InversesOfSemigroupElement(S, y);
[ Transformation( [ 1, 5, 1, 2, 5, 1, 3, 2, 2 ] ), 
  Transformation( [ 1, 2, 3, 5, 5, 1, 3, 5, 2 ] ), 
  Transformation( [ 1, 5, 1, 1, 5, 1, 3, 1, 2 ] ) ]
gap> IsRegularSemigroupElement(S, y);
true
gap> IsRegularSemigroup(S);
false
gap> T := Semigroup([
> Transformation([1, 2, 4, 5, 6, 3, 7, 8]),
> Transformation([3, 3, 4, 5, 6, 2, 7, 8]),
> Transformation([1, 2, 5, 3, 6, 8, 4, 4])]);;
gap> IsInverseSemigroup(T);
true
gap> U := Semigroup([
> Transformation([1, 1, 1, 4, 4, 4, 7, 7, 7, 1]),
> Transformation([2, 2, 2, 5, 5, 5, 8, 8, 8, 2]),
> Transformation([3, 3, 3, 6, 6, 6, 9, 9, 9, 3]),
> Transformation([1, 1, 1, 4, 4, 4, 7, 7, 7, 4]),
> Transformation([1, 1, 1, 4, 4, 4, 7, 7, 7, 7])]);;
gap> IsBand(U);
true
gap> V := Semigroup([
> Transformation([2, 4, 5, 3, 7, 8, 6, 9, 1]),
> Transformation([3, 5, 6, 7, 8, 1, 9, 2, 4])]);;
gap> IsCommutativeSemigroup(V);
true
gap> W := Semigroup([
> Transformation([2, 2, 4, 4, 6, 6, 8, 8, 10, 10, 12, 12, 2]),
> Transformation([1, 1, 3, 3, 5, 5, 7, 7, 9, 9, 11, 11, 3]),
> Transformation([1, 7, 3, 9, 5, 11, 7, 1, 9, 3, 11, 5, 5]),
> Transformation([7, 7, 9, 9, 11, 11, 1, 1, 3, 3, 5, 5, 7])]);;
gap> IsSimpleSemigroup(W);
true

S := Semigroup([
Transformation([3, 1, 4, 2, 5, 2, 1, 6, 1]),
Transformation([5, 7, 8, 8, 7, 5, 9, 1, 9]),
Transformation([7, 6, 2, 8, 4, 7, 5, 8, 3])]);
x := Transformation([3, 1, 4, 2, 5, 2, 1, 6, 1]);;
InversesOfSemigroupElement(S, x);
IsRegularSemigroupElement(S, x);
y := Transformation([1, 9, 7, 5, 5, 1, 9, 5, 1]);;
InversesOfSemigroupElement(S, y);
IsRegularSemigroupElement(S, y);
IsRegularSemigroup(S);
T := Semigroup([
Transformation([1, 2, 4, 5, 6, 3, 7, 8]),
Transformation([3, 3, 4, 5, 6, 2, 7, 8]),
Transformation([1, 2, 5, 3, 6, 8, 4, 4])]);;
IsInverseSemigroup(T);
U := Semigroup([
Transformation([1, 1, 1, 4, 4, 4, 7, 7, 7, 1]),
Transformation([2, 2, 2, 5, 5, 5, 8, 8, 8, 2]),
Transformation([3, 3, 3, 6, 6, 6, 9, 9, 9, 3]),
Transformation([1, 1, 1, 4, 4, 4, 7, 7, 7, 4]),
Transformation([1, 1, 1, 4, 4, 4, 7, 7, 7, 7])]);;
IsBand(U);
V := Semigroup([
Transformation([2, 4, 5, 3, 7, 8, 6, 9, 1]),
Transformation([3, 5, 6, 7, 8, 1, 9, 2, 4])]);;
IsCommutativeSemigroup(V);
W := Semigroup([
Transformation([2, 2, 4, 4, 6, 6, 8, 8, 10, 10, 12, 12, 2]),
Transformation([1, 1, 3, 3, 5, 5, 7, 7, 9, 9, 11, 11, 3]),
Transformation([1, 7, 3, 9, 5, 11, 7, 1, 9, 3, 11, 5, 5]),
Transformation([7, 7, 9, 9, 11, 11, 1, 1, 3, 3, 5, 5, 7])]);;
IsSimpleSemigroup(W);

Info

See Chapter 12 of the Semigroups manual for a comprehensive list of semigroup properties that can be checked by the Semigroups package, as well as Section 51.4 of the GAP reference manual.

Green's relations and egg-box diagrams

Recall that the Green's \(\mathscr{R}, \mathscr{L}\) and \(\mathscr{J}\) relations are equivalence relations on a semigroup \(S\) defined by

  • \(x \mathscr{R} y\) if and only if \(x S = y S\),
  • \(x \mathscr{L} y\) if and only if \(S x = S y\),
  • \(x \mathscr{J} y\) if and only if \(S x S = S y S\).

The Green's \(\mathscr{H}\) and \(\mathscr{D}\) relations are defined as the intersection and composition of the \(\mathscr{R}\) and \(\mathscr{L}\) relations, respectively. For a finite semigroup, the \(\mathscr{D}\) and \(\mathscr{J}\) relations coincide.

We can obtain the \(\mathscr{R}, \mathscr{L}, \mathscr{D}\) or \(\mathscr{H}\)-equivalence class of an element of a semigroup using the RClass, LClass, DClass and HClass functions, respectively.

gap> S := Semigroup([Transformation([1, 1]), Transformation([2, 2]), Transformation([5, 4, 3, 2, 1])]);
<transformation semigroup of degree 5 with 3 generators>
gap> RClass(S, Transformation([1, 1]));
<Green's R-class: Transformation( [ 1, 1 ] )>
gap> Elements(RClass(S, Transformation([1, 1])));
[ Transformation( [ 1, 1 ] ), Transformation( [ 2, 2 ] ), 
  Transformation( [ 4, 4, 3, 2, 1 ] ), Transformation( [ 5, 5, 3, 2, 1 ] ) ]
gap> Elements(LClass(S, Transformation([1, 1])));
[ Transformation( [ 1, 1 ] ), Transformation( [ 5, 4, 3, 1, 1 ] ) ]
gap> Elements(DClass(S, Transformation([1, 1])));
[ Transformation( [ 1, 1 ] ), Transformation( [ 1, 2, 3, 4, 4 ] ), 
  Transformation( [ 1, 2, 3, 5, 5 ] ), Transformation( [ 2, 2 ] ), 
  Transformation( [ 4, 4, 3, 2, 1 ] ), Transformation( [ 5, 4, 3, 1, 1 ] ), 
  Transformation( [ 5, 4, 3, 2, 2 ] ), Transformation( [ 5, 5, 3, 2, 1 ] ) ]
gap> Elements(HClass(S, Transformation([1, 1])));
[ Transformation( [ 1, 1 ] ) ]

S := Semigroup([Transformation([1, 1]), Transformation([2, 2]), Transformation([5, 4, 3, 2, 1])]);
RClass(S, Transformation([1, 1]));
Elements(RClass(S, Transformation([1, 1])));
Elements(LClass(S, Transformation([1, 1])));
Elements(DClass(S, Transformation([1, 1])));
Elements(HClass(S, Transformation([1, 1])));

Recall that the egg-box diagram of a semigroup is a visual representation of its Green's relations. In GAP we can display them using the Splash and DotString functions:

gap> T := FullTransformationSemigroup(3);
gap> Splash(DotString(T, rec(maximal := true)));

T := FullTransformationSemigroup(3);
Splash(DotString(T, rec(maximal := true)));

The resulting egg-box diagram for \(\mathcal{T}_3\) can be seen on the right. The large boxes labelled 1, 2 and 3 in the diagram correspond to Green's \(\mathscr{D}\)-classes of \(\mathcal{T}_3\), the lines between them denote inclusion in the ordering on \(\mathscr{D}\)-classes induced by the Green's \(\mathscr{J}\)-relation.

The rows of the boxes representing the \(\mathscr{D}\)-classes correspond to Green's \(\mathscr{L}\)-classes, the columns to Green's \(\mathscr{R}\)-classes. Finally, the cells of the boxes representing the \(\mathscr{D}\)-classes are the \(\mathscr{H}\)-classes of \(\mathcal{T}_3\). Cells shaded in gray denote the group \(\mathscr{H}\)-classes, and they contain the StructureDescription of these groups, this is a consequence of the rec(maximal := true) argument.

So, by visual inspection we can deduce that \(\mathcal{T}_3\) has 3 Green's \(\mathscr{D}\)-classes, furthermore, each \(\mathscr{D}\)-class contains a group \(\mathscr{H}\)-class, and is therefore a regular \(\mathscr{D}\)-class. Hence we can conclude that \(\mathcal{T}_3\) is regular, just by visual inspection of the egg-box diagram.

The egg-box diagram of \(\mathcal{T}_3\) The egg-box diagram of \(\mathcal{T}_3\)

The egg-box diagram of \(\mathcal{T}_3\).

Info

See Chapter 10 of the Semigroups manual for a deeper look at Green's relation related functionality.

Isomorphisms

We can check if two semigroups \(S\) and \(T\) are isomorphic using the IsomorphismSemigroups function. The function will return an isomorphism, if one exists, and return fail if the semigroups are not isomorphic.

gap> S := Semigroup([Transformation([1, 1]), Transformation([2, 2])]);
<transformation semigroup of degree 2 with 2 generators>
gap> T := Semigroup([Transformation([1, 3, 3]), Transformation([1, 2, 2])]);
<transformation semigroup of degree 3 with 2 generators>
gap> IsomorphismSemigroups(S, T); # Isomorphism found
CompositionMapping( MappingByFunction( <Rees matrix semigroup 1x2 over Group(())>, 
<simple transformation semigroup of degree 3 with 2 generators>
, function( object ) ... end, function( object ) ... end ), CompositionMapping( 
((), GroupHomomorphismByImages( Group( [ () ] ), Group( [ () ] ), [  ], [  ] ), 
[ (), (), () ]), MappingByFunction( <simple transformation semigroup of degree 2 
with 2 generators>, <Rees matrix semigroup 1x2 over Group(())>
, function( object ) ... end, function( object ) ... end ) ) )
gap> IsomorphismSemigroups(S, FullTransformationMonoid(10)); # No isomorphism
fail

S := Semigroup([Transformation([1, 1]), Transformation([2, 2])]);
T := Semigroup([Transformation([1, 3, 3]), Transformation([1, 2, 2])]);
IsomorphismSemigroups(S, T); # Isomorphism found
IsomorphismSemigroups(S, FullTransformationMonoid(10)); # No isomorphism

Warning

If either S or T is an infinite semigroup, then IsomorphismSemigroups may never terminate as the isomorphism problem for infinite finitely generated semigroups is undecidable.

Info

See Chapter 14 of the Semigroups manual for more information about semigroup isomorphisms and homomorphisms.

Lattices of congruences

Given a semigroup \(S\) one can construct the congruence lattice of \(S\) using the LatticeOfCongruences function.

gap> P := PartitionMonoid(2);
<regular bipartition *-monoid of size 15, degree 2 with 3 generators>
gap> latt := LatticeOfCongruences(S);
<lattice of 11 two-sided congruences over <regular transformation semigroup 
of size 71, degree 5 with 3 generators>>
gap> CongruencesOfPoset(latt);
[ <2-sided semigroup congruence over <regular bipartition *-monoid of size 15, 
    degree 2 with 3 generators> with 0 generating pairs>, 
  <universal semigroup congruence over <regular bipartition *-monoid of size 15, 
    degree 2 with 3 generators>>, <2-sided semigroup congruence over 
    <regular bipartition *-monoid of size 15, degree 2 with 3 generators> with 
    1 generating pairs>, <2-sided semigroup congruence over <regular bipartition *-
    monoid of size 15, degree 2 with 3 generators> with 1 generating pairs>, 
  <2-sided semigroup congruence over <regular bipartition *-monoid of size 15, 
    degree 2 with 3 generators> with 1 generating pairs>, 
  <2-sided semigroup congruence over <regular bipartition *-monoid of size 15, 
    degree 2 with 3 generators> with 1 generating pairs>, 
  <2-sided semigroup congruence over <regular bipartition *-monoid of size 15, 
    degree 2 with 3 generators> with 1 generating pairs>, 
  <2-sided semigroup congruence over <regular bipartition *-monoid of size 15, 
    degree 2 with 3 generators> with 1 generating pairs>, 
  <2-sided semigroup congruence over <regular bipartition *-monoid of size 15, 
    degree 2 with 3 generators> with 1 generating pairs>, 
  <2-sided semigroup congruence over <regular bipartition *-monoid of size 15, 
    degree 2 with 3 generators> with 1 generating pairs>, 
  <2-sided semigroup congruence over <regular bipartition *-monoid of size 15, 
    degree 2 with 3 generators> with 2 generating pairs>, 
  <2-sided semigroup congruence over <regular bipartition *-monoid of size 15, 
    degree 2 with 3 generators> with 2 generating pairs>, 
  <2-sided semigroup congruence over <regular bipartition *-monoid of size 15, 
    degree 2 with 3 generators> with 2 generating pairs> ]

P := PartitionMonoid(2);
latt := LatticeOfCongruences(S);
CongruencesOfPoset(latt);

Analogous functions exist for computing the left and right congruence lattices of \(S\) as well.

We can use the DotString function to visualize a congruence lattice.

gap> P := PartitionMonoid(2);
<regular bipartition *-monoid of size 15, degree 2 with 3 generators>
gap> latt := LatticeOfCongruences(S);
<lattice of 11 two-sided congruences over <regular transformation semigroup 
of size 71, degree 5 with 3 generators>>
gap> Splash(DotString(latt));

P := PartitionMonoid(2);
latt := LatticeOfCongruences(S);
Splash(DotString(latt));

The congruence lattice of \(\mathcal{P}_2\) The congruence lattice of \(\mathcal{P}_2\)

The congruence lattice of \(\mathcal{P}_2\). Result of Splash(DotString(latt));.

Info

See Chapter 13 of the Semigroups manual for more information about semigroup congruences.

  1. East, J., Egri-Nagy, A., Mitchell, J. D. and Péresse, Y., Computing finite semigroups, J. Symbolic Computation, 92 (2019), 110 - 155. DOI: 10.1016/j.jsc.2018.01.002. ↩

  2. Froidure, V. and Pin, J.-E., Algorithms for computing finite semigroups, in Foundations of computational mathematics (Rio de Janeiro, 1997), Springer, Berlin (1997), 112–126. DOI: 10.1007/978-3-642-60539-0_9 ↩