Goto Chapter: Top 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 Bib Ind

51 Semigroups and Monoids

51.8 Green's Relations

51.8-1 GreensRRelation

51.8-2 IsGreensRelation

51.8-3 IsGreensClass

51.8-4 IsGreensLessThanOrEqual

51.8-5 RClassOfHClass

51.8-6 EggBoxOfDClass

51.8-7 DisplayEggBoxOfDClass

51.8-8 GreensRClassOfElement

51.8-9 GreensRClasses

51.8-10 GroupHClassOfGreensDClass

51.8-11 IsGroupHClass

51.8-12 IsRegularDClass

51.8-13 DisplaySemigroup

51.8-1 GreensRRelation

51.8-2 IsGreensRelation

51.8-3 IsGreensClass

51.8-4 IsGreensLessThanOrEqual

51.8-5 RClassOfHClass

51.8-6 EggBoxOfDClass

51.8-7 DisplayEggBoxOfDClass

51.8-8 GreensRClassOfElement

51.8-9 GreensRClasses

51.8-10 GroupHClassOfGreensDClass

51.8-11 IsGroupHClass

51.8-12 IsRegularDClass

51.8-13 DisplaySemigroup

51.9 Rees Matrix Semigroups

51.9-1 ReesMatrixSemigroup

51.9-2 ReesMatrixSubsemigroup

51.9-3 IsomorphismReesMatrixSemigroup

51.9-4 IsReesMatrixSemigroupElement

51.9-5 ReesMatrixSemigroupElement

51.9-6 IsReesMatrixSubsemigroup

51.9-7 IsReesMatrixSemigroup

51.9-8 Matrix

51.9-9 Rows and columns

51.9-10 UnderlyingSemigroup

51.9-11 AssociatedReesMatrixSemigroupOfDClass

51.9-1 ReesMatrixSemigroup

51.9-2 ReesMatrixSubsemigroup

51.9-3 IsomorphismReesMatrixSemigroup

51.9-4 IsReesMatrixSemigroupElement

51.9-5 ReesMatrixSemigroupElement

51.9-6 IsReesMatrixSubsemigroup

51.9-7 IsReesMatrixSemigroup

51.9-8 Matrix

51.9-9 Rows and columns

51.9-10 UnderlyingSemigroup

51.9-11 AssociatedReesMatrixSemigroupOfDClass

This chapter describes functions for creating semigroups and monoids and determining information about them.

`‣ IsSemigroup` ( D ) | ( synonym ) |

returns `true`

if the object `D` is a semigroup. A *semigroup* is a magma (see 35) with associative multiplication.

`‣ 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.

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); <transformation semigroup of degree 4 with 2 generators>

`‣ Subsemigroup` ( S, gens ) | ( function ) |

`‣ SubsemigroupNC` ( S, gens ) | ( function ) |

are just synonyms of `Submagma`

(35.2-7) and `SubmagmaNC`

(35.2-7), respectively.

gap> a:=GeneratorsOfSemigroup(s)[1]; Transformation( [ 2, 3, 4, 1 ] ) gap> t:=Subsemigroup(s,[a]); <commutative transformation semigroup of degree 4 with 1 generator>

`‣ 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.

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

`‣ SemigroupByGenerators` ( gens ) | ( operation ) |

is the underlying operation of `Semigroup`

(51.1-2).

`‣ 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.

`‣ 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.

`‣ GeneratorsOfSemigroup` ( S ) | ( attribute ) |

Semigroup generators of a semigroup `D` are the same as magma generators, see `GeneratorsOfMagma`

(35.4-1).

gap> GeneratorsOfSemigroup(s); [ Transformation( [ 2, 3, 4, 1 ] ), Transformation( [ 2, 2 ] ) ] gap> GeneratorsOfSemigroup(t); [ Transformation( [ 2, 3, 4, 1 ] ) ]

`‣ 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.

gap> IsGeneratorsOfSemigroup([Transformation([2,3,1])]); true

`‣ 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

`name``1`

, ...,`name``k`

