Goto Chapter: Top 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 Bib Ind
 [Top of Book]  [Contents]   [Previous Chapter]   [Next Chapter] 

13 Attributes and operations for semigroups
 13.1 Accessing the elements of a semigroup
 13.2 Cayley graphs
 13.3 Random elements of a semigroup
 13.4 Properties of elements in a semigroup
 13.5 Expressing semigroup elements as words in generators
 13.6 Generating sets
 13.7 Minimal ideals and multiplicative zeros
 13.8 Group of units and identity elements
 13.9 Idempotents
 13.10 Maximal subsemigroups
 13.11 The normalizer of a semigroup
 13.12 Attributes of transformations and transformation semigroups
 13.13 Attributes of partial perm semigroups
 13.14 Attributes of Rees (0-)matrix semigroups
 13.15 Changing the representation of a semigroup

13 Attributes and operations for semigroups

In this chapter we decribe the methods that are available in Semigroups for determining the attributes of a semigroup, and the operations which can be applied to a semigroup.

13.1 Accessing the elements of a semigroup

13.1-1 AsListCanonical
‣ AsListCanonical( S )( attribute )
‣ EnumeratorCanonical( S )( attribute )
‣ IteratorCanonical( S )( operation )

Returns: A list, enumerator, or iterator.

When the argument S is a semigroup in the representation IsEnumerableSemigroupRep (6.1-4), AsListCanonical returns a list of the elements of S in the order they are enumerated by the Froidure-Pin Algorithm. This is the same as the order used to index the elements of S in RightCayleyGraphSemigroup (13.2-1) and LeftCayleyGraphSemigroup (13.2-1).

EnumeratorCanonical and IteratorCanonical return an enumerator and an iterator where the elements are ordered in the same way as AsListCanonical. Using EnumeratorCanonical or IteratorCanonical will often use less memory than AsListCanonical, but may have slightly worse performance if the elements of the semigroup are looped over repeatedly. EnumeratorCanonical returns the same list as AsListCanonical if AsListCanonical has ever been called for S.

If S is an acting semigroup, then the value returned by AsList may not equal the value returned by AsListCanonical. AsListCanonical exists so that there is a method for obtaining the elements of S in the particular order used by RightCayleyGraphSemigroup (13.2-1) and LeftCayleyGraphSemigroup (13.2-1).

See also PositionCanonical (13.1-2).

gap> S := Semigroup(Transformation([1, 3, 2]));;
gap> AsListCanonical(S);
[ Transformation( [ 1, 3, 2 ] ), IdentityTransformation ]
gap> IteratorCanonical(S);
<iterator>
gap> EnumeratorCanonical(S);
[ Transformation( [ 1, 3, 2 ] ), IdentityTransformation ]
gap> S := Monoid([Matrix(IsBooleanMat, [[1, 0, 0],
>                                       [0, 1, 0],
>                                       [0, 1, 0]])]);
<commutative monoid of 3x3 boolean matrices with 1 generator>
gap> it := IteratorCanonical(S);
<iterator>
gap> NextIterator(it);
Matrix(IsBooleanMat, [[1, 0, 0], [0, 1, 0], [0, 0, 1]])
gap> en := EnumeratorCanonical(S);
<enumerator of <commutative monoid of 3x3 boolean matrices with 1 
 generator>>
gap> en[1];
Matrix(IsBooleanMat, [[1, 0, 0], [0, 1, 0], [0, 0, 1]])
gap> Position(en, en[1]);
1
gap> Length(en);
2

13.1-2 PositionCanonical
‣ PositionCanonical( S, x )( operation )

Returns: true or false.

When the argument S is a semigroup in the representation IsEnumerableSemigroupRep (6.1-4) and x is an element of S, PositionCanonical returns the position of x in AsListCanonical(S) or equivalently the position of x in EnumeratorCanonical(S).

See also AsListCanonical (13.1-1) and EnumeratorCanonical (13.1-1).

gap> S := FullTropicalMaxPlusMonoid(2, 3);
<monoid of 2x2 tropical max-plus matrices with 13 generators>
gap> x := Matrix(IsTropicalMaxPlusMatrix, [[1, 3], [2, 1]], 3);
Matrix(IsTropicalMaxPlusMatrix, [[1, 3], [2, 1]], 3)
gap> PositionCanonical(S, x);
234
gap> EnumeratorCanonical(S)[234] = x;
true

13.1-3 Enumerate
‣ Enumerate( S[, limit] )( operation )

Returns: A semigroup (the argument).

If S is a semigroup with representation IsEnumerableSemigroupRep (6.1-4) and limit is a positive integer, then this operation can be used to enumerate at least limit elements of S, or Size(S) elements if this is less than limit, using the Froidure-Pin Algorithm.

If the optional second argument limit is not given, then the semigroup is enumerated until all of its elements have been found.

For reasons of performance, S is enumerated in batches according to the option batch_size, which can be specified when S is created; see Section 6.3.

gap> S := FullTransformationMonoid(7);
<full transformation monoid of degree 7>
gap> Enumerate(S, 1000);
<full transformation monoid of degree 7>
gap> Display(S);
<partially enumerated semigroup with 8197 elements, 
224 rules, max word length 11>

13.1-4 IsFullyEnumerated
‣ IsFullyEnumerated( S )( operation )

Returns: true or false.

If S is a semigroup with representation IsEnumerableSemigroupRep (6.1-4), then this operation returns true if the Froidure-Pin Algorithm has been run to completion (i.e. all of the elements of S have been found) and false if S has not been fully enumerated.

gap> S := FullBooleanMatMonoid(4);
<monoid of 4x4 boolean matrices with 7 generators>
gap> Enumerate(S, 1000);
<monoid of 4x4 boolean matrices with 7 generators>
gap> IsFullyEnumerated(S);
false
gap> Size(S);
65536
gap> IsFullyEnumerated(S);
true

13.2 Cayley graphs

13.2-1 RightCayleyGraphSemigroup
‣ RightCayleyGraphSemigroup( S )( attribute )
‣ LeftCayleyGraphSemigroup( S )( attribute )

Returns: A list of lists of positive integers.

When the argument S is a semigroup in the representation IsEnumerableSemigroupRep (6.1-4), RightCayleyGraphSemigroup returns the right Cayley graphs of S, as a list graph where graph[i][j] is equal to PositionCanonical(S, AsListCanonical(S)[i] * GeneratorsOfSemigroup(S)[j]). The list returned by LeftCayleyGraphSemigroup is defined analogously.

gap> S := FullTransformationMonoid(2);
<full transformation monoid of degree 2>
gap> RightCayleyGraphSemigroup(S);
[ [ 1, 2, 3 ], [ 2, 1, 3 ], [ 3, 4, 3 ], [ 4, 3, 3 ] ]
gap> LeftCayleyGraphSemigroup(S);
[ [ 1, 2, 3 ], [ 2, 1, 4 ], [ 3, 3, 3 ], [ 4, 4, 4 ] ]

13.3 Random elements of a semigroup

13.3-1 Random
‣ Random( S )( method )

Returns: A random element.

This function returns a random element of the semigroup S. If the elements of S have been calculated, then one of these is chosen randomly. Otherwise, if the data structure for S is known, then a random element of a randomly chosen \(\mathscr{R}\)-class is returned. If the data structure for S has not been calculated, then a short product (at most 2 * Length(GeneratorsOfSemigroup(S))) of generators is returned.

13.4 Properties of elements in a semigroup

13.4-1 IndexPeriodOfSemigroupElement
‣ IndexPeriodOfSemigroupElement( x )( operation )

Returns: A list of two positive integers.

If x is a semigroup element, then IndexPeriodOfSemigroupElement(x) returns the pair [m, r], where m and r are the least positive integers such that x^(m + r) = x ^ m. The number m is known as the index of x, and the numberr is known as the period of x.

gap> x := Transformation([2, 6, 3, 5, 6, 1]);;
gap> IndexPeriodOfSemigroupElement(x);
[ 2, 3 ]
gap> m := IndexPeriodOfSemigroupElement(x)[1];;
gap> r := IndexPeriodOfSemigroupElement(x)[2];;
gap> x ^ (m + r) = x ^ m;
true
gap> x := PartialPerm([0, 2, 3, 0, 5]);
<identity partial perm on [ 2, 3, 5 ]>
gap> IsIdempotent(x);
true
gap> IndexPeriodOfSemigroupElement(x);
[ 1, 1 ]

13.4-2 SmallestIdempotentPower
‣ SmallestIdempotentPower( x )( attribute )

Returns: A positive integer.

If x is a semigroup element, then SmallestIdempotentPower(x) returns the least positive integer n such that x^n is an idempotent. The smallest idempotent power of x is the least multiple of the period of x that is greater than or equal to the index of x; see IndexPeriodOfSemigroupElement (13.4-1).

gap> x := Transformation([4, 1, 4, 5, 1]);
Transformation( [ 4, 1, 4, 5, 1 ] )
gap> SmallestIdempotentPower(x);
3
gap> ForAll([1 .. 2], i -> not IsIdempotent(x ^ i));
true
gap> IsIdempotent(x ^ 3);
true
gap> x := Bipartition([[1, 2, -3, -4], [3, -5], [4, -1], [5, -2]]);
<block bijection: [ 1, 2, -3, -4 ], [ 3, -5 ], [ 4, -1 ], [ 5, -2 ]>
gap> SmallestIdempotentPower(x);
4
gap> ForAll([1 .. 3], i -> not IsIdempotent(x ^ i));
true
gap> x := PartialPerm([]);
<empty partial perm>
gap> SmallestIdempotentPower(x);
1
gap> IsIdempotent(x);
true

13.5 Expressing semigroup elements as words in generators

It is possible to express an element of a semigroup as a word in the generators of that semigroup. This section describes how to accomplish this in Semigroups.

13.5-1 EvaluateWord
‣ EvaluateWord( gens, w )( operation )

Returns: A semigroup element.

The argument gens should be a collection of generators of a semigroup and the argument w should be a list of positive integers less than or equal to the length of gens. This operation evaluates the word w in the generators gens. More precisely, EvaluateWord(gens, w) returns the equivalent of:

Product(List(w, i -> gens[i]));

see also Factorization (13.5-2).

for elements of a semigroup

When gens is a list of elements of a semigroup and w is a list of positive integers less than or equal to the length of gens, this operation returns the product gens[w[1]] * gens[w[2]] * .. . * gens[w[n]] when the length of w is n.

