51 Semigroups and Monoids This chapter describes functions for creating semigroups and monoids and determining information about them. 51.1 Semigroups 51.1-1 IsSemigroup IsSemigroup( D )  Synonym returns true if the object D is a semigroup. A semigroup is a magma (see 35) with associative multiplication. 51.1-2 Semigroup Semigroup( gen1, gen2, ... )  function Semigroup( gens )  function In the first form, Semigroup returns the semigroup generated by the arguments gen1, gen2, ..., that is, the closure of these elements under multiplication. In the second form, Semigroup returns the semigroup generated by the elements in the homogeneous list gens; a square matrix as only argument is treated as one generator, not as a list of generators. It is not checked whether the underlying multiplication is associative, use Magma (35.2-1) and IsAssociative (35.4-7) if you want to check whether a magma is in fact a semigroup.  Example  gap> a:= Transformation( [ 2, 3, 4, 1 ] ); Transformation( [ 2, 3, 4, 1 ] ) gap> b:= Transformation( [ 2, 2, 3, 4 ] ); Transformation( [ 2, 2 ] ) gap> s:= Semigroup(a, b);   51.1-3 Subsemigroup Subsemigroup( S, gens )  function SubsemigroupNC( S, gens )  function are just synonyms of Submagma (35.2-7) and SubmagmaNC (35.2-7), respectively.  Example  gap> a:=GeneratorsOfSemigroup(s)[1]; Transformation( [ 2, 3, 4, 1 ] ) gap> t:=Subsemigroup(s,[a]);   51.1-4 IsSubsemigroup IsSubsemigroup( S, T )  operation Returns: true or false. This operation returns true if the semigroup T is a subsemigroup of the semigroup S and false if it is not.  Example  gap> f := Transformation([5, 6, 7, 1, 4, 3, 2, 7]); Transformation( [ 5, 6, 7, 1, 4, 3, 2, 7 ] ) gap> T := Semigroup(f);; gap> IsSubsemigroup(FullTransformationSemigroup(4), T); false gap> S := Semigroup(f);; gap> T := Semigroup(f ^ 2);; gap> IsSubsemigroup(S, T); true  51.1-5 SemigroupByGenerators SemigroupByGenerators( gens )  operation is the underlying operation of Semigroup (51.1-2). 51.1-6 AsSemigroup AsSemigroup( C )  operation If C is a collection whose elements form a semigroup under \* (31.12-1) (see IsSemigroup (51.1-1)) then AsSemigroup returns this semigroup. Otherwise fail is returned. 51.1-7 AsSubsemigroup AsSubsemigroup( D, C )  operation Let D be a domain and C a collection. If C is a subset of D that forms a semigroup then AsSubsemigroup returns this semigroup, with parent D. Otherwise fail is returned. 51.1-8 GeneratorsOfSemigroup GeneratorsOfSemigroup( S )  attribute Semigroup generators of a semigroup D are the same as magma generators, see GeneratorsOfMagma (35.4-1).  Example  gap> GeneratorsOfSemigroup(s); [ Transformation( [ 2, 3, 4, 1 ] ), Transformation( [ 2, 2 ] ) ] gap> GeneratorsOfSemigroup(t); [ Transformation( [ 2, 3, 4, 1 ] ) ]  51.1-9 IsGeneratorsOfSemigroup IsGeneratorsOfSemigroup( C )  property This property reflects whether the list or collection C generates a semigroup. IsAssociativeElementCollection (31.15-1) implies  IsGeneratorsOfSemigroup, but is not used directly in semigroup code, because of conflicts with matrices.  Example  gap> IsGeneratorsOfSemigroup([Transformation([2,3,1])]); true  51.1-10 FreeSemigroup FreeSemigroup( [wfilt, ]rank[, name] )  function FreeSemigroup( [wfilt, ]name1[, name2[, ...]] )  function FreeSemigroup( [wfilt, ]names )  function FreeSemigroup( [wfilt, ]infinity[, name][, init] )  function FreeSemigroup returns a free semigroup. The number of generators, and the labels given to the generators, can be specified in several different ways. Warning: the labels of generators are only an aid for printing, and do not necessarily distinguish generators; see the examples at the end for more information.  1: For a given rank, and an optional generator name prefix  Called with a positive integer rank, FreeSemigroup returns a free semigroup on rank generators. The optional argument name must be a string; its default value is "s". If name is not given but the generatorNames option is, then this option is respected as described in Section 50.1-16. Otherwise, the generators of the returned free semigroup are labelled name1, ..., namek, where k is the value of rank. 2: For given generator names Called with various (at least one) nonempty strings, FreeSemigroup returns a free semigroup on as many generators as arguments, which are labelled name1, name2, etc. 3: For a given list of generator names Called with a nonempty finite list names of nonempty strings, FreeSemigroup returns a free semigroup on Length(names) generators, whose i-th generator is labelled names[i].  4: For the rank infinity, an optional default generator name prefix, and an optional finite list of generator names  Called in the fourth form, FreeSemigroup returns a free semigroup on infinitely many generators. The optional argument name must be a string; its default value is "s", and the optional argument init must be a finite list of nonempty strings; its default value is an empty list. The generators are initially labelled according to the list init, followed by namei for each i in the range from Length(init)+1 to infinity; such a label is not allowed to appear in init. If the optional first argument wfilt is given, then it must be either IsSyllableWordsFamily, IsLetterWordsFamily, IsWLetterWordsFamily, or IsBLetterWordsFamily. This filter specifies the representation used for the elements of the free semigroup (see 37.6). If no such filter is given, a letter representation is used. For more on associative words see Chapter 37.  Example  gap> f1 := FreeSemigroup( 3 );  gap> f2 := FreeSemigroup( 3 , "generator" );  gap> f3 := FreeSemigroup( "gen1" , "gen2" );  gap> f4 := FreeSemigroup( ["gen1" , "gen2"] );  gap> FreeSemigroup( 3 : generatorNames := "boom" );  gap> FreeSemigroup( 2 : generatorNames := [ "u", "v", "w" ] );  gap> FreeSemigroup( infinity ) ;  gap> F := FreeSemigroup( infinity, "g", [ "a", "b" ]);  gap> GeneratorsOfSemigroup( F ){[1..4]}; [ a, b, g3, g4 ] gap> GeneratorsOfSemigroup( FreeSemigroup( infinity, "gen" ) ){[1..3]}; [ gen1, gen2, gen3 ] gap> GeneratorsOfSemigroup( FreeSemigroup( infinity, [ "f" ] ) ){[1..3]}; [ f, s2, s3 ] gap> FreeSemigroup(IsSyllableWordsFamily, 5);   Each free object defines a unique alphabet (and a unique family of words). Its generators are the letters of this alphabet, thus words of length one.  Example  gap> FreeSemigroup( 5 );  gap> FreeMonoid( "a", "b" );  gap> FreeGroup( infinity );  gap> FreeSemigroup( "x", "y" );  gap> FreeMonoid( 7 );   Remember that names are just a help for printing and do not necessarily distinguish letters. It is possible to create arbitrarily weird situations by choosing strange names for the letters.  Example  gap> f := FreeGroup( "x", "x" );  gap> gens := GeneratorsOfGroup( f ); [ x, x ] gap> gens[1] = gens[2]; false gap> f:= FreeGroup( "f1*f2", "f2^-1", "Group( [ f1, f2 ] )" );  gap> gens:= GeneratorsOfGroup( f );; gap> gens[1] * gens[2]; f1*f2*f2^-1 gap> gens[1] / gens[3]; f1*f2*Group( [ f1, f2 ] )^-1 gap> gens[3] / gens[1] / gens[2]; Group( [ f1, f2 ] )*f1*f2^-1*f2^-1^-1  51.1-11 SemigroupByMultiplicationTable SemigroupByMultiplicationTable( A )  function returns the semigroup whose multiplication is defined by the square matrix A (see MagmaByMultiplicationTable (35.3-1)) if such a semigroup exists. Otherwise fail is returned.  Example  gap> SemigroupByMultiplicationTable([[1,2,3],[2,3,1],[3,1,2]]);  gap> SemigroupByMultiplicationTable([[1,2,3],[2,3,1],[3,2,1]]); fail  51.2 Monoids 51.2-1 IsMonoid IsMonoid( D )  Synonym A monoid is a magma-with-one (see 35) with associative multiplication. 51.2-2 Monoid Monoid( gen1, gen2, ... )  function Monoid( gens[, id] )  function In the first form, Monoid returns the monoid generated by the arguments gen1, gen2, ..., that is, the closure of these elements under multiplication and taking the 0-th power. In the second form, Monoid returns the monoid generated by the elements in the homogeneous list gens; a square matrix as only argument is treated as one generator, not as a list of generators. In the second form, the identity element id may be given as the second argument. It is not checked whether the underlying multiplication is associative, use MagmaWithOne (35.2-2) and IsAssociative (35.4-7) if you want to check whether a magma-with-one is in fact a monoid. 51.2-3 Submonoid Submonoid( M, gens )  function SubmonoidNC( M, gens )  function are just synonyms of SubmagmaWithOne (35.2-8) and SubmagmaWithOneNC (35.2-8), respectively. 51.2-4 MonoidByGenerators MonoidByGenerators( gens[, one] )  operation is the underlying operation of Monoid (51.2-2). 51.2-5 AsMonoid AsMonoid( C )  operation If C is a collection whose elements form a monoid, then AsMonoid returns this monoid. Otherwise fail is returned. 51.2-6 AsSubmonoid AsSubmonoid( D, C )  operation Let D be a domain and C a collection. If C is a subset of D that forms a monoid then AsSubmonoid returns this monoid, with parent D. Otherwise fail is returned. 51.2-7 GeneratorsOfMonoid GeneratorsOfMonoid( M )  attribute Monoid generators of a monoid M are the same as magma-with-one generators (see GeneratorsOfMagmaWithOne (35.4-2)). 51.2-8 TrivialSubmonoid TrivialSubmonoid( M )  attribute is just a synonym for TrivialSubmagmaWithOne (35.4-13). 51.2-9 FreeMonoid FreeMonoid( [wfilt, ]rank[, name] )  function FreeMonoid( [wfilt][,] [name1[, name2[, ...]]] )  function FreeMonoid( [wfilt, ]names )  function FreeMonoid( [wfilt, ]infinity[, name][, init] )  function FreeMonoid returns a free monoid. The number of generators, and the labels given to the generators, can be specified in several different ways. Warning: the labels of generators are only an aid for printing, and do not necessarily distinguish generators; see the examples at the end of FreeSemigroup (51.1-10) for more information.  1: For a given rank, and an optional generator name prefix  Called with a nonnegative integer rank, FreeMonoid returns a free monoid on rank generators. The optional argument name must be a string; its default value is "m". If name is not given but the generatorNames option is, then this option is respected as described in Section 50.1-16. Otherwise, the generators of the returned free monoid are labelled name1, ..., namek, where k is the value of rank. 2: For given generator names Called with various nonempty strings, FreeMonoid returns a free monoid on as many generators as arguments, which are labelled name1, name2, etc. 3: For a given list of generator names Called with a finite list names of nonempty strings, FreeMonoid returns a free monoid on Length(names) generators, whose i-th generator is labelled names[i].  4: For the rank infinity, an optional default generator name prefix, and an optional finite list of generator names  Called in the fourth form, FreeMonoid returns a free monoid on infinitely many generators. The optional argument name must be a string; its default value is "m", and the optional argument init must be a finite list of nonempty strings; its default value is an empty list. The generators are initially labelled according to the list init, followed by namei for each i in the range from Length(init)+1 to infinity. If the optional first argument wfilt is given, then it must be either IsSyllableWordsFamily, IsLetterWordsFamily, IsWLetterWordsFamily, or IsBLetterWordsFamily. This filter specifies the representation used for the elements of the free monoid (see 37.6). If no such filter is given, a letter representation is used. For more on associative words see Chapter 37.  Example  gap> FreeMonoid(5);  gap> FreeMonoid(4, "gen");  gap> FreeMonoid(3 : generatorNames := "turbo");  gap> FreeMonoid(2 : generatorNames := ["u", "v", "w"]);  gap> FreeMonoid(); FreeMonoid(0); FreeMonoid([]);    gap> FreeMonoid("a", "b", "c");  gap> FreeMonoid(["x", "y"]);  gap> FreeMonoid(infinity);  gap> F := FreeMonoid(infinity, "g", ["a", "b"]);  gap> GeneratorsOfMonoid(F){[1..4]}; [ a, b, g3, g4 ] gap> GeneratorsOfMonoid(FreeMonoid(infinity, "gen")){[1..3]}; [ gen1, gen2, gen3 ] gap> GeneratorsOfMonoid(FreeMonoid(infinity, [ "f", "g" ])){[1..3]}; [ f, g, m3 ] gap> FreeMonoid(IsSyllableWordsFamily, 50);   51.2-10 MonoidByMultiplicationTable MonoidByMultiplicationTable( A )  function returns the monoid whose multiplication is defined by the square matrix A (see MagmaByMultiplicationTable (35.3-1)) if such a monoid exists. Otherwise fail is returned.  Example  gap> MonoidByMultiplicationTable([[1,2,3],[2,3,1],[3,1,2]]);  gap> MonoidByMultiplicationTable([[1,2,3],[2,3,1],[1,3,2]]); fail  51.3 Inverse semigroups and monoids 51.3-1 InverseSemigroup InverseSemigroup( obj1, obj2, ... )  function Returns: An inverse semigroup. If obj1, obj2, ... are (any combination) of associative elements with unique semigroup inverses, semigroups of such elements, or collections of such elements, then InverseSemigroup returns the inverse semigroup generated by the union of obj1, obj2, .... This equals the semigroup generated by the union of obj1, obj2, ... and their inverses. For example if S and T are inverse semigroups, then InverseSemigroup(S, f, Idempotents(T)); is the inverse semigroup generated by Union(GeneratorsOfInverseSemigroup(S), [f], Idempotents(T)));. As present, the only associative elements with unique semigroup inverses, which do not always generate a group, are partial permutations; see Chapter 54.  Example  gap> S := InverseSemigroup( > PartialPerm( [ 1, 2, 3, 6, 8, 10 ], [ 2, 6, 7, 9, 1, 5 ] ) );; gap> f := PartialPerm( [ 1, 2, 3, 4, 5, 8, 10 ],  > [ 7, 1, 4, 3, 2, 6, 5 ] );; gap> S := InverseSemigroup(S, f, Idempotents(SymmetricInverseSemigroup(5)));  gap> Size(S); 1233  51.3-2 InverseMonoid InverseMonoid( obj1, obj2, ... )  function Returns: An inverse monoid. If obj1, obj2, ... are (any combination) of associative elements with unique semigroup inverses, semigroups of such elements, or collections of such elements, then InverseMonoid returns the inverse monoid generated by the union of obj1, obj2, .... This equals the monoid generated by the union of obj1, obj2, ... and their inverses. As present, the only associative elements with unique semigroup inverses are partial permutations; see Chapter 54. For example if S and T are inverse monoids, then InverseMonoid(S, f, Idempotents(T)); is the inverse monoid generated by Union(GeneratorsOfInverseMonoid(S), [f], Idempotents(T)));.  Example  gap> S := InverseMonoid( > PartialPerm( [ 1, 2, 3, 6, 8, 10 ], [ 2, 6, 7, 9, 1, 5 ] ) );; gap> f := PartialPerm( [ 1, 2, 3, 4, 5, 8, 10 ],  > [ 7, 1, 4, 3, 2, 6, 5 ] );; gap> S := InverseMonoid(S, f, Idempotents(SymmetricInverseSemigroup(5)));  gap> Size(S); 1243  51.3-3 GeneratorsOfInverseSemigroup GeneratorsOfInverseSemigroup( S )  attribute Returns: The generators of an inverse semigroup. If S is an inverse semigroup, then GeneratorsOfInverseSemigroup returns the generators used to define S, i.e. an inverse semigroup generating set for S. The value of GeneratorsOfSemigroup(S), for an inverse semigroup S, is the union of inverse semigroup generator and their inverses. So, S is the semigroup, as opposed to inverse semigroup, generated by the elements of GeneratorsOfInverseSemigroup(S) and their inverses. If S is an inverse monoid, then GeneratorsOfInverseSemigroup returns the generators used to define S, as described above, and the identity of S.  Example  gap> S:=InverseMonoid( >  PartialPerm( [ 1, 2 ], [ 1, 4 ] ), >  PartialPerm( [ 1, 2, 4 ], [ 3, 4, 1 ] ) );; gap> GeneratorsOfSemigroup(S); [ , [2,4](1), [2,4,1,3],   [4,2](1), [3,1,4,2] ] gap> GeneratorsOfInverseSemigroup(S); [ [2,4](1), [2,4,1,3], ] gap> GeneratorsOfMonoid(S); [ [2,4](1), [2,4,1,3], [4,2](1), [3,1,4,2] ]  51.3-4 GeneratorsOfInverseMonoid GeneratorsOfInverseMonoid( S )  attribute Returns: The generators of an inverse monoid. If S is an inverse monoid, then GeneratorsOfInverseMonoid returns the generators used to define S, i.e. an inverse monoid generating set for S. There are four different possible generating sets which define an inverse monoid. More precisely, an inverse monoid can be generated as an inverse monoid, inverse semigroup, monoid, or semigroup. The different generating sets in each case can be obtained using GeneratorsOfInverseMonoid, GeneratorsOfInverseSemigroup (51.3-3), GeneratorsOfMonoid (51.2-7), and GeneratorsOfSemigroup (51.1-8), respectively.  Example  gap> S:=InverseMonoid( >  PartialPerm( [ 1, 2 ], [ 1, 4 ] ), >  PartialPerm( [ 1, 2, 4 ], [ 3, 4, 1 ] ) );; gap> GeneratorsOfInverseMonoid(S); [ [2,4](1), [2,4,1,3] ]  51.3-5 IsInverseSubsemigroup IsInverseSubsemigroup( S, T )  operation Returns: true or false. If the semigroup T is an inverse subsemigroup of the semigroup S, then this operation returns true.  Example  gap> T:=InverseSemigroup(RandomPartialPerm(4));; gap> IsInverseSubsemigroup(SymmetricInverseSemigroup(4), T);  true 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> IsInverseSubsemigroup(FullTransformationSemigroup(8), T); true  51.4 Properties of Semigroups The following functions determine information about semigroups. 51.4-1 IsRegularSemigroup IsRegularSemigroup( S )  property returns true if S is regular, i.e., if every D-class of S is regular. 51.4-2 IsRegularSemigroupElement IsRegularSemigroupElement( S, x )  operation returns true if x has a general inverse in S, i.e., there is an element y ∈ S such that x y x = x and y x y = y. 51.4-3 InversesOfSemigroupElement InversesOfSemigroupElement( S, x )  operation Returns: A list of the inverses of an element of a semigroup. InversesOfSemigroupElement returns a list of the inverses of the element x in the semigroup S. An element y in S is an inverse of x if x*y*x=x and y*x*y=y. The element x has an inverse if and only if x is a regular element of S.  Example  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])]);  gap> x := Transformation([3, 1, 4, 2, 5, 2, 1, 6, 1]);; gap> InversesOfSemigroupElement(S, x); [ ] gap> IsRegularSemigroupElement(S, x); false gap> x := Transformation([1, 9, 7, 5, 5, 1, 9, 5, 1]);; gap> Set(InversesOfSemigroupElement(S, x)); [ Transformation( [ 1, 2, 3, 5, 5, 1, 3, 5, 2 ] ),   Transformation( [ 1, 5, 1, 1, 5, 1, 3, 1, 2 ] ),   Transformation( [ 1, 5, 1, 2, 5, 1, 3, 2, 2 ] ) ] gap> IsRegularSemigroupElement(S, x); true gap> S := ReesZeroMatrixSemigroup(Group((1,2,3)), >  [[(), ()], [(), 0], [(), (1,2,3)]]);; gap> x := ReesZeroMatrixSemigroupElement(S, 2, (1,2,3), 3);; gap> InversesOfSemigroupElement(S, x); [ (1,(1,2,3),3), (1,(1,3,2),1), (2,(),3), (2,(1,2,3),1) ]  51.4-4 IsSimpleSemigroup IsSimpleSemigroup( S )  property is true if and only if the semigroup S has no proper ideals. 51.4-5 IsZeroSimpleSemigroup IsZeroSimpleSemigroup( S )  property is true if and only if the semigroup has no proper ideals except for 0, where S is a semigroup with zero. If the semigroup does not find its zero, then a break-loop is entered. 51.4-6 IsZeroGroup IsZeroGroup( S )  property is true if and only if the semigroup S is a group with zero adjoined. 51.4-7 IsReesCongruenceSemigroup IsReesCongruenceSemigroup( S )  property returns true if S is a Rees Congruence semigroup, that is, if all congruences of S are Rees Congruences. 51.4-8 IsInverseSemigroup IsInverseSemigroup( S )  property IsInverseMonoid( S )  Category Returns: true or false. A semigroup S is an inverse semigroup if every element x in S has a unique semigroup inverse, that is, a unique element y in S such that x*y*x=x and y*x*y=y. A monoid that happens to be an inverse semigroup is called an inverse monoid; see IsMonoid (51.2-1).  Example  gap> S := 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(S); true  51.5 Ideals of semigroups Ideals of semigroups are the same as ideals of the semigroup when considered as a magma. For documentation on ideals for magmas, see Magma (35.2-1). 51.5-1 SemigroupIdealByGenerators SemigroupIdealByGenerators( S, gens )  operation S is a semigroup, gens is a list of elements of S. Returns the two-sided ideal of S generated by gens. 51.5-2 ReesCongruenceOfSemigroupIdeal ReesCongruenceOfSemigroupIdeal( I )  attribute A two sided ideal I of a semigroup S defines a congruence on S given by ∆ ∪ I × I. 51.5-3 IsLeftSemigroupIdeal IsLeftSemigroupIdeal( I )  property IsRightSemigroupIdeal( I )  property IsSemigroupIdeal( I )  property Categories of semigroup ideals. 51.6 Congruences on semigroups An equivalence or a congruence on a semigroup is the equivalence or congruence on the semigroup considered as a magma. So, to deal with equivalences and congruences on semigroups, magma functions are used. For documentation on equivalences and congruences on magmas, see Magma (35.2-1). 51.6-1 IsSemigroupCongruence IsSemigroupCongruence( c )  property a magma congruence c on a semigroup. 51.6-2 IsReesCongruence IsReesCongruence( c )  property returns true if and only if the congruence c has at most one nonsingleton congruence class. 51.7 Quotients Given a semigroup and a congruence on the semigroup, one can construct a new semigroup: the quotient semigroup. The following functions deal with quotient semigroups in GAP. For a semigroup S, elements of a quotient semigroup are equivalence classes of elements of the QuotientSemigroupPreimage (51.7-3) value under the congruence given by the value of QuotientSemigroupCongruence (51.7-3). It is probably most useful for calculating the elements of the equivalence classes by using Elements (30.3-11) or by looking at the images of elements of QuotientSemigroupPreimage (51.7-3) under the map returned by QuotientSemigroupHomomorphism (51.7-3), which maps the QuotientSemigroupPreimage (51.7-3) value to S. For intensive computations in a quotient semigroup, it is probably worthwhile finding another representation as the equality test could involve enumeration of the elements of the congruence classes being compared. 51.7-1 IsQuotientSemigroup IsQuotientSemigroup( S )  Category is the category of semigroups constructed from another semigroup and a congruence on it. 51.7-2 HomomorphismQuotientSemigroup HomomorphismQuotientSemigroup( cong )  function for a congruence cong and a semigroup S. Returns the homomorphism from S to the quotient of S by cong. 51.7-3 QuotientSemigroupPreimage QuotientSemigroupPreimage( S )  attribute QuotientSemigroupCongruence( S )  attribute QuotientSemigroupHomomorphism( S )  attribute for a quotient semigroup S. 51.8 Green's Relations Green's equivalence relations play a very important role in semigroup theory. In this section we describe how they can be used in GAP. The five Green's relations are R, L, J, H, D: two elements x, y from a semigroup S are R-related if and only if xS^1 = yS^1, L-related if and only if S^1 x = S^1 y and J-related if and only if S^1 xS^1 = S^1 yS^1; finally, H = R ∧ L, and D = R ∘ L. Recall that relations R, L and J induce a partial order among the elements of the semigroup S: for two elements x, y from S, we say that x is less than or equal to y in the order on R if xS^1 ⊆ yS^1; similarly, x is less than or equal to y under L if S^1x ⊆ S^1y; finally x is less than or equal to y under J if S^1 xS^1 ⊆ S^1 tS^1. We extend this preorder to a partial order on equivalence classes in the natural way. 51.8-1 GreensRRelation GreensRRelation( semigroup )  attribute GreensLRelation( semigroup )  attribute GreensJRelation( semigroup )  attribute GreensDRelation( semigroup )  attribute GreensHRelation( semigroup )  attribute The Green's relations (which are equivalence relations) are attributes of the semigroup semigroup. 51.8-2 IsGreensRelation IsGreensRelation( bin-relation )  filter IsGreensRRelation( equiv-relation )  filter IsGreensLRelation( equiv-relation )  filter IsGreensJRelation( equiv-relation )  filter IsGreensHRelation( equiv-relation )  filter IsGreensDRelation( equiv-relation )  filter Categories for the Green's relations. 51.8-3 IsGreensClass IsGreensClass( equiv-class )  filter IsGreensRClass( equiv-class )  filter IsGreensLClass( equiv-class )  filter IsGreensJClass( equiv-class )  filter IsGreensHClass( equiv-class )  filter IsGreensDClass( equiv-class )  filter return true if the equivalence class equiv-class is a Green's class of any type, or of R, L, J, H, D type, respectively, or false otherwise. 51.8-4 IsGreensLessThanOrEqual IsGreensLessThanOrEqual( C1, C2 )  operation returns true if the Green's class C1 is less than or equal to C2 under the respective ordering (as defined above), and false otherwise. Only defined for R, L and J classes. 51.8-5 RClassOfHClass RClassOfHClass( H )  attribute LClassOfHClass( H )  attribute are attributes reflecting the natural ordering over the various Green's classes. RClassOfHClass and LClassOfHClass return the R and L classes, respectively, in which an H class is contained. 51.8-6 EggBoxOfDClass EggBoxOfDClass( Dclass )  attribute returns for a Green's D class Dclass a matrix whose rows represent R classes and columns represent L classes. The entries are the H classes. 51.8-7 DisplayEggBoxOfDClass DisplayEggBoxOfDClass( Dclass )  function displays a picture of the D class Dclass, as an array of 1s and 0s. A 1 represents a group H class. 51.8-8 GreensRClassOfElement GreensRClassOfElement( S, a )  operation GreensLClassOfElement( S, a )  operation GreensDClassOfElement( S, a )  operation GreensJClassOfElement( S, a )  operation GreensHClassOfElement( S, a )  operation Creates the X class of the element a in the semigroup S where X is one of L, R, D, J, or H. 51.8-9 GreensRClasses GreensRClasses( S )  attribute GreensLClasses( S )  attribute GreensHClasses( S )  attribute GreensJClasses( S )  attribute GreensDClasses( S )  attribute If S is a semigroup, then these attributes return the Green's R-, L-, H-, J-, or D-classes, respectively for the semigroup S. Additionally, if S is a Green's D-class of a semigroup, then GreensRClasses and GreensLClasses return the Green's R- or L-classes of the semigroup, respectively, contained in the D-class S; if S is a Green's D-, R-, or L-class of a semigroup, then GreensHClasses returns the Green's H-classes of the semigroup contained in the Green's class S. EquivalenceClasses (33.7-3) for a Green's relation lead to one of these functions. 51.8-10 GroupHClassOfGreensDClass GroupHClassOfGreensDClass( Dclass )  attribute for a D class Dclass of a semigroup, returns a group H class of the D class, or fail if there is no group H class. 51.8-11 IsGroupHClass IsGroupHClass( Hclass )  property returns true if the Green's H class Hclass is a group, which in turn is true if and only if Hclass^2 intersects Hclass. 51.8-12 IsRegularDClass IsRegularDClass( Dclass )  property returns true if the Greens D class Dclass is regular. A D class is regular if and only if each of its elements is regular, which in turn is true if and only if any one element of Dclass is regular. Idempotents are regular since eee = e so it follows that a Green's D class containing an idempotent is regular. Conversely, it is true that a regular D class must contain at least one idempotent. (See [How76, Prop. 3.2].) 51.8-13 DisplaySemigroup DisplaySemigroup( S )  operation Produces a convenient display of a transformation semigroup's D-Class structure. Let S be a transformation semigroup of degree n. Then for each r≤ n, we show all D-classes of rank r. A regular D-class with a single H-class of size 120 appears as  Example  *[H size = 120, 1 L-class, 1 R-class]   (the * denoting regularity). 51.9 Rees Matrix Semigroups In this section, we describe the functions in GAP for Rees matrix and 0-matrix semigroups and their subsemigroups. The importance of these semigroups lies in the fact that Rees matrix semigroups over groups are exactly the completely simple semigroups, and Rees 0-matrix semigroups over groups are the completely 0-simple semigroups. Let I and J be sets, let S be a semigroup, and let P=(p_ji)_j∈ J, i∈ I be a |J|× |I| matrix with entries in S. Then the Rees matrix semigroup with underlying semigroup S and matrix P is just the direct product I× S × J with multiplication defined by (i, s, j)(k, t, l)=(i,s\cdot p_{j,k}\cdot t, l).  Rees 0-matrix semigroups are defined as follows. If I, J, S, and P are as above and 0 denotes a new element, then the Rees 0-matrix semigroup with underlying semigroup S and matrix P is (I× S× J)∪ {0} with multiplication defined by (i, s, j)(k, t, l)=(i, s\cdot p_{j,k}\cdot t, l)  when p_j,k is not 0 and 0 if p_j,k is 0. If R is a Rees matrix or 0-matrix semigroup, then the rows of R is the index set I, the columns of R is the index set J, the semigroup S is the underlying semigroup of R, and the matrix P is the matrix of S. Thoroughout this section, wherever the distinction is unimportant, we will refer to Rees matrix or 0-matrix semigroups collectively as Rees matrix semigroups. Multiplication of elements of a Rees matrix semigroup obviously depends on the matrix used to create the semigroup. Hence elements of a Rees matrix semigroup can only be created with reference to the semigroup to which they belong. More specifically, every collection or semigroup of Rees matrix semigroup elements is created from a specific Rees matrix semigroup, which contains the whole family of its elements. So, it is not possible to multiply or compare elements belonging to distinct Rees matrix semigroups, since they belong to different families. For example, this situation is similar to free groups, but it is different to permutations, which belong to a single family, and where arbitrary permutations can be compared and multiplied without reference to any group containing them. A subsemigroup of a Rees matrix semigroup is not necessarily a Rees matrix semigroup. Every semigroup consisting of elements of a Rees matrix semigroup satisfies the property IsReesMatrixSubsemigroup (51.9-6) and every semigroup of Rees 0-matrix semigroup elements satisfies IsReesZeroMatrixSubsemigroup (51.9-6). Rees matrix and 0-matrix semigroups can be created using the operations ReesMatrixSemigroup (51.9-1) and ReesZeroMatrixSemigroup (51.9-1), respectively, from an underlying semigroup and a matrix. Rees matrix semigroups created in this way contain the whole family of their elements. Every element of a Rees matrix semigroup belongs to a unique semigroup created in this way; every subsemigroup of a Rees matrix semigroup is a subsemigroup of a unique semigroup created in this way. Subsemigroups of Rees matrix semigroups can also be created by specifying generators. A subsemigroup of a Rees matrix semigroup I× U× J satisfies IsReesMatrixSemigroup (51.9-7) if and only if it is equal to I'× U'× J' where I'⊆ I, J'⊆ J, and U' is a subsemigroup of U. The analogous statements holds for Rees 0-matrix semigroups. It is not necessarily the case that a simple subsemigroups of Rees matrix semigroups satisfies IsReesMatrixSemigroup (51.9-7). A Rees matrix semigroup is simple if and only if its underlying semigroup is simple. A finite semigroup is simple if and only if it is isomorphic to a Rees matrix semigroup over a group; this isomorphism can be obtained explicitly using IsomorphismReesMatrixSemigroup (51.9-3). Similarly, 0-simple subsemigroups of Rees 0-matrix semigroups do not have to satisfy IsReesZeroMatrixSemigroup (51.9-7). A Rees 0-matrix semigroup with more than 2 elements is 0-simple if and only if every row and every column of its matrix contains a non-zero entry, and its underlying semigroup is simple. A finite semigroup is 0-simple if and only if it is isomorphic to a Rees 0-matrix semigroup over a group; again this isomorphism can be found by using IsomorphismReesZeroMatrixSemigroup (51.9-3). Elements of a Rees matrix or 0-matrix semigroup belong to the categories IsReesMatrixSemigroupElement (51.9-4) and IsReesZeroMatrixSemigroupElement (51.9-4), respectively. Such elements can be created directly using the functions ReesMatrixSemigroupElement (51.9-5) and ReesZeroMatrixSemigroupElement (51.9-5). A semigroup in GAP can either satisfies IsReesMatrixSemigroup (51.9-7) or IsReesZeroMatrixSemigroup (51.9-7) but not both. 51.9-1 ReesMatrixSemigroup ReesMatrixSemigroup( S, mat )  operation ReesZeroMatrixSemigroup( S, mat )  operation Returns: A Rees matrix or 0-matrix semigroup. When S is a semigroup and mat is an m by n matrix with entries in S, the function ReesMatrixSemigroup returns the n by m Rees matrix semigroup over S with multiplication defined by mat. The arguments of ReesZeroMatrixSemigroup should be a semigroup S and an m by n matrix mat with entries in S or equal to the integer 0. ReesZeroMatrixSemigroup returns the n by m Rees 0-matrix semigroup over S with multiplication defined by mat. In GAP a Rees 0-matrix semigroup always contains a multiplicative zero element, regardless of whether there are any entries in mat which are equal to 0.  Example  gap> G:=Random(AllGroups(Size, 32));; gap> mat:=List([1..5], x-> List([1..3], y-> Random(G)));; gap> S:=ReesMatrixSemigroup(G, mat); > gap> mat:=[[(), 0, (), ()], [0, 0, 0, 0]];; gap> S:=ReesZeroMatrixSemigroup(DihedralGroup(IsPermGroup, 8), mat);   51.9-2 ReesMatrixSubsemigroup ReesMatrixSubsemigroup( R, I, U, J )  operation ReesZeroMatrixSubsemigroup( R, I, U, J )  operation Returns: A Rees matrix or 0-matrix subsemigroup. The arguments of ReesMatrixSubsemigroup should be a Rees matrix semigroup R, subsets I and J of the rows and columns of R, respectively, and a subsemigroup U of the underlying semigroup of R. ReesMatrixSubsemigroup returns the subsemigroup of R generated by the direct product of I, U, and J. The usage and returned value of ReesZeroMatrixSubsemigroup is analogous when R is a Rees 0-matrix semigroup.  Example  gap> G:=CyclicGroup(IsPermGroup, 1007);; gap> mat:=[[(), 0, 0], [0, (), 0], [0, 0, ()],  > [(), (), ()], [0, 0, ()]];; gap> R:=ReesZeroMatrixSemigroup(G, mat); > gap> ReesZeroMatrixSubsemigroup(R, [1,3], G, [1..5]); >  51.9-3 IsomorphismReesMatrixSemigroup IsomorphismReesMatrixSemigroup( S )  attribute IsomorphismReesZeroMatrixSemigroup( S )  attribute Returns: An isomorphism. Every finite simple semigroup is isomorphic to a Rees matrix semigroup over a group, and every finite 0-simple semigroup is isomorphic to a Rees 0-matrix semigroup over a group. If the argument S is a simple semigroup, then IsomorphismReesMatrixSemigroup returns an isomorphism to a Rees matrix semigroup over a group. If S is not simple, then IsomorphismReesMatrixSemigroup returns an error. If the argument S is a 0-simple semigroup, then IsomorphismReesZeroMatrixSemigroup returns an isomorphism to a Rees 0-matrix semigroup over a group. If S is not 0-simple, then IsomorphismReesZeroMatrixSemigroup returns an error. See IsSimpleSemigroup (51.4-4) and IsZeroSimpleSemigroup (51.4-5).  Example  gap> S := Semigroup(Transformation([2, 1, 1, 2, 1]),  >  Transformation([3, 4, 3, 4, 4]),  >  Transformation([3, 4, 3, 4, 3]),  >  Transformation([4, 3, 3, 4, 4]));; gap> IsSimpleSemigroup(S); true gap> Range(IsomorphismReesMatrixSemigroup(S));  gap> mat := [[(), 0, 0],  >  [0, (), 0],  >  [0, 0, ()]];; gap> R := ReesZeroMatrixSemigroup(Group((1,2,4,5,6)), mat);  gap> U := ReesZeroMatrixSubsemigroup(R, [1, 2], Group(()), [2, 3]);  gap> IsZeroSimpleSemigroup(U); false gap> U := ReesZeroMatrixSubsemigroup(R, [2, 3], Group(()), [2, 3]);  gap> IsZeroSimpleSemigroup(U); true gap> Rows(U); Columns(U); [ 2, 3 ] [ 2, 3 ] gap> V := Range(IsomorphismReesZeroMatrixSemigroup(U));  gap> Rows(V); Columns(V);  [ 1, 2 ] [ 1, 2 ]  51.9-4 IsReesMatrixSemigroupElement IsReesMatrixSemigroupElement( elt )  Category IsReesZeroMatrixSemigroupElement( elt )  Category Returns: true or false. Every element of a Rees matrix semigroup belongs to the category IsReesMatrixSemigroupElement, and every element of a Rees 0-matrix semigroup belongs to the category IsReesZeroMatrixSemigroupElement.  Example  gap> G:=Group((1,2,3));; gap> mat:=[ [ (), (1,3,2) ], [ (1,3,2), () ] ];; gap> R:=ReesMatrixSemigroup(G, mat);  gap> GeneratorsOfSemigroup(R); [ (1,(1,2,3),1), (2,(),2) ] gap> IsReesMatrixSemigroupElement(last[1]); true gap> IsReesZeroMatrixSemigroupElement(last2[1]); false  51.9-5 ReesMatrixSemigroupElement ReesMatrixSemigroupElement( R, i, x, j )  function ReesZeroMatrixSemigroupElement( R, i, x, j )  function Returns: An element of a Rees matrix or 0-matrix semigroup. The arguments of ReesMatrixSemigroupElement should be a Rees matrix subsemigroup R, elements i and j of the the rows and columns of R, respectively, and an element x of the underlying semigroup of R. ReesMatrixSemigroupElement returns the element of R with row index i, underlying element x in the underlying semigroup of R, and column index j, if such an element exist, if such an element exists. The usage of ReesZeroMatrixSemigroupElement is analogous to that of ReesMatrixSemigroupElement, when R is a Rees 0-matrix semigroup. The row i, underlying element x, and column j of an element y of a Rees matrix (or 0-matrix) semigroup can be recovered from y using y[1], y[2], and y[3], respectively.  Example  gap> G:=Group((1,2,3));; gap> mat:=[ [ 0, () ], [ (1,3,2), (1,3,2) ] ];; gap> R:=ReesZeroMatrixSemigroup(G, mat);  gap> ReesZeroMatrixSemigroupElement(R, 1, (1,2,3), 2); (1,(1,2,3),2) gap> MultiplicativeZero(R); 0  51.9-6 IsReesMatrixSubsemigroup IsReesMatrixSubsemigroup( R )  Synonym IsReesZeroMatrixSubsemigroup( R )  Synonym Returns: true or false. Every semigroup consisting of elements of a Rees matrix semigroup satisfies the property IsReesMatrixSubsemigroup and every semigroup of Rees 0-matrix semigroup elements satisfies IsReesZeroMatrixSubsemigroup. Note that a subsemigroup of a Rees matrix semigroup is not necessarily a Rees matrix semigroup.  Example  gap> G:=DihedralGroup(32);; gap> mat:=List([1..2], x-> List([1..10], x-> Random(G)));; gap> R:=ReesMatrixSemigroup(G, mat); > gap> S:=Semigroup(GeneratorsOfSemigroup(R));   gap> IsReesMatrixSubsemigroup(S);  true gap> S:=Semigroup(GeneratorsOfSemigroup(R)[1]);  gap> IsReesMatrixSubsemigroup(S); true  51.9-7 IsReesMatrixSemigroup IsReesMatrixSemigroup( R )  property IsReesZeroMatrixSemigroup( R )  property Returns: true or false. A subsemigroup of a Rees matrix semigroup I× U× J satisfies IsReesMatrixSemigroup if and only if it is equal to I'× U'× J' where I'⊆ I, J'⊆ J, and U' is a subsemigroup of U. It can be costly to check that a subsemigroup defined by generators satisfies IsReesMatrixSemigroup. The analogous statements holds for Rees 0-matrix semigroups. It is not necessarily the case that a simple subsemigroups of Rees matrix semigroups satisfies IsReesMatrixSemigroup. A Rees matrix semigroup is simple if and only if its underlying semigroup is simple. A finite semigroup is simple if and only if it is isomorphic to a Rees matrix semigroup over a group; this isomorphism can be obtained explicitly using IsomorphismReesMatrixSemigroup (51.9-3). Similarly, 0-simple subsemigroups of Rees 0-matrix semigroups do not have to satisfy IsReesZeroMatrixSemigroup. A Rees 0-matrix semigroup with more than 2 elements is 0-simple if and only if every row and every column of its matrix contains a non-zero entry, and its underlying semigroup is simple. A finite semigroup is 0-simple if and only if it is isomorphic to a Rees 0-matrix semigroup over a group; again this isomorphism can be found by using IsomorphismReesMatrixSemigroup (51.9-3).  Example  gap> G:=PSL(2,5);; gap> mat:=[ [ 0, (), 0, (2,6,3,5,4) ],  > [ (), 0, (), 0 ], [ 0, 0, 0, () ] ];; gap> R:=ReesZeroMatrixSemigroup(G, mat);  gap> IsReesZeroMatrixSemigroup(R); true gap> U:=ReesZeroMatrixSubsemigroup(R, [1..3], Group(()), [1..2]);  gap> IsReesZeroMatrixSemigroup(U); true gap> V:=Semigroup(GeneratorsOfSemigroup(U));  gap> IsReesZeroMatrixSemigroup(V); true gap> S:=Semigroup(Transformation([1,1]), Transformation([1,2]));  gap> IsSimpleSemigroup(S); false gap> mat:=[[0, One(S), 0, One(S)], [One(S), 0, One(S), 0],  > [0, 0, 0, One(S)]];; gap> R:=ReesZeroMatrixSemigroup(S, mat);; gap> U:=ReesZeroMatrixSubsemigroup(R, [1..3],  > Semigroup(Transformation([1,1])), [1..2]);  gap> V:=Semigroup(GeneratorsOfSemigroup(U));  gap> IsReesZeroMatrixSemigroup(V); true gap> T:=Semigroup( > ReesZeroMatrixSemigroupElement(R, 3, Transformation( [ 1, 1 ] ), 3),  > ReesZeroMatrixSemigroupElement(R, 2, Transformation( [ 1, 1 ] ), 2));  gap> IsReesZeroMatrixSemigroup(T); false  51.9-8 Matrix Matrix( R )  operation MatrixOfReesMatrixSemigroup( R )  attribute MatrixOfReesZeroMatrixSemigroup( R )  attribute Returns: A matrix. If R is a Rees matrix or 0-matrix semigroup, then MatrixOfReesMatrixSemigroup respectively MatrixOfReesZeroMatrixSemigroup return the matrix used to define multiplication in R. For convenience, one may also abbreviate either to Matrix. More specifically, if R is a Rees matrix or 0-matrix semigroup, which is a proper subsemigroup of another such semigroup, then Matrix returns the matrix used to define the Rees matrix (or 0-matrix) semigroup consisting of the whole family to which the elements of R belong. Thus, for example, a 1 by 1 Rees matrix semigroup can have a 65 by 15 matrix. Arbitrary subsemigroups of Rees matrix or 0-matrix semigroups do not have a matrix. Such a subsemigroup R has a matrix if and only if it satisfies IsReesMatrixSemigroup (51.9-7) or IsReesZeroMatrixSemigroup (51.9-7).  Example  gap> G:=AlternatingGroup(5);; gap> mat:=[[(), (), ()], [(), (), ()]];; gap> R:=ReesMatrixSemigroup(G, mat);  gap> Matrix(R);  [ [ (), (), () ], [ (), (), () ] ] gap> R:=ReesMatrixSubsemigroup(R, [1,2], Group(()), [2]);  gap> Matrix(R); [ [ (), (), () ], [ (), (), () ] ]  51.9-9 Rows and columns Rows( R )  attribute Columns( R )  attribute Returns: The rows or columns of R. Rows returns the rows of the Rees matrix or 0-matrix semigroup R. Note that the rows of the semigroup correspond to the columns of the matrix used to define multiplication in R. Columns returns the columns of the Rees matrix or 0-matrix semigroup R. Note that the columns of the semigroup correspond to the rows of the matrix used to define multiplication in R. Arbitrary subsemigroups of Rees matrix or 0-matrix semigroups do not have rows or columns. Such a subsemigroup R has rows and columns if and only if it satisfies IsReesMatrixSemigroup (51.9-7) or IsReesZeroMatrixSemigroup (51.9-7).  Example  gap> G:=Group((1,2,3));;  gap> mat:=List([1..100], x-> List([1..200], x->Random(G)));; gap> R:=ReesZeroMatrixSemigroup(G, mat);   gap> Rows(R); [ 1 .. 200 ] gap> Columns(R); [ 1 .. 100 ]  51.9-10 UnderlyingSemigroup UnderlyingSemigroup( R )  attribute UnderlyingSemigroup( R )  attribute Returns: A semigroup. UnderlyingSemigroup returns the underlying semigroup of the Rees matrix or 0-matrix semigroup R. Arbitrary subsemigroups of Rees matrix or 0-matrix semigroups do not have an underlying semigroup. Such a subsemigroup R has an underlying semigroup if and only if it satisfies IsReesMatrixSemigroup (51.9-7) or IsReesZeroMatrixSemigroup (51.9-7).  Example  gap> S:=Semigroup(Transformation( [ 2, 1, 1, 2, 1 ] ),  > Transformation( [ 3, 4, 3, 4, 4 ] ), Transformation([ 3, 4, 3, 4, 3 ] ), > Transformation([ 4, 3, 3, 4, 4 ] ) );; gap> R:=Range(IsomorphismReesMatrixSemigroup(S));   gap> UnderlyingSemigroup(R); Group([ (1,2) ])  51.9-11 AssociatedReesMatrixSemigroupOfDClass AssociatedReesMatrixSemigroupOfDClass( D )  attribute Returns: A Rees matrix or 0-matrix semigroup. If D is a regular D-class of a finite semigroup S, then there is a standard way of associating a Rees matrix semigroup to D. If D is a subsemigroup of S, then D is simple and hence is isomorphic to a Rees matrix semigroup. In this case, the associated Rees matrix semigroup of D is just the Rees matrix semigroup isomorphic to D. If D is not a subsemigroup of S, then we define a semigroup with elements D and a new element 0 with multiplication of x,y∈ D defined by: xy equals the product of x and y if it belongs to D and 0 if it does not. The semigroup thus defined is 0-simple and hence is isomorphic to a Rees 0-matrix semigroup. This semigroup can also be described as the Rees quotient of the ideal generated by D by it maximal subideal. The associated Rees matrix semigroup of D is just the Rees 0-matrix semigroup isomorphic to the semigroup defined above.  Example  gap> S:=FullTransformationSemigroup(5);; gap> D:=GreensDClasses(S)[3]; {Transformation( [ 1, 1, 1, 2, 3 ] )} gap> AssociatedReesMatrixSemigroupOfDClass(D);