, 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(`

generators, whose`names`)`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 namesCalled 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`name``i`

for each`i`

in the range from`Length(`

to`init`)+1`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.

gap> f1 := FreeSemigroup( 3 ); <free semigroup on the generators [ s1, s2, s3 ]> gap> f2 := FreeSemigroup( 3 , "generator" ); <free semigroup on the generators [ generator1, generator2, generator3 ]> gap> f3 := FreeSemigroup( "gen1" , "gen2" ); <free semigroup on the generators [ gen1, gen2 ]> gap> f4 := FreeSemigroup( ["gen1" , "gen2"] ); <free semigroup on the generators [ gen1, gen2 ]> gap> FreeSemigroup( 3 : generatorNames := "boom" ); <free semigroup on the generators [ boom1, boom2, boom3 ]> gap> FreeSemigroup( 2 : generatorNames := [ "u", "v", "w" ] ); <free semigroup on the generators [ u, v ]> gap> FreeSemigroup( infinity ) ; <free semigroup on the generators [ s1, s2, ... ]> gap> F := FreeSemigroup( infinity, "g", [ "a", "b" ]); <free semigroup on the generators [ 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); <free semigroup on the generators [ s1, s2, s3, s4, s5 ]>

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.

gap> FreeSemigroup( 5 ); <free semigroup on the generators [ s1, s2, s3, s4, s5 ]> gap> FreeMonoid( "a", "b" ); <free monoid on the generators [ a, b ]> gap> FreeGroup( infinity ); <free group with infinity generators> gap> FreeSemigroup( "x", "y" ); <free semigroup on the generators [ x, y ]> gap> FreeMonoid( 7 ); <free monoid on the generators [ m1, m2, m3, m4, m5, m6, m7 ]>

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.

gap> f := FreeGroup( "x", "x" ); <free group on the generators [ x, x ]> gap> gens := GeneratorsOfGroup( f ); [ x, x ] gap> gens[1] = gens[2]; false gap> f:= FreeGroup( "f1*f2", "f2^-1", "Group( [ f1, f2 ] )" ); <free group on the generators [ 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

`‣ 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.

gap> SemigroupByMultiplicationTable([[1,2,3],[2,3,1],[3,1,2]]); <semigroup of size 3, with 3 generators> gap> SemigroupByMultiplicationTable([[1,2,3],[2,3,1],[3,2,1]]); fail

`‣ IsMonoid` ( D ) | ( synonym ) |

A *monoid* is a magma-with-one (see 35) with associative multiplication.

`‣ 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.

`‣ Submonoid` ( M, gens ) | ( function ) |

`‣ SubmonoidNC` ( M, gens ) | ( function ) |

are just synonyms of `SubmagmaWithOne`

(35.2-8) and `SubmagmaWithOneNC`

(35.2-8), respectively.

`‣ MonoidByGenerators` ( gens[, one] ) | ( operation ) |

is the underlying operation of `Monoid`

(51.2-2).

`‣ AsMonoid` ( C ) | ( operation ) |

If `C` is a collection whose elements form a monoid, then `AsMonoid`

returns this monoid. Otherwise `fail`

is returned.

`‣ 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.

`‣ GeneratorsOfMonoid` ( M ) | ( attribute ) |

Monoid generators of a monoid `M` are the same as magma-with-one generators (see `GeneratorsOfMagmaWithOne`

(35.4-2)).

`‣ TrivialSubmonoid` ( M ) | ( attribute ) |

is just a synonym for `TrivialSubmagmaWithOne`

(35.4-13).

`‣ 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

`name``1`

, ...,`name``k`

, 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(`

generators, whose`names`)`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 namesCalled 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`name``i`

for each`i`

in the range from`Length(`

to`init`)+1`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.

gap> FreeMonoid(5); <free monoid on the generators [ m1, m2, m3, m4, m5 ]> gap> FreeMonoid(4, "gen"); <free monoid on the generators [ gen1, gen2, gen3, gen4 ]> gap> FreeMonoid(3 : generatorNames := "turbo"); <free monoid on the generators [ turbo1, turbo2, turbo3 ]> gap> FreeMonoid(2 : generatorNames := ["u", "v", "w"]); <free monoid on the generators [ u, v ]> gap> FreeMonoid(); FreeMonoid(0); FreeMonoid([]); <free monoid of rank zero> <free monoid of rank zero> <free monoid of rank zero> gap> FreeMonoid("a", "b", "c"); <free monoid on the generators [ a, b, c ]> gap> FreeMonoid(["x", "y"]); <free monoid on the generators [ x, y ]> gap> FreeMonoid(infinity); <free monoid with infinity generators> gap> F := FreeMonoid(infinity, "g", ["a", "b"]); <free monoid with infinity generators> 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); <free monoid with 50 generators>