for elements of an inverse semigroup

When gens is a list of elements with a semigroup inverse and w is a list of non-zero integers whose absolute value does not exceed the length of gens, this operation returns the product gens[AbsInt(w[1])] ^ SignInt(w[1]) * .. . * gens[AbsInt(w[n])] ^ SignInt(w[n]) where n is the length of w.

Note that EvaluateWord(gens, []) returns One(gens) if gens belongs to the category IsMultiplicativeElementWithOne (Reference: IsMultiplicativeElementWithOne).

gap> gens := [
> Transformation([2, 4, 4, 6, 8, 8, 6, 6]),
> Transformation([2, 7, 4, 1, 4, 6, 5, 2]),
> Transformation([3, 6, 2, 4, 2, 2, 2, 8]),
> Transformation([4, 3, 6, 4, 2, 1, 2, 6]),
> Transformation([4, 5, 1, 3, 8, 5, 8, 2])];;
gap> S := Semigroup(gens);;
gap> x := Transformation([1, 4, 6, 1, 7, 2, 7, 6]);;
gap> word := Factorization(S, x);
[ 4, 2 ]
gap> EvaluateWord(gens, word);
Transformation( [ 1, 4, 6, 1, 7, 2, 7, 6 ] )
gap> S := SymmetricInverseMonoid(10);;
gap> x := PartialPerm([2, 6, 7, 0, 0, 9, 0, 1, 0, 5]);
[3,7][8,1,2,6,9][10,5]
gap> word := Factorization(S, x);
[ -2, -2, -2, -2, -3, -2, -2, -2, -2, -2, 5, 2, 5, 5, 2, 5, 2, 2, 2, 
  2, -3, 2, 2, 2, 3, 2, 2, 2, 2, 2, 2, 2, 2, 3, 2, 3, 2 ]
gap> EvaluateWord(GeneratorsOfSemigroup(S), word);
[3,7][8,1,2,6,9][10,5]

13.5-2 Factorization
‣ Factorization( S, x )( operation )

Returns: A word in the generators.

for semigroups

When S is a semigroup and x belongs to S, Factorization return a word in the generators of S that is equal to x. In this case, a word is a list of positive integers where an entry i corresponds to GeneratorsOfSemigroups(S)[i]. More specifically,

EvaluateWord(GeneratorsOfSemigroup(S), Factorization(S, x)) = x;
for inverse semigroups

When S is an inverse semigroup and x belongs to S, Factorization return a word in the generators of S that is equal to x. In this case, a word is a list of non-zero integers where an entry i corresponds to GeneratorsOfSemigroup(S)[i] and -i corresponds to GeneratorsOfSemigroup(S)[i] ^ -1. As in the previous case,

EvaluateWord(GeneratorsOfSemigroup(S), Factorization(S, x)) = x;

Note that Factorization does not always return a word of minimum length; see MinimalFactorization (13.5-3).

See also EvaluateWord (13.5-1) and GeneratorsOfSemigroup (Reference: GeneratorsOfSemigroup).

gap> gens := [Transformation([2, 2, 9, 7, 4, 9, 5, 5, 4, 8]),
>             Transformation([4, 10, 5, 6, 4, 1, 2, 7, 1, 2])];;
gap> S := Semigroup(gens);;
gap> x := Transformation([1, 10, 2, 10, 1, 2, 7, 10, 2, 7]);;
gap> word := Factorization(S, x);
[ 2, 2, 1, 2 ]
gap> EvaluateWord(gens, word);
Transformation( [ 1, 10, 2, 10, 1, 2, 7, 10, 2, 7 ] )
gap> S := SymmetricInverseMonoid(8);
<symmetric inverse monoid of degree 8>
gap> x := PartialPerm([1, 2, 3, 4, 5, 8], [7, 1, 4, 3, 2, 6]);
[5,2,1,7][8,6](3,4)
gap> word := Factorization(S, x);
[ -2, -2, -2, -2, -2, -2, 2, 4, 4, 2, 3, 2, -3, -2, -2, 3, 2, -3, -2, 
  -2, 4, -3, -4, 2, 2, 3, -2, -3, 4, -3, -4, 2, 2, 3, -2, -3, 2, 2, 
  3, -2, -3, 2, 2, 3, -2, -3, 4, -3, -4, 3, 2, -3, -2, -2, 3, 2, -3, 
  -2, -2, 4, 3, -4, 3, 2, -3, -2, -2, 3, 2, -3, -2, -2, 3, 2, 2, 3, 
  2, 2, 2, 2 ]
gap> EvaluateWord(GeneratorsOfSemigroup(S), word);
[5,2,1,7][8,6](3,4)
gap> S := DualSymmetricInverseMonoid(6);;
gap> x := S.1 * S.2 * S.3 * S.2 * S.1;
<block bijection: [ 1, 6, -4 ], [ 2, -2, -3 ], [ 3, -5 ], [ 4, -6 ], 
 [ 5, -1 ]>
gap> word := Factorization(S, x);
[ -2, -2, -2, -2, -2, 4, 2 ]
gap> EvaluateWord(GeneratorsOfSemigroup(S), word);
<block bijection: [ 1, 6, -4 ], [ 2, -2, -3 ], [ 3, -5 ], [ 4, -6 ], 
 [ 5, -1 ]>

13.5-3 MinimalFactorization
‣ MinimalFactorization( S, x )( operation )

Returns: A minimal word in the generators.

This operation returns a minimal length word in the generators of the semigroup S that equals the element x. In this case, a word is a list of positive integers where an entry i corresponds to GeneratorsOfSemigroups(S)[i]. More specifically,

EvaluateWord(GeneratorsOfSemigroup(S), MinimalFactorization(S, x)) = x;

MinimalFactorization involves exhaustively enumerating S until the element x is found, and so MinimalFactorization may be less efficient than Factorization (13.5-2) for some semigroups.

Unlike Factorization (13.5-2) this operation does not distinguish between semigroups and inverse semigroups. See also EvaluateWord (13.5-1) and GeneratorsOfSemigroup (Reference: GeneratorsOfSemigroup).

gap> S := Semigroup(Transformation([2, 2, 9, 7, 4, 9, 5, 5, 4, 8]),
>                   Transformation([4, 10, 5, 6, 4, 1, 2, 7, 1, 2]));
<transformation semigroup of degree 10 with 2 generators>
gap> x := Transformation([8, 8, 2, 2, 9, 2, 8, 8, 9, 9]);
Transformation( [ 8, 8, 2, 2, 9, 2, 8, 8, 9, 9 ] )
gap> Factorization(S, x);
[ 1, 2, 1, 1, 1, 2, 1, 1, 1, 2, 1, 1, 1, 2, 1 ]
gap> MinimalFactorization(S, x);
[ 1, 2, 1, 1, 1, 1, 2, 2, 1 ]

13.6 Generating sets

13.6-1 Generators
‣ Generators( S )( attribute )

Returns: A list of generators.

Generators returns a generating set that can be used to define the semigroup S. The generators of a monoid or inverse semigroup S, say, can be defined in several ways, for example, including or excluding the identity element, including or not the inverses of the generators. Generators uses the definition that returns the least number of generators. If no generating set for S is known, then GeneratorsOfSemigroup is used by default.

for a group

Generators(S) is a synonym for GeneratorsOfGroup (Reference: GeneratorsOfGroup).

for an ideal of semigroup

Generators(S) is a synonym for GeneratorsOfSemigroupIdeal (7.2-1).

for a semigroup

Generators(S) is a synonym for GeneratorsOfSemigroup (Reference: GeneratorsOfSemigroup).

for a monoid

Generators(S) is a synonym for GeneratorsOfMonoid (Reference: GeneratorsOfMonoid).

for an inverse semigroup

Generators(S) is a synonym for GeneratorsOfInverseSemigroup (Reference: GeneratorsOfInverseSemigroup).

for an inverse monoid

Generators(S) is a synonym for GeneratorsOfInverseMonoid (Reference: GeneratorsOfInverseMonoid).

gap> M := Monoid([
> Transformation([1, 4, 6, 2, 5, 3, 7, 8, 9, 9]),
> Transformation([6, 3, 2, 7, 5, 1, 8, 8, 9, 9])]);;
gap> GeneratorsOfSemigroup(M);
[ IdentityTransformation, 
  Transformation( [ 1, 4, 6, 2, 5, 3, 7, 8, 9, 9 ] ), 
  Transformation( [ 6, 3, 2, 7, 5, 1, 8, 8, 9, 9 ] ) ]
gap> GeneratorsOfMonoid(M);
[ Transformation( [ 1, 4, 6, 2, 5, 3, 7, 8, 9, 9 ] ), 
  Transformation( [ 6, 3, 2, 7, 5, 1, 8, 8, 9, 9 ] ) ]
gap> Generators(M);
[ Transformation( [ 1, 4, 6, 2, 5, 3, 7, 8, 9, 9 ] ), 
  Transformation( [ 6, 3, 2, 7, 5, 1, 8, 8, 9, 9 ] ) ]
gap> S := Semigroup(Generators(M));;
gap> Generators(S);
[ Transformation( [ 1, 4, 6, 2, 5, 3, 7, 8, 9, 9 ] ), 
  Transformation( [ 6, 3, 2, 7, 5, 1, 8, 8, 9, 9 ] ) ]
gap> GeneratorsOfSemigroup(S);
[ Transformation( [ 1, 4, 6, 2, 5, 3, 7, 8, 9, 9 ] ), 
  Transformation( [ 6, 3, 2, 7, 5, 1, 8, 8, 9, 9 ] ) ]

13.6-2 SmallGeneratingSet
‣ SmallGeneratingSet( coll )( attribute )
‣ SmallSemigroupGeneratingSet( coll )( attribute )
‣ SmallMonoidGeneratingSet( coll )( attribute )
‣ SmallInverseSemigroupGeneratingSet( coll )( attribute )
‣ SmallInverseMonoidGeneratingSet( coll )( attribute )

Returns: A small generating set for a semigroup.

The attributes SmallXGeneratingSet return a relatively small generating subset of the collection of elements coll, which can also be a semigroup. The returned value of SmallXGeneratingSet, where applicable, has the property that

      X(SmallXGeneratingSet(coll)) = X(coll);

where X is any of Semigroup (Reference: Semigroup), Monoid (Reference: Monoid), InverseSemigroup (Reference: InverseSemigroup), or InverseMonoid (Reference: InverseMonoid).

If the number of generators for S is already relatively small, then these functions will often return the original generating set. These functions may return different results in different GAP sessions.

SmallGeneratingSet returns the smallest of the returned values of SmallXGeneratingSet which is applicable to coll; see Generators (13.6-1).

As neither irredundancy, nor minimal length are proven, these functions usually return an answer much more quickly than IrredundantGeneratingSubset (13.6-3). These functions can be used whenever a small generating set is desired which does not necessarily needs to be minimal.

gap> S := Semigroup([
> Transformation([1, 2, 3, 2, 4]),
> Transformation([1, 5, 4, 3, 2]),
> Transformation([2, 1, 4, 2, 2]),
> Transformation([2, 4, 4, 2, 1]),
> Transformation([3, 1, 4, 3, 2]),
> Transformation([3, 2, 3, 4, 1]),
> Transformation([4, 4, 3, 3, 5]),
> Transformation([5, 1, 5, 5, 3]),
> Transformation([5, 4, 3, 5, 2]),
> Transformation([5, 5, 4, 5, 5])]);;
gap> SmallGeneratingSet(S);
[ Transformation( [ 1, 5, 4, 3, 2 ] ), Transformation( [ 3, 2, 3, 4, 1 ] ), 
  Transformation( [ 5, 4, 3, 5, 2 ] ), Transformation( [ 1, 2, 3, 2, 4 ] ), 
  Transformation( [ 4, 4, 3, 3, 5 ] ) ]
gap> S := RandomInverseMonoid(IsPartialPermMonoid, 10000, 10);;
gap> SmallGeneratingSet(S);
[ [ 1 .. 10 ] -> [ 3, 2, 4, 5, 6, 1, 7, 10, 9, 8 ],
  [ 1 .. 10 ] -> [ 5, 10, 8, 9, 3, 2, 4, 7, 6, 1 ],
  [ 1, 3, 4, 5, 6, 7, 8, 9, 10 ] -> [ 1, 6, 4, 8, 2, 10, 7, 3, 9 ] ]
gap> M := MathieuGroup(24);;
gap> mat := List([1 .. 1000], x -> Random(M));;
gap> Append(mat, [1 .. 1000] * 0);
gap> mat := List([1 .. 138], x -> List([1 .. 57], x -> Random(mat)));;
gap> R := ReesZeroMatrixSemigroup(M, mat);;
gap> U := Semigroup(List([1 .. 200], x -> Random(R)));
<subsemigroup of 57x138 Rees 0-matrix semigroup with 100 generators>
gap> Length(SmallGeneratingSet(U));
84
gap> S := RandomSemigroup(IsBipartitionSemigroup, 100, 4);
<bipartition semigroup of degree 4 with 96 generators>
gap> Length(SmallGeneratingSet(S));
13

13.6-3 IrredundantGeneratingSubset
‣ IrredundantGeneratingSubset( coll )( operation )

Returns: A list of irredundant generators.

If coll is a collection of elements of a semigroup, then this function returns a subset U of coll such that no element of U is generated by the other elements of U.

gap> S := Semigroup([
> Transformation([5, 1, 4, 6, 2, 3]),
> Transformation([1, 2, 3, 4, 5, 6]),
> Transformation([4, 6, 3, 4, 2, 5]),
> Transformation([5, 4, 6, 3, 1, 3]),
> Transformation([2, 2, 6, 5, 4, 3]),
> Transformation([3, 5, 5, 1, 2, 4]),
> Transformation([6, 5, 1, 3, 3, 4]),
> Transformation([1, 3, 4, 3, 2, 1])]);;
gap> IrredundantGeneratingSubset(S);
[ Transformation( [ 1, 3, 4, 3, 2, 1 ] ), 
  Transformation( [ 2, 2, 6, 5, 4, 3 ] ), 
  Transformation( [ 3, 5, 5, 1, 2, 4 ] ), 
  Transformation( [ 5, 1, 4, 6, 2, 3 ] ), 
  Transformation( [ 5, 4, 6, 3, 1, 3 ] ), 
  Transformation( [ 6, 5, 1, 3, 3, 4 ] ) ]
gap> S := RandomInverseMonoid(IsPartialPermMonoid, 1000, 10);
<inverse partial perm monoid of degree 10 with 1000 generators>
gap> SmallGeneratingSet(S);
[ [ 1 .. 10 ] -> [ 6, 5, 1, 9, 8, 3, 10, 4, 7, 2 ], 
  [ 1 .. 10 ] -> [ 1, 4, 6, 2, 8, 5, 7, 10, 3, 9 ], 
  [ 1, 2, 3, 4, 6, 7, 8, 9 ] -> [ 7, 5, 10, 1, 8, 4, 9, 6 ]
  [ 1 .. 9 ] -> [ 4, 3, 5, 7, 10, 9, 1, 6, 8 ] ]
gap> IrredundantGeneratingSubset(last);
[ [ 1 .. 9 ] -> [ 4, 3, 5, 7, 10, 9, 1, 6, 8 ], 
  [ 1 .. 10 ] -> [ 1, 4, 6, 2, 8, 5, 7, 10, 3, 9 ], 
  [ 1 .. 10 ] -> [ 6, 5, 1, 9, 8, 3, 10, 4, 7, 2 ] ]
gap> S := RandomSemigroup(IsBipartitionSemigroup, 1000, 4);
<bipartition semigroup of degree 4 with 749 generators>
gap> SmallGeneratingSet(S);
[ <bipartition: [ 1, -3 ], [ 2, -2 ], [ 3, -1 ], [ 4, -4 ]>, 
  <bipartition: [ 1, 3, -2 ], [ 2, -1, -3 ], [ 4, -4 ]>, 
  <bipartition: [ 1, -4 ], [ 2, 4, -1, -3 ], [ 3, -2 ]>, 
  <bipartition: [ 1, -1, -3 ], [ 2, -4 ], [ 3, 4, -2 ]>, 
  <bipartition: [ 1, -2, -4 ], [ 2 ], [ 3, -3 ], [ 4, -1 ]>, 
  <bipartition: [ 1, -2 ], [ 2, -1, -3 ], [ 3, 4, -4 ]>, 
  <bipartition: [ 1, 3, -1 ], [ 2, -3 ], [ 4, -2, -4 ]>, 
  <bipartition: [ 1, -1 ], [ 2, 4, -4 ], [ 3, -2, -3 ]>, 
  <bipartition: [ 1, 3, -1 ], [ 2, -2 ], [ 4, -3, -4 ]>, 
  <bipartition: [ 1, 2, -2 ], [ 3, -1, -4 ], [ 4, -3 ]>, 
  <bipartition: [ 1, -2, -3 ], [ 2, -4 ], [ 3 ], [ 4, -1 ]>, 
  <bipartition: [ 1, -1 ], [ 2, 4, -3 ], [ 3, -2 ], [ -4 ]>, 
  <bipartition: [ 1, -3 ], [ 2, -1 ], [ 3, 4, -4 ], [ -2 ]>, 
  <bipartition: [ 1, 2, -4 ], [ 3, -1 ], [ 4, -2 ], [ -3 ]>, 
  <bipartition: [ 1, -3 ], [ 2, -4 ], [ 3, -1, -2 ], [ 4 ]> ]
gap> IrredundantGeneratingSubset(last);
[ <bipartition: [ 1, 2, -4 ], [ 3, -1 ], [ 4, -2 ], [ -3 ]>, 
  <bipartition: [ 1, 3, -1 ], [ 2, -2 ], [ 4, -3, -4 ]>, 
  <bipartition: [ 1, 3, -2 ], [ 2, -1, -3 ], [ 4, -4 ]>, 
  <bipartition: [ 1, -1 ], [ 2, 4, -3 ], [ 3, -2 ], [ -4 ]>, 
  <bipartition: [ 1, -3 ], [ 2, -1 ], [ 3, 4, -4 ], [ -2 ]>, 
  <bipartition: [ 1, -3 ], [ 2, -2 ], [ 3, -1 ], [ 4, -4 ]>, 
  <bipartition: [ 1, -3 ], [ 2, -4 ], [ 3, -1, -2 ], [ 4 ]>, 
  <bipartition: [ 1, -2, -3 ], [ 2, -4 ], [ 3 ], [ 4, -1 ]>, 
  <bipartition: [ 1, -2, -4 ], [ 2 ], [ 3, -3 ], [ 4, -1 ]> ]

13.6-4 MinimalSemigroupGeneratingSet
‣ MinimalSemigroupGeneratingSet( S )( attribute )
‣ MinimalMonoidGeneratingSet( S )( attribute )
‣ MinimalInverseSemigroupGeneratingSet( S )( attribute )
‣ MinimalInverseMonoidGeneratingSet( S )( attribute )

Returns: A minimal generating set for a semigroup.

Warning: currently, no methods are installed to compute these attributes.

The attributes MinimalXGeneratingSet return a minimal generating set for the semigroup S, with respect to length. The returned value of MinimalXGeneratingSet, where applicable, is a minimal-length list of elements of S with the property that

      X(MinimalXGeneratingSet(S)) = S;
    

where X is any of Semigroup (Reference: Semigroup), Monoid (Reference: Monoid), InverseSemigroup (Reference: InverseSemigroup), or InverseMonoid (Reference: InverseMonoid).

For certain types of semigroup, for example monogenic semigroups, a MinimalXGeneratingSet may be known a priori, or may be deduced as a by-product of other functions. However, since there are no methods installed to compute these attributes directly, for most semigroups it is not currently possible to find a MinimalXGeneratingSet with the Semigroups package.

See also SmallGeneratingSet (13.6-2) and IrredundantGeneratingSubset (13.6-3).

gap> S := MonogenicSemigroup(3, 6);;
gap> MinimalSemigroupGeneratingSet(S);
[ Transformation( [ 2, 3, 4, 5, 6, 1, 6, 7, 8 ] ) ]
gap> S := Semigroup([
>  PartialPerm([1, 2, 3, 4, 5], [1, 2, 3, 4, 5]),
>  PartialPerm([1, 2, 3, 4], [5, 2, 4, 1]),
>  PartialPerm([1, 2, 4, 5], [4, 2, 3, 1])]);
<partial perm monoid of rank 5 with 2 generators>
gap> IsMonogenicInverseMonoid(S);
true
gap> MinimalInverseMonoidGeneratingSet(S);
[ [3,4,1,5](2) ]