`‣ 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.

gap> MonoidByMultiplicationTable([[1,2,3],[2,3,1],[3,1,2]]); <monoid of size 3, with 3 generators> gap> MonoidByMultiplicationTable([[1,2,3],[2,3,1],[1,3,2]]); fail

`‣ 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.

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))); <inverse partial perm semigroup of rank 10 with 34 generators> gap> Size(S); 1233

`‣ 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)));`

.

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))); <inverse partial perm monoid of rank 10 with 35 generators> gap> Size(S); 1243

`‣ 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(`

, for an inverse semigroup `S`)`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(`

and their inverses.`S`)

If `S` is an inverse monoid, then `GeneratorsOfInverseSemigroup`

returns the generators used to define `S`, as described above, and the identity of `S`.

gap> S:=InverseMonoid( > PartialPerm( [ 1, 2 ], [ 1, 4 ] ), > PartialPerm( [ 1, 2, 4 ], [ 3, 4, 1 ] ) );; gap> GeneratorsOfSemigroup(S); [ <identity partial perm on [ 1, 2, 3, 4 ]>, [2,4](1), [2,4,1,3], [4,2](1), [3,1,4,2] ] gap> GeneratorsOfInverseSemigroup(S); [ [2,4](1), [2,4,1,3], <identity partial perm on [ 1, 2, 3, 4 ]> ] gap> GeneratorsOfMonoid(S); [ [2,4](1), [2,4,1,3], [4,2](1), [3,1,4,2] ]

`‣ 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.

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

`‣ 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`

.

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

The following functions determine information about semigroups.

`‣ IsRegularSemigroup` ( S ) | ( property ) |

returns `true`

if `S` is regular, i.e., if every \(\mathcal{D}\)-class of `S` is regular.

`‣ 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.

`‣ 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

and `x`*y*`x`=`x``y*`

. The element `x`*y=y`x` has an inverse if and only if `x` is a regular element of `S`.

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

`‣ IsSimpleSemigroup` ( S ) | ( property ) |

is `true`

if and only if the semigroup `S` has no proper ideals.

`‣ 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.

`‣ IsZeroGroup` ( S ) | ( property ) |

is `true`

if and only if the semigroup `S` is a group with zero adjoined.

`‣ IsReesCongruenceSemigroup` ( S ) | ( property ) |

returns `true`

if `S` is a Rees Congruence semigroup, that is, if all congruences of `S` are Rees Congruences.

`‣ 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).

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

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

`‣ 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`.

`‣ ReesCongruenceOfSemigroupIdeal` ( I ) | ( attribute ) |

A two sided ideal `I` of a semigroup `S` defines a congruence on `S` given by ∆ ∪ I × I.

`‣ IsLeftSemigroupIdeal` ( I ) | ( property ) |

`‣ IsRightSemigroupIdeal` ( I ) | ( property ) |

`‣ IsSemigroupIdeal` ( I ) | ( property ) |

Categories of semigroup ideals.

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

`‣ IsSemigroupCongruence` ( c ) | ( property ) |

a magma congruence `c` on a semigroup.

`‣ IsReesCongruence` ( c ) | ( property ) |

returns `true`

if and only if the congruence `c` has at most one nonsingleton congruence class.

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.

`‣ IsQuotientSemigroup` ( S ) | ( category ) |

is the category of semigroups constructed from another semigroup and a congruence on it.

`‣ HomomorphismQuotientSemigroup` ( cong ) | ( function ) |

for a congruence `cong` and a semigroup `S`. Returns the homomorphism from `S` to the quotient of `S` by `cong`.

`‣ QuotientSemigroupPreimage` ( S ) | ( attribute ) |

`‣ QuotientSemigroupCongruence` ( S ) | ( attribute ) |

`‣ QuotientSemigroupHomomorphism` ( S ) | ( attribute ) |

for a quotient semigroup `S`.

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.

`‣ 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`.

`‣ 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.