13.6-5 GeneratorsSmallest
‣ GeneratorsSmallest( S )( attribute )

Returns: A set of elements.

For a semigroup S, GeneratorsSmallest returns the lexicographically least set of elements X such that X generates S as a semigroup, and such that X is lexicographically ordered and has the property that each X[i] is not generated by X[1], X[2], ..., X[i-1].

It can be difficult to find the set of generators X, and it might contain a substantial proportion of the elements of S.

Two semigroups have the same set of elements if and only if their smallest generating sets are equal. However, due to the complexity of determining the GeneratorsSmallest, this is not the method used by the Semigroups package when comparing semigroups.

gap> S := Monoid([
>  Transformation([1, 3, 4, 1]),
>  Transformation([2, 4, 1, 2]),
>  Transformation([3, 1, 1, 3]),
>  Transformation([3, 3, 4, 1])]);
<transformation monoid of degree 4 with 4 generators>
gap> GeneratorsSmallest(S);
[ Transformation( [ 1, 1, 1, 1 ] ), Transformation( [ 1, 1, 1, 2 ] ), 
  Transformation( [ 1, 1, 1, 3 ] ), Transformation( [ 1, 1, 1 ] ), 
  Transformation( [ 1, 1, 2, 1 ] ), Transformation( [ 1, 1, 2, 2 ] ), 
  Transformation( [ 1, 1, 3, 1 ] ), Transformation( [ 1, 1, 3, 3 ] ), 
  Transformation( [ 1, 1 ] ), Transformation( [ 1, 1, 4, 1 ] ), 
  Transformation( [ 1, 2, 1, 1 ] ), Transformation( [ 1, 2, 2, 1 ] ), 
  IdentityTransformation, Transformation( [ 1, 3, 1, 1 ] ), 
  Transformation( [ 1, 3, 4, 1 ] ), Transformation( [ 2, 1, 1, 2 ] ), 
  Transformation( [ 2, 2, 2 ] ), Transformation( [ 2, 4, 1, 2 ] ), 
  Transformation( [ 3, 3, 3 ] ), Transformation( [ 3, 3, 4, 1 ] ) ]
gap> T := Semigroup(Bipartition([[1, 2, 3], [4, -1], [-2], [-3], [-4]]),
>                   Bipartition([[1, -3, -4], [2, 3, 4, -2], [-1]]),
>                   Bipartition([[1, 2, 3, 4, -2], [-1, -4], [-3]]),
>                   Bipartition([[1, 2, 3, 4], [-1], [-2], [-3, -4]]),
>                   Bipartition([[1, 2, -1, -2], [3, 4, -3], [-4]]));
<bipartition semigroup of degree 4 with 5 generators>
gap> GeneratorsSmallest(T);
[ <bipartition: [ 1, 2, 3, 4, -1, -2, -3 ], [ -4 ]>, 
  <bipartition: [ 1, 2, 3, 4, -1, -2 ], [ -3 ], [ -4 ]>, 
  <bipartition: [ 1, 2, 3, 4, -1 ], [ -2 ], [ -3 ], [ -4 ]>, 
  <bipartition: [ 1, 2, 3, 4, -2, -3, -4 ], [ -1 ]>, 
  <bipartition: [ 1, 2, 3, 4, -2 ], [ -1, -4 ], [ -3 ]>, 
  <bipartition: [ 1, 2, 3, 4, -2 ], [ -1 ], [ -3, -4 ]>, 
  <bipartition: [ 1, 2, 3, 4, -3 ], [ -1, -2 ], [ -4 ]>, 
  <bipartition: [ 1, 2, 3, 4 ], [ -1, -2, -3 ], [ -4 ]>, 
  <bipartition: [ 1, 2, 3, 4, -3, -4 ], [ -1 ], [ -2 ]>, 
  <bipartition: [ 1, 2, 3 ], [ 4, -1, -2, -3 ], [ -4 ]>, 
  <bipartition: [ 1, 2, -1, -2 ], [ 3, 4, -3 ], [ -4 ]>, 
  <bipartition: [ 1, -3 ], [ 2, 3, 4, -1, -2 ], [ -4 ]>, 
  <bipartition: [ 1, -3, -4 ], [ 2, 3, 4, -2 ], [ -1 ]> ]

13.7 Minimal ideals and multiplicative zeros

In this section we describe the attributes of a semigroup that can be found using the Semigroups package.

13.7-1 MinimalIdeal
‣ MinimalIdeal( S )( attribute )

Returns: The minimal ideal of a semigroup.

The minimal ideal of a semigroup is the least ideal with respect to containment.

It is significantly easier to find the minimal \(\mathscr{D}\)-class of a semigroup, than to find its \(\mathscr{D}\)-classes.

See also RepresentativeOfMinimalIdeal (13.7-2), PartialOrderOfDClasses (12.1-10), IsGreensLessThanOrEqual (Reference: IsGreensLessThanOrEqual), and MinimalDClass (12.1-6).

gap> S := Semigroup(
> Transformation([3, 4, 1, 3, 6, 3, 4, 6, 10, 1]),
> Transformation([8, 2, 3, 8, 4, 1, 3, 4, 9, 7]));;
gap> MinimalIdeal(S);
<simple transformation semigroup ideal of degree 10 with 1 generator>
gap> Elements(MinimalIdeal(S));
[ Transformation( [ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 ] ), 
  Transformation( [ 3, 3, 3, 3, 3, 3, 3, 3, 3, 3 ] ), 
  Transformation( [ 4, 4, 4, 4, 4, 4, 4, 4, 4, 4 ] ), 
  Transformation( [ 6, 6, 6, 6, 6, 6, 6, 6, 6, 6 ] ), 
  Transformation( [ 8, 8, 8, 8, 8, 8, 8, 8, 8, 8 ] ) ]
gap> x := Transformation([8, 8, 8, 8, 8, 8, 8, 8, 8, 8]);;
gap> D := DClass(S, x);;
gap> ForAll(GreensDClasses(S), x -> IsGreensLessThanOrEqual(D, x));
true
gap> MinimalIdeal(POI(10));
<partial perm group of rank 10>
gap> MinimalIdeal(BrauerMonoid(6));
<simple bipartition *-semigroup ideal of degree 6 with 1 generator>

13.7-2 RepresentativeOfMinimalIdeal
‣ RepresentativeOfMinimalIdeal( S )( attribute )
‣ RepresentativeOfMinimalDClass( S )( attribute )

Returns: An element of the minimal ideal of a semigroup.

The minimal ideal of a semigroup is the least ideal with respect to containment.

This method returns a representative element of the minimal ideal of S without having to create the minimal ideal itself. In general, beyond being a member of the minimal ideal, the returned element is not guaranteed to have any special properties. However, the element will coincide with the zero element of S if one exists.

This method works particularly well if S is a semigroup of transformations or partial permutations.

See also MinimalIdeal (13.7-1) and MinimalDClass (12.1-6).

gap> S := SymmetricInverseSemigroup(10);;
gap> RepresentativeOfMinimalIdeal(S);
<empty partial perm>
gap> B := Semigroup([
> Bipartition([[1, 2], [3, 6, -2], [4, 5, -3, -4], [-1, -6], [-5]]),
> Bipartition([[1, -1], [2], [3], [4, -3], [5, 6, -5, -6],
>   [-2, -4]])]);;
gap> RepresentativeOfMinimalIdeal(B);
<bipartition: [ 1, 2 ], [ 3, 6 ], [ 4, 5 ], [ -1, -5, -6 ], 
 [ -2, -4 ], [ -3 ]>
gap> S := Semigroup(Transformation([5, 1, 6, 2, 2, 4]),
>                   Transformation([3, 5, 5, 1, 6, 2]));;
gap> RepresentativeOfMinimalDClass(S);
Transformation( [ 1, 2, 2, 5, 5, 1 ] )
gap> MinimalDClass(S);
<Green's D-class: Transformation( [ 1, 2, 2, 5, 5, 1 ] )>

13.7-3 MultiplicativeZero
‣ MultiplicativeZero( S )( attribute )

Returns: The zero element of a semigroup.

MultiplicativeZero returns the zero element of the semigroup S if it exists and fail if it does not. See also MultiplicativeZero (Reference: MultiplicativeZero).

gap> S := Semigroup(Transformation([1, 4, 2, 6, 6, 5, 2]),
>                   Transformation([1, 6, 3, 6, 2, 1, 6]));;
gap> MultiplicativeZero(S);
Transformation( [ 1, 1, 1, 1, 1, 1, 1 ] )
gap> S := Semigroup(Transformation([2, 8, 3, 7, 1, 5, 2, 6]),
>                   Transformation([3, 5, 7, 2, 5, 6, 3, 8]),
>                   Transformation([6, 7, 4, 1, 4, 1, 6, 2]),
>                   Transformation([8, 8, 5, 1, 7, 5, 2, 8]));;
gap> MultiplicativeZero(S);
fail
gap> S := InverseSemigroup(
> PartialPerm([1, 3, 4], [5, 3, 1]),
> PartialPerm([1, 2, 3, 4], [4, 3, 1, 2]),
> PartialPerm([1, 3, 4, 5], [2, 4, 5, 3]));;
gap> MultiplicativeZero(S);
<empty partial perm>
gap> S := PartitionMonoid(6);
<regular bipartition *-monoid of size 4213597, degree 6 with 4 
 generators>
gap> MultiplicativeZero(S);
fail
gap> S := DualSymmetricInverseMonoid(6);
<inverse block bijection monoid of degree 6 with 3 generators>
gap> MultiplicativeZero(S);
<block bijection: [ 1, 2, 3, 4, 5, 6, -1, -2, -3, -4, -5, -6 ]>

13.7-4 UnderlyingSemigroupOfSemigroupWithAdjoinedZero
‣ UnderlyingSemigroupOfSemigroupWithAdjoinedZero( S )( attribute )

Returns: A semigroup, or fail.

If S is a semigroup for which the property IsSemigroupWithAdjoinedZero (14.1-19) is true, (i.e. S has a MultiplicativeZero (13.7-3) and the set S ∖ { 0 } is a subsemigroup of S), then this method returns the semigroup S ∖ { 0 }.

Otherwise, if S is a semigroup for which the property IsSemigroupWithAdjoinedZero (14.1-19) is false, then this method returns fail.

gap> S := Semigroup([
> Transformation([2, 3, 4, 5, 1, 6]),
> Transformation([2, 1, 3, 4, 5, 6]),
> Transformation([6, 6, 6, 6, 6, 6])]);
<transformation semigroup of degree 6 with 3 generators>
gap> MultiplicativeZero(S);
Transformation( [ 6, 6, 6, 6, 6, 6 ] )
gap> G := UnderlyingSemigroupOfSemigroupWithAdjoinedZero(S);
<transformation semigroup of degree 5 with 2 generators>
gap> IsGroupAsSemigroup(G);
true
gap> IsZeroGroup(S);
true
gap> S := SymmetricInverseMonoid(6);;
gap> MultiplicativeZero(S);
<empty partial perm>
gap> G := UnderlyingSemigroupOfSemigroupWithAdjoinedZero(S);
fail

13.8 Group of units and identity elements

13.8-1 GroupOfUnits
‣ GroupOfUnits( S )( attribute )

Returns: The group of units of a semigroup or fail.

GroupOfUnits returns the group of units of the semigroup S as a subsemigroup of S if it exists and returns fail if it does not. Use IsomorphismPermGroup (6.5-5) if you require a permutation representation of the group of units.

If a semigroup S has an identity e, then the group of units of S is the set of those s in S such that there exists t in S where s*t=t*s=e. Equivalently, the group of units is the \(\mathscr{H}\)-class of the identity of S.

See also GreensHClassOfElement (Reference: GreensHClassOfElement), IsMonoidAsSemigroup (14.1-12), and MultiplicativeNeutralElement (Reference: MultiplicativeNeutralElement).

gap> S := Semigroup(
> Transformation([1, 2, 5, 4, 3, 8, 7, 6]),
> Transformation([1, 6, 3, 4, 7, 2, 5, 8]),
> Transformation([2, 1, 6, 7, 8, 3, 4, 5]),
> Transformation([3, 2, 3, 6, 1, 6, 1, 2]),
> Transformation([5, 2, 3, 6, 3, 4, 7, 4]));;
gap> Size(S);
5304
gap> StructureDescription(GroupOfUnits(S));
"C2 x S4"
gap> S := InverseSemigroup(
> PartialPerm([1, 2, 3, 4, 5, 6, 7, 8, 9, 10],
>             [2, 4, 5, 3, 6, 7, 10, 9, 8, 1]),
> PartialPerm([1, 2, 3, 4, 5, 6, 7, 8, 10],
>             [8, 2, 3, 1, 4, 5, 10, 6, 9]));;
gap> StructureDescription(GroupOfUnits(S));
"C8"
gap> S := InverseSemigroup(
> PartialPerm([1, 3, 4], [4, 3, 5]),
> PartialPerm([1, 2, 3, 5], [3, 1, 5, 2]));;
gap> GroupOfUnits(S);
fail
gap> S := Semigroup(
> Bipartition([[1, 2, 3, -1, -3], [-2]]),
> Bipartition([[1, -1], [2, 3, -2, -3]]),
> Bipartition([[1, -2], [2, -3], [3, -1]]),
> Bipartition([[1], [2, 3, -2], [-1, -3]]));;
gap> StructureDescription(GroupOfUnits(S));
"C3"

13.9 Idempotents

13.9-1 Idempotents
‣ Idempotents( obj[, n] )( attribute )

Returns: A list of idempotents.

The argument obj should be a semigroup, \(\mathscr{D}\)-class, \(\mathscr{H}\)-class, \(\mathscr{L}\)-class, or \(\mathscr{R}\)-class.

If the optional second argument n is present and obj is a semigroup, then a list of the idempotents in obj of rank n is returned. If you are only interested in the idempotents of a given rank, then the second version of the function will probably be faster. However, if the optional second argument is present, then nothing is stored in obj and so every time the function is called the computation must be repeated.

This functions produce essentially the same output as the GAP library function with the same name; see Idempotents (Reference: Idempotents). The main difference is that this function can be applied to a wider class of objects as described above.

See also IsRegularDClass (Reference: IsRegularDClass), IsRegularGreensClass (12.3-2) IsGroupHClass (Reference: IsGroupHClass), NrIdempotents (13.9-2), and GroupHClass (12.4-1).

gap> S := Semigroup(Transformation([2, 3, 4, 1]),
>                   Transformation([3, 3, 1, 1]));;
gap> Idempotents(S, 1);
[  ]
gap> AsSet(Idempotents(S, 2));
[ Transformation( [ 1, 1, 3, 3 ] ), Transformation( [ 1, 3, 3, 1 ] ), 
  Transformation( [ 2, 2, 4, 4 ] ), Transformation( [ 4, 2, 2, 4 ] ) ]
gap> AsSet(Idempotents(S));
[ Transformation( [ 1, 1, 3, 3 ] ), IdentityTransformation, 
  Transformation( [ 1, 3, 3, 1 ] ), Transformation( [ 2, 2, 4, 4 ] ), 
  Transformation( [ 4, 2, 2, 4 ] ) ]
gap> x := Transformation([2, 2, 4, 4]);;
gap> R := GreensRClassOfElement(S, x);;
gap> Idempotents(R);
[ Transformation( [ 1, 1, 3, 3 ] ), Transformation( [ 2, 2, 4, 4 ] ) ]
gap> x := Transformation([4, 2, 2, 4]);;
gap> L := GreensLClassOfElement(S, x);;
gap> AsSet(Idempotents(L));
[ Transformation( [ 2, 2, 4, 4 ] ), Transformation( [ 4, 2, 2, 4 ] ) ]
gap> D := DClassOfLClass(L);;
gap> AsSet(Idempotents(D));
[ Transformation( [ 1, 1, 3, 3 ] ), Transformation( [ 1, 3, 3, 1 ] ), 
  Transformation( [ 2, 2, 4, 4 ] ), Transformation( [ 4, 2, 2, 4 ] ) ]
gap> L := GreensLClassOfElement(S, Transformation([3, 1, 1, 3]));;
gap> AsSet(Idempotents(L));
[ Transformation( [ 1, 1, 3, 3 ] ), Transformation( [ 1, 3, 3, 1 ] ) ]
gap> H := GroupHClass(D);
<Green's H-class: Transformation( [ 1, 1, 3, 3 ] )>
gap> Idempotents(H);
[ Transformation( [ 1, 1, 3, 3 ] ) ]
gap> S := InverseSemigroup(
> PartialPerm([10, 6, 3, 4, 9, 0, 1]),
> PartialPerm([6, 10, 7, 4, 8, 2, 9, 1]));;
gap> Idempotents(S, 1);
[ <identity partial perm on [ 4 ]> ]
gap> Idempotents(S, 0);
[  ]

13.9-2 NrIdempotents
‣ NrIdempotents( obj )( attribute )

Returns: A positive integer.

This function returns the number of idempotents in obj where obj can be a semigroup, \(\mathscr{D}\)-, \(\mathscr{L}\)-, \(\mathscr{H}\)-, or \(\mathscr{R}\)-class. If the actual idempotents are not required, then it is more efficient to use NrIdempotents(obj) than Length(Idempotents(obj)) since the idempotents themselves are not created when NrIdempotents is called.

See also Idempotents (Reference: Idempotents) and Idempotents (13.9-1), IsRegularDClass (Reference: IsRegularDClass), IsRegularGreensClass (12.3-2) IsGroupHClass (Reference: IsGroupHClass), and GroupHClass (12.4-1).

gap> S := Semigroup(Transformation([2, 3, 4, 1]),
>                   Transformation([3, 3, 1, 1]));;
gap> NrIdempotents(S);
5
gap> f := Transformation([2, 2, 4, 4]);;
gap> R := GreensRClassOfElement(S, f);;
gap> NrIdempotents(R);
2
gap> f := Transformation([4, 2, 2, 4]);;
gap> L := GreensLClassOfElement(S, f);;
gap> NrIdempotents(L);
2
gap> D := DClassOfLClass(L);;
gap> NrIdempotents(D);
4
gap> L := GreensLClassOfElement(S, Transformation([3, 1, 1, 3]));;
gap> NrIdempotents(L);
2
gap> H := GroupHClass(D);;
gap> NrIdempotents(H);
1
gap> S := InverseSemigroup(
> PartialPerm([1, 2, 3, 5, 7, 9, 10],
>              [6, 7, 2, 9, 1, 5, 3]),
> PartialPerm([1, 2, 3, 5, 6, 7, 9, 10],
>             [8, 1, 9, 4, 10, 5, 6, 7]));;
gap> NrIdempotents(S);
236
gap> f := PartialPerm([2, 3, 7, 9, 10],
>                     [7, 2, 1, 5, 3]);;
gap> D := DClassNC(S, f);;
gap> NrIdempotents(D);
13

13.9-3 IdempotentGeneratedSubsemigroup
‣ IdempotentGeneratedSubsemigroup( S )( attribute )

Returns: A semigroup.

IdempotentGeneratedSubsemigroup returns the subsemigroup of the semigroup S generated by the idempotents of S.

See also Idempotents (13.9-1) and SmallGeneratingSet (13.6-2).

gap> S := Semigroup(Transformation([1, 1]),
>                   Transformation([2, 1]),
>                   Transformation([1, 2, 2]),
>                   Transformation([1, 2, 3, 4, 5, 1]),
>                   Transformation([1, 2, 3, 4, 5, 5]),
>                   Transformation([1, 2, 3, 4, 6, 5]),
>                   Transformation([1, 2, 3, 5, 4]),
>                   Transformation([1, 2, 3, 7, 4, 5, 7]),
>                   Transformation([1, 2, 4, 8, 8, 3, 8, 7]),
>                   Transformation([1, 2, 8, 4, 5, 6, 7, 8]),
>                   Transformation([7, 7, 7, 4, 5, 6, 1]));;
gap> IdempotentGeneratedSubsemigroup(S) =
> Monoid(Transformation([1, 1]),
>        Transformation([1, 2, 1]),
>        Transformation([1, 2, 2]),
>        Transformation([1, 2, 3, 1]),
>        Transformation([1, 2, 3, 2]),
>        Transformation([1, 2, 3, 4, 1]),
>        Transformation([1, 2, 3, 4, 2]),
>        Transformation([1, 2, 3, 4, 4]),
>        Transformation([1, 2, 3, 4, 5, 1]),
>        Transformation([1, 2, 3, 4, 5, 2]),
>        Transformation([1, 2, 3, 4, 5, 5]),
>        Transformation([1, 2, 3, 4, 5, 7, 7]),
>        Transformation([1, 2, 3, 4, 7, 6, 7]),
>        Transformation([1, 2, 3, 6, 5, 6]),
>        Transformation([1, 2, 3, 7, 5, 6, 7]),
>        Transformation([1, 2, 8, 4, 5, 6, 7, 8]),
>        Transformation([2, 2]));
true
gap> S := SymmetricInverseSemigroup(5);
<symmetric inverse monoid of degree 5>
gap> IdempotentGeneratedSubsemigroup(S);
<inverse partial perm monoid of rank 5 with 5 generators>
gap> S := DualSymmetricInverseSemigroup(5);
<inverse block bijection monoid of degree 5 with 3 generators>
gap> IdempotentGeneratedSubsemigroup(S);
<inverse block bijection monoid of degree 5 with 10 generators>
gap> IsSemilattice(last);
true