`‣ 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.

`‣ 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.

`‣ 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.

`‣ 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.

`‣ 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.

`‣ 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.

`‣ 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.

`‣ 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.

`‣ 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`.

`‣ 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].)

`‣ 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

*[H size = 120, 1 L-class, 1 R-class]

(the `*`

denoting regularity).

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.

`‣ 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`

.

gap> G:=Random(AllSmallGroups(Size, 32));; gap> mat:=List([1..5], x-> List([1..3], y-> Random(G)));; gap> S:=ReesMatrixSemigroup(G, mat); <Rees matrix semigroup 3x5 over <pc group of size 32 with 5 generators>> gap> mat:=[[(), 0, (), ()], [0, 0, 0, 0]];; gap> S:=ReesZeroMatrixSemigroup(DihedralGroup(IsPermGroup, 8), mat); <Rees 0-matrix semigroup 4x2 over Group([ (1,2,3,4), (2,4) ])>

`‣ 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.

gap> G:=CyclicGroup(IsPermGroup, 1007);; gap> mat:=[[(), 0, 0], [0, (), 0], [0, 0, ()], > [(), (), ()], [0, 0, ()]];; gap> R:=ReesZeroMatrixSemigroup(G, mat); <Rees 0-matrix semigroup 3x5 over <permutation group of size 1007 with 1 generator>> gap> ReesZeroMatrixSubsemigroup(R, [1,3], G, [1..5]); <Rees 0-matrix semigroup 2x5 over <permutation group of size 1007 with 1 generator>>

`‣ 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).

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)); <Rees matrix semigroup 4x2 over Group([ (1,2) ])> gap> mat := [[(), 0, 0], > [0, (), 0], > [0, 0, ()]];; gap> R := ReesZeroMatrixSemigroup(Group((1,2,4,5,6)), mat); <Rees 0-matrix semigroup 3x3 over Group([ (1,2,4,5,6) ])> gap> U := ReesZeroMatrixSubsemigroup(R, [1, 2], Group(()), [2, 3]); <subsemigroup of 3x3 Rees 0-matrix semigroup with 4 generators> gap> IsZeroSimpleSemigroup(U); false gap> U := ReesZeroMatrixSubsemigroup(R, [2, 3], Group(()), [2, 3]); <subsemigroup of 3x3 Rees 0-matrix semigroup with 3 generators> gap> IsZeroSimpleSemigroup(U); true gap> Rows(U); Columns(U); [ 2, 3 ] [ 2, 3 ] gap> V := Range(IsomorphismReesZeroMatrixSemigroup(U)); <Rees 0-matrix semigroup 2x2 over Group(())> gap> Rows(V); Columns(V); [ 1, 2 ] [ 1, 2 ]

`‣ 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`

.

gap> G:=Group((1,2,3));; gap> mat:=[ [ (), (1,3,2) ], [ (1,3,2), () ] ];; gap> R:=ReesMatrixSemigroup(G, mat); <Rees matrix semigroup 2x2 over Group([ (1,2,3) ])> gap> GeneratorsOfSemigroup(R); [ (1,(1,2,3),1), (2,(),2) ] gap> IsReesMatrixSemigroupElement(last[1]); true gap> IsReesZeroMatrixSemigroupElement(last2[1]); false

`‣ 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.

gap> G:=Group((1,2,3));; gap> mat:=[ [ 0, () ], [ (1,3,2), (1,3,2) ] ];; gap> R:=ReesZeroMatrixSemigroup(G, mat); <Rees 0-matrix semigroup 2x2 over Group([ (1,2,3) ])> gap> ReesZeroMatrixSemigroupElement(R, 1, (1,2,3), 2); (1,(1,2,3),2) gap> MultiplicativeZero(R); 0

`‣ 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.