13.10 Maximal subsemigroups

The Semigroups package provides methods to calculate the maximal subsemigroups of a finite semigroup, subject to various conditions. A maximal subsemigroup of a semigroup is a proper subsemigroup that is contained in no other proper subsemigroup of the semigroup.

When computing the maximal subsemigroups of a regular Rees (0-)matrix semigroup over a group, additional functionality is available. As described in [GGR68], a maximal subsemigroup of a finite regular Rees (0-)matrix semigroup over a group is one of 6 possible types. Using the Semigroups package, it is possible to search for only those maximal subsemigroups of certain types.

A maximal subsemigroup of such a Rees (0-)matrix semigroup R over a group G is either:

  1. {0};

  2. formed by removing 0;

  3. formed by removing a column (a non-zero \(\mathscr{L}\)-class);

  4. formed by removing a row (a non-zero \(\mathscr{R}\)-class);

  5. formed by removing a set of both rows and columns;

  6. isomorphic to a Rees (0-)matrix semigroup of the same dimensions over a maximal subgroup of G (in particular, the maximal subsemigroup intersects every \(\mathscr{H}\)-class of R).

Note that if R is a Rees matrix semigroup then it has no maximal subsemigroups of types 1, 2, or 5. Only types 3, 4, and 6 are relevant to a Rees matrix semigroup.

13.10-1 MaximalSubsemigroups
‣ MaximalSubsemigroups( S )( attribute )
‣ MaximalSubsemigroups( S, opts )( operation )

Returns: The maximal subsemigroups of S.

If S is a finite semigroup, then the attribute MaximalSubsemigroups returns a list of the non-empty maximal subsemigroups of S. The methods used by MaximalSubsemigroups are based on [GGR68], and are described in [DMW16].

It is computationally expensive to search for the maximal subsemigroups of a semigroup, and so computations involving MaximalSubsemigroups may be very lengthy. A substantial amount of information on the progress of MaximalSubsemigroups is provided through the info class InfoSemigroups (2.6-1), with increasingly detailed information given at levels 1, 2, and 3.

The behaviour of MaximalSubsemigroups can be altered via the second argument opts, which should be a record. The optional components of opts are:

gens (a boolean)

If opts.gens is false or unspecified, then the maximal subsemigroups themselves are returned and not just generating sets for these subsemigroups.

It can be more computationally expensive to return the generating sets for the maximal subsemigroups, than to return the maximal subsemigroups themselves.

contain (a list)

If opts.contain is duplicate-free list of elements of S, then MaximalSubsemigroups will search for the maximal subsemigroups of S which contain those elements.

D (a \(\mathscr{D}\)-class)

For a maximal subsemigroup M of a finite semigroup S, there exists a unique \(\mathscr{D}\)-class which contains the complement of M in S. In other words, the elements of S which M lacks are contained in a unique \(\mathscr{D}\)-class.

If opts.D is a \(\mathscr{D}\)-class of S, then MaximalSubsemigroups will search exclusively for those maximal subsemigroups of S whose complement is contained in opts.D.

types (a list)

This option is relevant only if S is a regular Rees (0-)matrix semigroup over a group.

As described at the start of this subsection, 13.10, a maximal subsemigroup of a regular Rees (0-)matrix semigroup over a group is one of 6 possible types.

If S is a regular Rees (0-)matrix semigroup over a group and opts.types is a subset of [1 .. 6], then MaximalSubsemigroups will search for those maximal subsemigroups of S of the types enumerated by opts.types.

The default value for this option is [1 .. 6] (i.e. no restriction).

gap> S := FullTransformationSemigroup(3);
<full transformation monoid of degree 3>
gap> MaximalSubsemigroups(S);
[ <transformation semigroup of degree 3 with 7 generators>, 
  <transformation semigroup of degree 3 with 7 generators>, 
  <transformation semigroup of degree 3 with 7 generators>, 
  <transformation semigroup of degree 3 with 7 generators>, 
  <transformation monoid of degree 3 with 5 generators> ]
gap> MaximalSubsemigroups(S,
> rec(gens := true, D := DClass(S, Transformation([2, 2, 3]))));
[ [ Transformation( [ 1, 1, 1 ] ), Transformation( [ 3, 3, 3 ] ), 
      Transformation( [ 2, 2, 2 ] ), IdentityTransformation, 
      Transformation( [ 2, 3, 1 ] ), Transformation( [ 2, 1 ] ) ] ]
gap> MaximalSubsemigroups(S,
> rec(contain := [Transformation([2, 3, 1])]));
[ <transformation semigroup of degree 3 with 7 generators>, 
  <transformation monoid of degree 3 with 5 generators> ]
gap> R := PrincipalFactor(
> DClass(FullTransformationMonoid(4), Transformation([2, 2])));
<Rees 0-matrix semigroup 6x4 over Group([ (2,3,4), (2,4) ])>
gap> MaximalSubsemigroups(R, rec(types := [5],
>   contain := [RMSElement(R, 1, (), 1),
>               RMSElement(R, 1, (2, 3), 2)]));
[ <subsemigroup of 6x4 Rees 0-matrix semigroup with 10 generators>, 
  <subsemigroup of 6x4 Rees 0-matrix semigroup with 10 generators>, 
  <subsemigroup of 6x4 Rees 0-matrix semigroup with 10 generators>, 
  <subsemigroup of 6x4 Rees 0-matrix semigroup with 10 generators> ]

13.10-2 NrMaximalSubsemigroups
‣ NrMaximalSubsemigroups( S )( attribute )

Returns: The number of maximal subsemigroups of S.

If S is a finite semigroup, then NrMaximalSubsemigroups returns the number of non-empty maximal subsemigroups of S. The methods used by MaximalSubsemigroups are based on [GGR68], and are described in [DMW16].

It can be significantly faster to find the number of maximal subsemigroups of a semigroup than to find the maximal subsemigroups themselves.

Unless the maximal subsemigroups of S are already known, the command NrMaximalSubsemigroups(S) simply calls the command MaximalSubsemigroups(S, rec(number := true)).

For more information about searching for maximal subsemigroups of a finite semigroup in the Semigroups package, and for information about the options available to alter the search, see MaximalSubsemigroups (13.10-1). By supplying the additional option opts.number := true, the number of maximal subsemigroups will be returned rather than the subsemigroups themselves.

gap> S := FullTransformationSemigroup(3);
<full transformation monoid of degree 3>
gap> NrMaximalSubsemigroups(S);
5
gap> S := RectangularBand(3, 4);;
gap> NrMaximalSubsemigroups(S);
7
gap> R := PrincipalFactor(
> DClass(FullTransformationMonoid(4), Transformation([2, 2])));
<Rees 0-matrix semigroup 6x4 over Group([ (2,3,4), (2,4) ])>
gap> MaximalSubsemigroups(R, rec(number := true, types := [3, 4]));
10

13.10-3 IsMaximalSubsemigroup
‣ IsMaximalSubsemigroup( S, T )( operation )

Returns: true or false.

If S and T are semigroups, then IsMaximalSubsemigroup returns true if and only if T is a maximal subsemigroup of S.

A maximal subsemigroup of S is a proper subsemigroup of S which is contained in no other proper subsemigroup of S.

gap> S := ZeroSemigroup(2);;
gap> IsMaximalSubsemigroup(S, Semigroup(MultiplicativeZero(S)));
true
gap> S := FullTransformationSemigroup(4);
<full transformation monoid of degree 4>
gap> T := Semigroup(Transformation([3, 4, 1, 2]),
>                   Transformation([1, 4, 2, 3]),
>                   Transformation([2, 1, 1, 3]));
<transformation semigroup of degree 4 with 3 generators>
gap> IsMaximalSubsemigroup(S, T);
true
gap> R := Semigroup(Transformation([3, 4, 1, 2]),
>                   Transformation([1, 4, 2, 2]),
>                   Transformation([2, 1, 1, 3]));
<transformation semigroup of degree 4 with 3 generators>
gap> IsMaximalSubsemigroup(S, R);
false

13.11 The normalizer of a semigroup

13.11-1 Normalizer
‣ Normalizer( G, S[, opts] )( operation )
‣ Normalizer( S[, opts] )( operation )

Returns: A permutation group.

In its first form, this function returns the normalizer of the transformation, partial perm, or bipartition semigroup S in the permutation group G. In its second form, the normalizer of S in the symmetric group on [1 .. n] where n is the degree of S is returned.

The normalizer of a transformation semigroup S in a permutation group G in the subgroup H of G consisting of those elements in g in G conjugating S to S, i.e. S ^ g = S.

Analogous definitions can be given for a partial perm and bipartition semigroups.

The method used by this operation is based on Section 3 in [ABMN10].

The optional final argument opts allows you to specify various options, which determine how the normalizer is calculated. The values of these options can dramatically change the time it takes for this operation to complete. In different situations, different options give the best performance.

The argument opts should be a record, and the available options are:

random

If this option has the value true, then the non-deterministic algorithms in genss are used in Normalizer. So, there is some chance that Normalizer will return an incorrect result in this case, but these methods can also be much faster than the deterministic algorithms which are used if this option is false.

The default value for this option is false.

lambdastab

If this option has the value true, then Normalizer initially finds the setwise stabilizer of the images or right blocks of the semigroup S. Sometimes this improves the performance of Normalizer and sometimes it does not. If this option in false, then this setwise stabilizer is not found.

The default value for this option is true.

rhostab

If this option has the value true, then Normalizer initially finds the setwise stabilizer of the kernels, domains, or left blocks of the semigroup S. Sometimes this improves the performance of Normalizer and sometimes it does not. If this option is false, the this setwise stabilizer is not found.

If S is an inverse semigroup, then this option is ignored.

The default value for this option is true.

gap> S := BrauerMonoid(8);
<regular bipartition *-monoid of degree 8 with 3 generators>
gap> StructureDescription(Normalizer(S));
"S8"
gap> S := InverseSemigroup(PartialPerm([2, 5, 6, 3, 8]),
>                          PartialPerm([3, 6, 0, 2, 0, 0, 5, 7]));;
gap> Normalizer(S, rec(random := true, lambdastab := false));
#I  Have 33389 points.
#I  Have 40136 points in new orbit.
Group(())

13.12 Attributes of transformations and transformation semigroups

13.12-1 ComponentRepsOfTransformationSemigroup
‣ ComponentRepsOfTransformationSemigroup( S )( attribute )

Returns: The representatives of components of a transformation semigroup.

This function returns the representatives of the components of the action of the transformation semigroup S on the set of positive integers not greater than the degree of S.

The representatives are the least set of points such that every point can be reached from some representative under the action of S.

gap> S := Semigroup(
> Transformation([11, 11, 9, 6, 4, 1, 4, 1, 6, 7, 12, 5]),
> Transformation([12, 10, 7, 10, 4, 1, 12, 9, 11, 9, 1, 12]));;
gap> ComponentRepsOfTransformationSemigroup(S);
[ 2, 3, 8 ]

13.12-2 ComponentsOfTransformationSemigroup
‣ ComponentsOfTransformationSemigroup( S )( attribute )

Returns: The components of a transformation semigroup.

This function returns the components of the action of the transformation semigroup S on the set of positive integers not greater than the degree of S; the components of S partition this set.

gap> S := Semigroup(
> Transformation([11, 11, 9, 6, 4, 1, 4, 1, 6, 7, 12, 5]),
> Transformation([12, 10, 7, 10, 4, 1, 12, 9, 11, 9, 1, 12]));;
gap> ComponentsOfTransformationSemigroup(S);
[ [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 ] ]

13.12-3 CyclesOfTransformationSemigroup
‣ CyclesOfTransformationSemigroup( S )( attribute )

Returns: The cycles of a transformation semigroup.

This function returns the cycles, or strongly connected components, of the action of the transformation semigroup S on the set of positive integers not greater than the degree of S.

gap> S := Semigroup(
> Transformation([11, 11, 9, 6, 4, 1, 4, 1, 6, 7, 12, 5]),
> Transformation([12, 10, 7, 10, 4, 1, 12, 9, 11, 9, 1, 12]));;
gap> CyclesOfTransformationSemigroup(S);
[ [ 12 ], [ 1, 11 ], [ 1, 11, 12, 5, 4, 6 ], 
  [ 1, 11, 12, 5, 4, 10, 9, 6 ], [ 1, 12, 5, 4, 6 ], 
  [ 1, 12, 5, 4, 10, 9, 6 ], [ 1, 12, 5, 4, 10, 9, 11 ], 
  [ 11, 12, 5, 4, 10, 9 ], [ 12, 5, 4, 10, 7 ], [ 4, 10, 7 ] ]

13.12-4 DigraphOfActionOnPairs
‣ DigraphOfActionOnPairs( S )( attribute )
‣ DigraphOfActionOnPairs( S, n )( attribute )

Returns: A digraph, or fail.

If S is a transformation semigroup and n is a non-negative integer such that S acts on the points [1 .. n], then DigraphOfActionOnPairs(S, n) returns a digraph representing the OnSets (Reference: OnSets) action of S on the pairs of points in [1 .. n].

If the optional argument n is not specified, then by default the degree of S will be chosen for n; see DegreeOfTransformationSemigroup (Reference: DegreeOfTransformationSemigroup). If the semigroup S does not act on [1 .. n], then DigraphOfActionOnPairs(S, n) returns fail.

The digraph returned by DigraphOfActionOnPairs has n + n choose 2 vertices: the vertices [1 .. n] correspond to the points in [1 .. n], and the remaining vertices correspond to the pairs of points in [1 .. n]. This correspondence is stored in the vertex labels of the digraph; see DigraphVertexLabels (Digraphs: DigraphVertexLabels).

The edges of the digraph are defined as follows. For each pair {i, j} in [1 .. n], and for each generator f in GeneratorsOfSemigroup(S), there is an edge from the vertex corresponding to {i, j} to the vertex corresponding to {i ^ f, j ^ f}. Since f is a transformation, the set {i ^ f, j ^ f} may correspond to a pair (in the case that i ^ f <> j ^ f), or to a point (in the case that i ^ f = j ^ f). The label of an edge is the position of the first transformation within GeneratorsOfSemigroup(S) that maps the pair corresponding to the source vertex to the pair/point corresponding to the range vertex. See GeneratorsOfSemigroup (Reference: GeneratorsOfSemigroup) and DigraphEdgeLabels (Digraphs: DigraphEdgeLabels) for further information.

Note that the digraph returned by DigraphOfActionOnPairs has no multiple edges; see IsMultiDigraph (Digraphs: IsMultiDigraph).

gap> x := Transformation([2, 4, 3, 4, 7, 1, 6]);;
gap> y := Transformation([3, 3, 2, 3, 5, 1, 5]);;
gap> S := Semigroup(x, y);
<transformation semigroup of degree 7 with 2 generators>
gap> gr := DigraphOfActionOnPairs(S);
<digraph with 28 vertices, 41 edges>
gap> OnSets([2, 5], x);
[ 4, 7 ]
gap> DigraphVertexLabel(gr, 16);
[ 2, 5 ]
gap> DigraphVertexLabel(gr, 25);
[ 4, 7 ]
gap> DigraphEdgeLabel(gr, 16, 25);
1
gap> gr := DigraphOfActionOnPairs(S, 4);
<digraph with 10 vertices, 11 edges>
gap> DigraphVertexLabels(gr);
[ 1, 2, 3, 4, [ 1, 2 ], [ 1, 3 ], [ 1, 4 ], [ 2, 3 ], [ 2, 4 ], 
  [ 3, 4 ] ]
gap> DigraphOfActionOnPairs(S, 5);
fail

13.12-5 DigraphOfActionOnPoints
‣ DigraphOfActionOnPoints( S )( attribute )
‣ DigraphOfActionOnPoints( S, n )( attribute )

Returns: A digraph, or fail.

If S is a transformation semigroup and n is a non-negative integer such that S acts on the points [1 .. n], then DigraphOfActionOnPoints(S, n) returns a digraph representing the OnPoints (Reference: OnPoints) action of S on the set [1 .. n].

If the optional argument n is not specified, then by default the degree of S will be chosen for n; see DegreeOfTransformationSemigroup (Reference: DegreeOfTransformationSemigroup). If the semigroup S does not act on [1 .. n], then DigraphOfActionOnPairs(S, n) returns fail.

The digraph returned by DigraphOfActionOnPairs has n vertices, where the vertex i corresponds to the point i. For each point i in [1 .. n], and for each generator f in GeneratorsOfSemigroup(S), there is an edge from the vertex i to the vertex i ^ f. See GeneratorsOfSemigroup (Reference: GeneratorsOfSemigroup) for further information.

Note that the digraph returned by DigraphOfActionOnPoints has no multiple edges; see IsMultiDigraph (Digraphs: IsMultiDigraph).

gap> x := Transformation([2, 4, 2, 4, 7, 1, 6]);;
gap> y := Transformation([3, 3, 2, 3, 5, 1, 5]);;
gap> S := Semigroup(x, y);
<transformation semigroup of degree 7 with 2 generators>
gap> gr := DigraphOfActionOnPoints(S);
<digraph with 7 vertices, 12 edges>
gap> OnPoints(2, x);
4
gap> gr2 := DigraphOfActionOnPoints(S, 4);
<digraph with 4 vertices, 7 edges>
gap> gr2 = InducedSubdigraph(gr, [1 .. 4]);
true
gap> DigraphOfActionOnPoints(S, 5);
fail

13.12-6 FixedPointsOfTransformationSemigroup
‣ FixedPointsOfTransformationSemigroup( S )( attribute )

Returns: A set of positive integers.

If S is a transformation semigroup, then FixedPointsOfTransformationSemigroup(S) returns the set of points i in [1 .. DegreeOfTransformationSemigroup(S)] such that i ^ f = i for all f in S.

gap> f := Transformation([1, 4, 2, 4, 3, 7, 7]);
Transformation( [ 1, 4, 2, 4, 3, 7, 7 ] )
gap> S := Semigroup(f);
<commutative transformation semigroup of degree 7 with 1 generator>
gap> FixedPointsOfTransformationSemigroup(S);
[ 1, 4, 7 ]

13.12-7 IsTransitive
‣ IsTransitive( S[, X] )( property )
‣ IsTransitive( S[, n] )( property )

Returns: true or false.

A transformation semigroup S is transitive or strongly connected on the set X if for every i, j in X there is an element s in S such that i ^ s = j.

If the optional second argument is a positive integer n, then IsTransitive returns true if S is transitive on [1 .. n], and false if it is not.

If the optional second argument is not provided, then the degree of S is used by default; see DegreeOfTransformationSemigroup (Reference: DegreeOfTransformationSemigroup).

gap> S := Semigroup([
>  Bipartition([
>    [1, 2], [3, 6, -2], [4, 5, -3, -4], [-1, -6], [-5]]),
>  Bipartition([
>    [1, -4], [2, 3, 4, 5], [6], [-1, -6], [-2, -3], [-5]])]);
<bipartition semigroup of degree 6 with 2 generators>
gap> AsSemigroup(IsTransformationSemigroup, S);
<transformation semigroup of size 11, degree 12 with 2 generators>
gap> IsTransitive(last);
false
gap> IsTransitive(AsSemigroup(Group((1, 2, 3))));
true

13.12-8 SmallestElementSemigroup
‣ SmallestElementSemigroup( S )( attribute )
‣ LargestElementSemigroup( S )( attribute )

Returns: A transformation.

These attributes return the smallest and largest element of the transformation semigroup S, respectively. Smallest means the first element in the sorted set of elements of S and largest means the last element in the set of elements.

It is not necessary to find the elements of the semigroup to determine the smallest or largest element, and this function has considerable better performance than the equivalent Elements(S)[1] and Elements(S)[Size(S)].