gap> G:=DihedralGroup(32);; gap> mat:=List([1..2], x-> List([1..10], x-> Random(G)));; gap> R:=ReesMatrixSemigroup(G, mat); <Rees matrix semigroup 10x2 over <pc group of size 32 with 5 generators>> gap> S:=Semigroup(GeneratorsOfSemigroup(R)); <subsemigroup of 10x2 Rees matrix semigroup with 14 generators> gap> IsReesMatrixSubsemigroup(S); true gap> S:=Semigroup(GeneratorsOfSemigroup(R)[1]); <subsemigroup of 10x2 Rees matrix semigroup with 1 generator> gap> IsReesMatrixSubsemigroup(S); true

`‣ 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).

gap> G:=PSL(2,5);; gap> mat:=[ [ 0, (), 0, (2,6,3,5,4) ], > [ (), 0, (), 0 ], [ 0, 0, 0, () ] ];; gap> R:=ReesZeroMatrixSemigroup(G, mat); <Rees 0-matrix semigroup 4x3 over Group([ (3,5)(4,6), (1,2,5) (3,4,6) ])> gap> IsReesZeroMatrixSemigroup(R); true gap> U:=ReesZeroMatrixSubsemigroup(R, [1..3], Group(()), [1..2]); <subsemigroup of 4x3 Rees 0-matrix semigroup with 4 generators> gap> IsReesZeroMatrixSemigroup(U); true gap> V:=Semigroup(GeneratorsOfSemigroup(U)); <subsemigroup of 4x3 Rees 0-matrix semigroup with 4 generators> gap> IsReesZeroMatrixSemigroup(V); true gap> S:=Semigroup(Transformation([1,1]), Transformation([1,2])); <commutative transformation monoid of degree 2 with 1 generator> 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]); <subsemigroup of 4x3 Rees 0-matrix semigroup with 6 generators> gap> V:=Semigroup(GeneratorsOfSemigroup(U)); <subsemigroup of 4x3 Rees 0-matrix semigroup with 6 generators> gap> IsReesZeroMatrixSemigroup(V); true gap> T:=Semigroup( > ReesZeroMatrixSemigroupElement(R, 3, Transformation( [ 1, 1 ] ), 3), > ReesZeroMatrixSemigroupElement(R, 2, Transformation( [ 1, 1 ] ), 2)); <subsemigroup of 4x3 Rees 0-matrix semigroup with 2 generators> gap> IsReesZeroMatrixSemigroup(T); false

`‣ 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).

gap> G:=AlternatingGroup(5);; gap> mat:=[[(), (), ()], [(), (), ()]];; gap> R:=ReesMatrixSemigroup(G, mat); <Rees matrix semigroup 3x2 over Alt( [ 1 .. 5 ] )> gap> Matrix(R); [ [ (), (), () ], [ (), (), () ] ] gap> R:=ReesMatrixSubsemigroup(R, [1,2], Group(()), [2]); <subsemigroup of 3x2 Rees matrix semigroup with 2 generators> gap> Matrix(R); [ [ (), (), () ], [ (), (), () ] ]

`‣ 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).

gap> G:=Group((1,2,3));; gap> mat:=List([1..100], x-> List([1..200], x->Random(G)));; gap> R:=ReesZeroMatrixSemigroup(G, mat); <Rees 0-matrix semigroup 200x100 over Group([ (1,2,3) ])> gap> Rows(R); [ 1 .. 200 ] gap> Columns(R); [ 1 .. 100 ]

`‣ 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).

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)); <Rees matrix semigroup 4x2 over Group([ (1,2) ])> gap> UnderlyingSemigroup(R); Group([ (1,2) ])

`‣ AssociatedReesMatrixSemigroupOfDClass` ( D ) | ( attribute ) |

Returns: A Rees matrix or 0-matrix semigroup.

If `D` is a regular \(\mathcal{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=\left\{\begin{array}{ll} x*y\ (\textrm{in }S)&\textrm{if }x*y\in D\\ 0&\textrm{if }xy\not\in D. \end{array}\right.

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.

gap> S:=FullTransformationSemigroup(5);; gap> D:=GreensDClasses(S)[3]; {Transformation( [ 1, 1, 1, 2, 3 ] )} gap> AssociatedReesMatrixSemigroupOfDClass(D); <Rees 0-matrix semigroup 25x10 over Group([ (1,2)(3,5)(4,6), (1,3) (2,4)(5,6) ])>

Goto Chapter: Top 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 Bib Ind

generated by GAPDoc2HTML