gap> S := Monoid(
> Transformation([1, 4, 11, 11, 7, 2, 6, 2, 5, 5, 10]),
> Transformation([2, 4, 4, 2, 10, 5, 11, 11, 11, 6, 7]));
<transformation monoid of degree 11 with 2 generators>
gap> SmallestElementSemigroup(S);
IdentityTransformation
gap> LargestElementSemigroup(S);
Transformation( [ 11, 11, 10, 10, 7, 6, 5, 6, 2, 2, 4 ] )

13.12-9 CanonicalTransformation
‣ CanonicalTransformation( trans[, n] )( function )

Returns: A transformation.

If trans is a transformation, and n is a non-negative integer such that the restriction of trans to [1 .. n] defines a transformation of [1 .. n], then CanonicalTransformation returns a canonical representative of the transformation trans restricted to [1 .. n].

More specifically, let C(n) be a class of transformations of degree n such that AsDigraph returns isomorphic digraphs for every pair of element elements in C(n). Recall that for a transformation trans and integer n the function AsDigraph returns a digraph with n vertices and an edge with source x and range x^trans for every x in [1 .. n]. See AsDigraph (Digraphs: AsDigraph). Then CanonicalTransformation returns a canonical representative of the class C(n) that contains trans.

gap> x := Transformation([5, 1, 4, 1, 1]);
Transformation( [ 5, 1, 4, 1, 1 ] )
gap> y := Transformation([3, 3, 2, 3, 1]);
Transformation( [ 3, 3, 2, 3, 1 ] )
gap> CanonicalTransformation(x);
Transformation( [ 5, 5, 1, 5, 4 ] )
gap> CanonicalTransformation(y);
Transformation( [ 5, 5, 1, 5, 4 ] )

13.12-10 IsConnectedTransformationSemigroup
‣ IsConnectedTransformationSemigroup( S )( property )

Returns: true or false.

A transformation semigroup S is connected if the digraph returned by the function DigraphOfActionOnPoints is connected. See IsConnectedDigraph (Digraphs: IsConnectedDigraph) and DigraphOfActionOnPoints (13.12-5). The function IsConnectedTransformationSemigroup returns true if the semigroup S is connected and false otherwise.

gap> S := Semigroup([
>  Transformation([2, 4, 3, 4]),
>  Transformation([3, 3, 2, 3, 3])]);
<transformation semigroup of degree 5 with 2 generators>
gap> IsConnectedTransformationSemigroup(S);
true

13.13 Attributes of partial perm semigroups

13.13-1 ComponentRepsOfPartialPermSemigroup
‣ ComponentRepsOfPartialPermSemigroup( S )( attribute )

Returns: The representatives of components of a partial perm semigroup.

This function returns the representatives of the components of the action of the partial perm semigroup S on the set of positive integers where it is defined.

The representatives are the least set of points such that every point can be reached from some representative under the action of S.

gap> S := Semigroup([
> PartialPerm([1, 2, 3, 5, 6, 7, 8, 11, 12, 16, 19],
>             [9, 18, 20, 11, 5, 16, 8, 19, 14, 13, 1]),
> PartialPerm([1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 14, 16, 18, 19, 20],
>             [13, 1, 8, 5, 4, 14, 11, 12, 9, 20, 2, 18, 7, 3, 19])]);;
gap> ComponentRepsOfPartialPermSemigroup(S);
[ 1, 4, 6, 10, 15, 17 ]

13.13-2 ComponentsOfPartialPermSemigroup
‣ ComponentsOfPartialPermSemigroup( S )( attribute )

Returns: The components of a partial perm semigroup.

This function returns the components of the action of the partial perm semigroup S on the set of positive integers where it is defined; the components of S partition this set.

gap> S := Semigroup([
> PartialPerm([1, 2, 3, 5, 6, 7, 8, 11, 12, 16, 19],
>             [9, 18, 20, 11, 5, 16, 8, 19, 14, 13, 1]),
> PartialPerm([1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 14, 16, 18, 19, 20],
>             [13, 1, 8, 5, 4, 14, 11, 12, 9, 20, 2, 18, 7, 3, 19])]);;
gap> ComponentsOfPartialPermSemigroup(S);
[ [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 16, 18, 19, 20 ], 
  [ 15 ], [ 17 ] ]

13.13-3 CyclesOfPartialPerm
‣ CyclesOfPartialPerm( x )( attribute )

Returns: The cycles of a partial perm.

This function returns the cycles, or strongly connected components, of the action of the partial perm x on the set of positive integers where it is defined.

gap> x := PartialPerm([3, 1, 4, 2, 5, 0, 0, 6, 0, 7]);
[8,6][10,7](1,3,4,2)(5)
gap> CyclesOfPartialPerm(x);
[ [ 3, 4, 2, 1 ], [ 5 ] ]

13.13-4 CyclesOfPartialPermSemigroup
‣ CyclesOfPartialPermSemigroup( S )( attribute )

Returns: The cycles of a partial perm semigroup.

This function returns the cycles, or strongly connected components, of the action of the partial perm semigroup S on the set of positive integers where it is defined.

gap> S := Semigroup([
> PartialPerm([1, 2, 3, 5, 6, 7, 8, 11, 12, 16, 19],
>             [9, 18, 20, 11, 5, 16, 8, 19, 14, 13, 1]),
> PartialPerm([1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 14, 16, 18, 19, 20],
>             [13, 1, 8, 5, 4, 14, 11, 12, 9, 20, 2, 18, 7, 3, 19])]);;
gap> CyclesOfPartialPermSemigroup(S);
[ [ 1, 9, 12, 14, 2, 20, 19, 3, 8, 11 ] ]

The content in this chapter is based partly on work by Zachary Mesyan. A full description of the objects described can be found in [MM16].

13.14 Attributes of Rees (0-)matrix semigroups

13.14-1 RZMSDigraph
‣ RZMSDigraph( R )( attribute )

Returns: A digraph.

If R is an n by m Rees 0-matrix semigroup M^0[I, T, Λ; P] (so that I = {1,2,...,n} and Λ = {1,2,...,m}) then RZMSDigraph returns a symmetric bipartite digraph with n+m vertices. An index i ∈ I corresponds to the vertex i and an index j ∈ Λ corresponds to the vertex j + n.

Two vertices v and w in RZMSDigraph(R) are adjacent if and only if v∈ I, w - n∈ Λ, and P[w - n][v] ≠ 0.

This digraph is commonly called the Graham-Houghton graph of R.

gap> R := PrincipalFactor(
> DClass(FullTransformationMonoid(5),
>        Transformation([2, 4, 1, 5, 5])));
<Rees 0-matrix semigroup 10x5 over Group([ (1,2,3,4), (1,2) ])>
gap> gr := RZMSDigraph(R);
<digraph with 15 vertices, 40 edges>
gap> e := DigraphEdges(gr)[1];
[ 1, 11 ]
gap> Matrix(R)[e[2] - 10][e[1]] <> 0;
true

13.14-2 RZMSConnectedComponents
‣ RZMSConnectedComponents( R )( attribute )

Returns: The connected components of a Rees 0-matrix semigroup.

If R is an n by m Rees 0-matrix semigroup M^0[I, T, Λ; P] (so that I = {1,2,...,n} and Λ = {1,2,...,m}) then RZMSConnectedComponents returns the connected components of R.

Connectedness is an equivalence relation on the indices of R: the equivalence classes of the relation are called the connected components of R, and two indices in I ∪ Λ are connected if and only if their corresponding vertices in RZMSDigraph(R) are connected (see RZMSDigraph (13.14-1)). If R has n connected components, then RZMSConnectedComponents will return a list of pairs:

[ [ I_1, Λ_1 ], ..., [ I_k, Λ_k ] ]

where I = I_1 ⊔ ⋯ ⊔ I_k, Λ = Λ_1 ⊔ ⋯ ⊔ Λ_k, and for each l the set I_l∪Λ_l is a connected component of R. Note that at most one of I_l and Λ_l is possibly empty. The ordering of the connected components in the result in unspecified.

gap> R := ReesZeroMatrixSemigroup(SymmetricGroup(5),
> [[(), 0, (1, 3), (4, 5), 0],
>  [0, (), 0, 0, (1, 3, 4, 5)],
>  [0, 0, (1, 5)(2, 3), 0, 0],
>  [0, (2, 3)(1, 4), 0, 0, 0]]);
<Rees 0-matrix semigroup 5x4 over Sym( [ 1 .. 5 ] )>
gap> RZMSConnectedComponents(R);
[ [ [ 1, 3, 4 ], [ 1, 3 ] ], [ [ 2, 5 ], [ 2, 4 ] ] ]

13.15 Changing the representation of a semigroup

13.15-1 IsomorphismReesMatrixSemigroup
‣ IsomorphismReesMatrixSemigroup( S )( attribute )
‣ IsomorphismReesZeroMatrixSemigroup( S )( attribute )
‣ IsomorphismReesMatrixSemigroupOverPermGroup( S )( attribute )
‣ IsomorphismReesZeroMatrixSemigroupOverPermGroup( S )( attribute )

Returns: An isomorphism.

If the semigroup S is finite and simple, then IsomorphismReesMatrixSemigroup returns an isomorphism to a Rees matrix semigroup over some group (usually a permutation group), and IsomorphismReesMatrixSemigroupOverPermGroup returns an isomorphism to a Rees matrix semigroup over a permutation group.

If S is finite and 0-simple, then IsomorphismReesZeroMatrixSemigroup returns an isomorphism to a Rees 0-matrix semigroup over some group (usually a permutation group), and IsomorphismReesZeroMatrixSemigroupOverPermGroup returns an isomorphism to a Rees 0-matrix semigroup over a permutation group.

See also InjectionPrincipalFactor (12.4-7).

gap> S := Semigroup(PartialPerm([1]));
<trivial partial perm group of rank 1 with 1 generator>
gap> IsomorphismReesMatrixSemigroup(S);
MappingByFunction( <trivial partial perm group of rank 1 with
  1 generator>, <Rees matrix semigroup 1x1 over Group(())>
, function( x ) ... end, function( x ) ... end )
gap> S := Semigroup(PartialPerm([1]), PartialPerm([]));
<partial perm monoid of rank 1 with 2 generators>
gap> Range(IsomorphismReesZeroMatrixSemigroup(S));
<Rees 0-matrix semigroup 1x1 over Group(())>
 [Top of Book]  [Contents]   [Previous Chapter]   [Next Chapter] 
Goto Chapter: Top 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 Bib Ind

generated by GAPDoc2HTML