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

10 Green's relations
 10.1 Creating Green's classes and representatives
 10.2 Iterators and enumerators of classes and representatives
 10.3 Properties of Green's classes
 10.4 Attributes of Green's classes
 10.5 Operations for Green's relations and classes

10 Green's relations

In this chapter we describe the functions in Semigroups for computing Green's classes and related properties of semigroups.

10.1 Creating Green's classes and representatives

In this section, we describe the methods in the Semigroups package for creating Green's classes.

10.1-1 XClassOfYClass
‣ DClassOfHClass( class )( method )
‣ DClassOfLClass( class )( method )
‣ DClassOfRClass( class )( method )
‣ LClassOfHClass( class )( method )
‣ RClassOfHClass( class )( method )

Returns: A Green's class.

XClassOfYClass returns the X-class containing the Y-class class where X and Y should be replaced by an appropriate choice of D, H, L, and R.

Note that if it is not known to GAP whether or not the representative of class is an element of the semigroup containing class, then no attempt is made to check this.

The same result can be produced using:

First(GreensXClasses(S), x -> Representative(x) in class);

but this might be substantially slower. Note that XClassOfYClass is also likely to be faster than

GreensXClassOfElement(S, Representative(class));

DClass can also be used as a synonym for DClassOfHClass, DClassOfLClass, and DClassOfRClass; LClass as a synonym for LClassOfHClass; and RClass as a synonym for RClassOfHClass. See also GreensDClassOfElement (Reference: GreensDClassOfElement) and GreensDClassOfElementNC (10.1-3).

gap> S := Semigroup(Transformation([1, 3, 2]),
>                   Transformation([2, 1, 3]),
>                   Transformation([3, 2, 1]),
>                   Transformation([1, 3, 1]));;
gap> R := GreensRClassOfElement(S, Transformation([3, 2, 1]));
<Green's R-class: Transformation( [ 3, 2, 1 ] )>
gap> DClassOfRClass(R);
<Green's D-class: Transformation( [ 3, 2, 1 ] )>
gap> IsGreensDClass(DClassOfRClass(R));
true
gap> S := InverseSemigroup(
> PartialPerm([2, 6, 7, 0, 0, 9, 0, 1, 0, 5]),
> PartialPerm([3, 8, 1, 9, 0, 4, 10, 5, 0, 6]));
<inverse partial perm semigroup of rank 10 with 2 generators>
gap> x := S.1;
[3,7][8,1,2,6,9][10,5]
gap> H := HClass(S, x);
<Green's H-class: [3,7][8,1,2,6,9][10,5]>
gap> R := RClassOfHClass(H);
<Green's R-class: [3,7][8,1,2,6,9][10,5]>
gap> L := LClass(H);;
gap> L = LClass(S, PartialPerm([1, 2, 0, 0, 5, 6, 7, 0, 9]));
true
gap> DClass(R) = DClass(L);
true
gap> DClass(H) = DClass(L);
true

10.1-2 GreensXClassOfElement
‣ GreensDClassOfElement( X, f )( operation )
‣ DClass( X, f )( operation )
‣ GreensHClassOfElement( X, f )( operation )
‣ GreensHClassOfElement( R, i, j )( operation )
‣ HClass( X, f )( operation )
‣ HClass( R, i, j )( operation )
‣ GreensLClassOfElement( X, f )( operation )
‣ LClass( X, f )( operation )
‣ GreensRClassOfElement( X, f )( operation )
‣ RClass( X, f )( operation )

Returns: A Green's class.

These functions produce essentially the same output as the GAP library functions with the same names; see GreensDClassOfElement (Reference: GreensDClassOfElement). The main difference is that these functions can be applied to a wider class of objects:

GreensDClassOfElement and DClass

X must be a semigroup.

GreensHClassOfElement and HClass

X can be a semigroup, \(\mathscr{R}\)-class, \(\mathscr{L}\)-class, or \(\mathscr{D}\)-class.

If R is a IxJ Rees matrix semigroup or a Rees 0-matrix semigroup, and i and j are integers of the corresponding index sets, then GreensHClassOfElement returns the \(\mathscr{H}\)-class in row i and column j.

GreensLClassOfElement and LClass

X can be a semigroup or \(\mathscr{D}\)-class.

GreensRClassOfElement and RClass

X can be a semigroup or \(\mathscr{D}\)-class.

Note that GreensXClassOfElement and XClass are synonyms and have identical output. The shorter command is provided for the sake of convenience.

10.1-3 GreensXClassOfElementNC
‣ GreensDClassOfElementNC( X, f )( operation )
‣ DClassNC( X, f )( operation )
‣ GreensHClassOfElementNC( X, f )( operation )
‣ HClassNC( X, f )( operation )
‣ GreensLClassOfElementNC( X, f )( operation )
‣ LClassNC( X, f )( operation )
‣ GreensRClassOfElementNC( X, f )( operation )
‣ RClassNC( X, f )( operation )

Returns: A Green's class.

These functions are essentially the same as GreensDClassOfElement (10.1-2) except that no effort is made to verify if f is an element of X. More precisely, GreensXClassOfElementNC and XClassNC first check if f has already been shown to be an element of X. If it is not known to GAP if f is an element of X, then no further attempt to verify this is made.

Note that GreensXClassOfElementNC and XClassNC are synonyms and have identical output. The shorter command is provided for the sake of convenience.

It can be quicker to compute the class of an element using GreensRClassOfElementNC, say, than using GreensRClassOfElement if it is known a priori that f is an element of X. On the other hand, if f is not an element of X, then the results of this computation are unpredictable.

For example, if

x := Transformation([15, 18, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20]);

in the semigroup X of order-preserving mappings on 20 points, then

GreensRClassOfElementNC(X, x);

returns an answer relatively quickly, whereas

GreensRClassOfElement(X, x)

can take a significant amount of time to return a value.

See also GreensRClassOfElement (Reference: GreensRClassOfElement) and RClassOfHClass (10.1-1).

gap> S := RandomSemigroup(IsTransformationSemigroup, 2, 1000);;
gap> x := [1, 1, 2, 2, 2, 1, 1, 1, 1, 1, 2, 2, 2, 2, 1, 1, 2, 2, 1];;
gap> x := EvaluateWord(Generators(S), x);;
gap> R := GreensRClassOfElementNC(S, x);;
gap> Size(R);
1
gap> L := GreensLClassOfElementNC(S, x);;
gap> Size(L);
1
gap> x := PartialPerm([2, 3, 4, 5, 0, 0, 6, 8, 10, 11]);;
gap> L := LClass(POI(11), x);
<Green's L-class: [1,2,3,4,5][7,6][9,10,11](8)>
gap> Size(L);
165

10.1-4 GreensXClasses
‣ GreensDClasses( obj )( method )
‣ DClasses( obj )( method )
‣ GreensHClasses( obj )( method )
‣ HClasses( obj )( method )
‣ GreensJClasses( obj )( method )
‣ JClasses( obj )( method )
‣ GreensLClasses( obj )( method )
‣ LClasses( obj )( method )
‣ GreensRClasses( obj )( method )
‣ RClasses( obj )( method )

Returns: A list of Green's classes.

These functions produce essentially the same output as the GAP library functions with the same names; see GreensDClasses (Reference: GreensDClasses). The main difference is that these functions can be applied to a wider class of objects:

GreensDClasses and DClasses

X should be a semigroup.

GreensHClasses and HClasses

X can be a semigroup, \(\mathscr{R}\)-class, \(\mathscr{L}\)-class, or \(\mathscr{D}\)-class.

GreensLClasses and LClasses

X can be a semigroup or \(\mathscr{D}\)-class.

GreensRClasses and RClasses

X can be a semigroup or \(\mathscr{D}\)-class.

Note that GreensXClasses and XClasses are synonyms and have identical output. The shorter command is provided for the sake of convenience.

See also DClassReps (10.1-5), IteratorOfDClassReps (10.2-1), IteratorOfDClasses (10.2-2), and NrDClasses (10.1-9).

gap> S := Semigroup(Transformation([3, 4, 4, 4]),
>                   Transformation([4, 3, 1, 2]));;
gap> GreensDClasses(S);
[ <Green's D-class: Transformation( [ 3, 4, 4, 4 ] )>,
  <Green's D-class: Transformation( [ 4, 3, 1, 2 ] )>,
  <Green's D-class: Transformation( [ 4, 4, 4, 4 ] )> ]
gap> GreensRClasses(S);
[ <Green's R-class: Transformation( [ 3, 4, 4, 4 ] )>,
  <Green's R-class: Transformation( [ 4, 3, 1, 2 ] )>,
  <Green's R-class: Transformation( [ 4, 4, 4, 4 ] )>,
  <Green's R-class: Transformation( [ 4, 4, 3, 4 ] )>,
  <Green's R-class: Transformation( [ 4, 3, 4, 4 ] )>,
  <Green's R-class: Transformation( [ 4, 4, 4, 3 ] )> ]
gap> D := GreensDClasses(S)[1];
<Green's D-class: Transformation( [ 3, 4, 4, 4 ] )>
gap> GreensLClasses(D);
[ <Green's L-class: Transformation( [ 3, 4, 4, 4 ] )>,
  <Green's L-class: Transformation( [ 1, 2, 2, 2 ] )> ]
gap> GreensRClasses(D);
[ <Green's R-class: Transformation( [ 3, 4, 4, 4 ] )>,
  <Green's R-class: Transformation( [ 4, 4, 3, 4 ] )>,
  <Green's R-class: Transformation( [ 4, 3, 4, 4 ] )>,
  <Green's R-class: Transformation( [ 4, 4, 4, 3 ] )> ]
gap> R := GreensRClasses(D)[1];
<Green's R-class: Transformation( [ 3, 4, 4, 4 ] )>
gap> GreensHClasses(R);
[ <Green's H-class: Transformation( [ 3, 4, 4, 4 ] )>,
  <Green's H-class: Transformation( [ 1, 2, 2, 2 ] )> ]
gap> S := InverseSemigroup([
> PartialPerm([2, 4, 1]), PartialPerm([3, 0, 4, 1])]);;
gap> GreensDClasses(S);
[ <Green's D-class: <identity partial perm on [ 1, 2, 4 ]>>,
  <Green's D-class: <identity partial perm on [ 1, 3, 4 ]>>,
  <Green's D-class: <identity partial perm on [ 1, 3 ]>>,
  <Green's D-class: <identity partial perm on [ 4 ]>>,
  <Green's D-class: <empty partial perm>> ]
gap> GreensLClasses(S);
[ <Green's L-class: <identity partial perm on [ 1, 2, 4 ]>>,
  <Green's L-class: [4,2,1,3]>,
  <Green's L-class: <identity partial perm on [ 1, 3, 4 ]>>,
  <Green's L-class: <identity partial perm on [ 1, 3 ]>>,
  <Green's L-class: [3,1,2]>, <Green's L-class: [1,4][3,2]>,
  <Green's L-class: [1,3,4]>, <Green's L-class: [3,1,4]>,
  <Green's L-class: [1,2](3)>,
  <Green's L-class: <identity partial perm on [ 4 ]>>,
  <Green's L-class: [4,1]>, <Green's L-class: [4,3]>,
  <Green's L-class: [4,2]>, <Green's L-class: <empty partial perm>> ]
gap> D := GreensDClasses(S)[3];
<Green's D-class: <identity partial perm on [ 1, 3 ]>>
gap> GreensLClasses(D);
[ <Green's L-class: <identity partial perm on [ 1, 3 ]>>,
  <Green's L-class: [3,1,2]>, <Green's L-class: [1,4][3,2]>,
  <Green's L-class: [1,3,4]>, <Green's L-class: [3,1,4]>,
  <Green's L-class: [1,2](3)> ]
gap> GreensRClasses(D);
[ <Green's R-class: <identity partial perm on [ 1, 3 ]>>,
  <Green's R-class: [2,1,3]>, <Green's R-class: [2,3][4,1]>,
  <Green's R-class: [4,3,1]>, <Green's R-class: [4,1,3]>,
  <Green's R-class: [2,1](3)> ]

10.1-5 XClassReps
‣ DClassReps( obj )( attribute )
‣ HClassReps( obj )( attribute )
‣ LClassReps( obj )( attribute )
‣ RClassReps( obj )( attribute )

Returns: A list of representatives.

XClassReps returns a list of the representatives of the Green's classes of obj, which can be a semigroup, \(\mathscr{D}\)-, \(\mathscr{L}\)-, or \(\mathscr{R}\)-class where appropriate.

The same output can be obtained by calling, for example:

List(GreensXClasses(obj), Representative);

Note that if the Green's classes themselves are not required, then XClassReps will return an answer more quickly than the above, since the Green's class objects are not created.

See also GreensDClasses (10.1-4), IteratorOfDClassReps (10.2-1), IteratorOfDClasses (10.2-2), and NrDClasses (10.1-9).

gap> S := Semigroup(Transformation([3, 4, 4, 4]),
>                   Transformation([4, 3, 1, 2]));;
gap> DClassReps(S);
[ Transformation( [ 3, 4, 4, 4 ] ), Transformation( [ 4, 3, 1, 2 ] ),
  Transformation( [ 4, 4, 4, 4 ] ) ]
gap> LClassReps(S);
[ Transformation( [ 3, 4, 4, 4 ] ), Transformation( [ 1, 2, 2, 2 ] ),
  Transformation( [ 4, 3, 1, 2 ] ), Transformation( [ 4, 4, 4, 4 ] ),
  Transformation( [ 2, 2, 2, 2 ] ), Transformation( [ 3, 3, 3, 3 ] ),
  Transformation( [ 1, 1, 1, 1 ] ) ]
gap> D := GreensDClasses(S)[1];
<Green's D-class: Transformation( [ 3, 4, 4, 4 ] )>
gap> LClassReps(D);
[ Transformation( [ 3, 4, 4, 4 ] ), Transformation( [ 1, 2, 2, 2 ] ) ]
gap> RClassReps(D);
[ Transformation( [ 3, 4, 4, 4 ] ), Transformation( [ 4, 4, 3, 4 ] ),
  Transformation( [ 4, 3, 4, 4 ] ), Transformation( [ 4, 4, 4, 3 ] ) ]
gap> R := GreensRClasses(D)[1];;
gap> HClassReps(R);
[ Transformation( [ 3, 4, 4, 4 ] ), Transformation( [ 1, 2, 2, 2 ] ) ]
gap> S := SymmetricInverseSemigroup(6);;
gap> e := InverseSemigroup(Idempotents(S));;
gap> M := MunnSemigroup(e);;
gap> L := LClassNC(M, PartialPerm([51, 63], [51, 47]));;
gap> HClassReps(L);
[ <identity partial perm on [ 47, 51 ]>, [27,47](51), [50,47](51),
  [64,47](51), [63,47](51), [59,47](51) ]

10.1-6 MinimalDClass
‣ MinimalDClass( S )( attribute )

Returns: The minimal \(\mathscr{D}\)-class of a semigroup.

The minimal ideal of a semigroup is the least ideal with respect to containment. MinimalDClass returns the \(\mathscr{D}\)-class corresponding to the minimal ideal of the semigroup S. Equivalently, MinimalDClass returns the minimal \(\mathscr{D}\)-class with respect to the partial order of \(\mathscr{D}\)-classes.

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

See also PartialOrderOfDClasses (10.1-10), IsGreensLessThanOrEqual (Reference: IsGreensLessThanOrEqual), MinimalIdeal (11.7-1) and RepresentativeOfMinimalIdeal (11.7-2).

gap> D := MinimalDClass(JonesMonoid(8));
<Green's D-class: <bipartition: [ 1, 2 ], [ 3, 4 ], [ 5, 6 ],
  [ 7, 8 ], [ -1, -2 ], [ -3, -4 ], [ -5, -6 ], [ -7, -8 ]>>
gap> S := InverseSemigroup(
> PartialPerm([1, 2, 3, 5, 7, 8, 9], [2, 6, 9, 1, 5, 3, 8]),
> PartialPerm([1, 3, 4, 5, 7, 8, 9], [9, 4, 10, 5, 6, 7, 1]));;
gap> MinimalDClass(S);
<Green's D-class: <empty partial perm>>

10.1-7 MaximalXClasses
‣ MaximalDClasses( S )( attribute )
‣ MaximalLClasses( S )( attribute )
‣ MaximalRClasses( S )( attribute )

Returns: The maximal \(\mathscr{D}\), \(\mathscr{L}\), or \(\mathscr{R}\)-classes of a semigroup.

Let X be one of Green's \(\mathscr{D}\)-, \(\mathscr{L}\)-, or \(\mathscr{R}\)-relations. Then MaximalXClasses returns the maximal Green's X-classes with respect to the partial order of X-classes.

See also PartialOrderOfDClasses (10.1-10), IsGreensLessThanOrEqual (Reference: IsGreensLessThanOrEqual), and MinimalDClass (10.1-6).

gap> MaximalDClasses(BrauerMonoid(8));
[ <Green's D-class: <block bijection: [ 1, -1 ], [ 2, -2 ],
      [ 3, -3 ], [ 4, -4 ], [ 5, -5 ], [ 6, -6 ], [ 7, -7 ],
      [ 8, -8 ]>> ]
gap> MaximalDClasses(FullTransformationMonoid(5));
[ <Green's D-class: IdentityTransformation> ]
gap> S := Semigroup(
> PartialPerm([1, 2, 3, 4, 5, 6, 7], [3, 8, 1, 4, 5, 6, 7]),
> PartialPerm([1, 2, 3, 6, 8], [2, 6, 7, 1, 5]),
> PartialPerm([1, 2, 3, 4, 6, 8], [4, 3, 2, 7, 6, 5]),
> PartialPerm([1, 2, 4, 5, 6, 7, 8], [7, 1, 4, 2, 5, 6, 3]));;
gap> MaximalDClasses(S);
[ <Green's D-class: [2,8](1,3)(4)(5)(6)(7)>,
  <Green's D-class: [8,3](1,7,6,5,2)(4)> ]

10.1-8 NrRegularDClasses
‣ NrRegularDClasses( S )( attribute )
‣ RegularDClasses( S )( attribute )

Returns: A positive integer, or a list.

NrRegularDClasses returns the number of regular \(\mathscr{D}\)-classes of the semigroup S.

RegularDClasses returns a list of the regular \(\mathscr{D}\)-classes of the semigroup S.

See also IsRegularGreensClass (10.3-2) and IsRegularDClass (Reference: IsRegularDClass).

gap> S := Semigroup(Transformation([1, 3, 4, 1, 3, 5]),
>                   Transformation([5, 1, 6, 1, 6, 3]));;
gap> NrRegularDClasses(S);
3
gap> NrDClasses(S);
7
gap> AsSet(RegularDClasses(S));
[ <Green's D-class: Transformation( [ 1, 4, 1, 1, 4, 3 ] )>,
  <Green's D-class: Transformation( [ 1, 1, 1, 1, 1 ] )>,
  <Green's D-class: Transformation( [ 1, 1, 1, 1, 1, 1 ] )> ]

10.1-9 NrXClasses
‣ NrDClasses( obj )( attribute )
‣ NrHClasses( obj )( attribute )
‣ NrLClasses( obj )( attribute )
‣ NrRClasses( obj )( attribute )

Returns: A positive integer.

NrXClasses returns the number of Green's classes in obj where obj can be a semigroup, \(\mathscr{D}\)-, \(\mathscr{L}\)-, or \(\mathscr{R}\)-class where appropriate. If the actual Green's classes are not required, then it is more efficient to use

NrHClasses(obj)

than

Length(HClasses(obj))

since the Green's classes themselves are not created when NrXClasses is called.

See also GreensRClasses (10.1-4), GreensRClasses (Reference: GreensRClasses), IteratorOfRClasses (10.2-2), and

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> x := Transformation([2, 5, 4, 7, 4, 3, 6, 3]);;
gap> R := RClass(S, x);
<Green's R-class: Transformation( [ 2, 5, 4, 7, 4, 3, 6, 3 ] )>
gap> NrHClasses(R);
12
gap> D := DClass(R);
<Green's D-class: Transformation( [ 2, 5, 4, 7, 4, 3, 6, 3 ] )>
gap> NrHClasses(D);
72
gap> L := LClass(S, x);
<Green's L-class: Transformation( [ 2, 5, 4, 7, 4, 3, 6, 3 ] )>
gap> NrHClasses(L);
6
gap> NrHClasses(S);
1555
gap> S := Semigroup(Transformation([4, 6, 5, 2, 1, 3]),
>                   Transformation([6, 3, 2, 5, 4, 1]),
>                   Transformation([1, 2, 4, 3, 5, 6]),
>                   Transformation([3, 5, 6, 1, 2, 3]),
>                   Transformation([5, 3, 6, 6, 6, 2]),
>                   Transformation([2, 3, 2, 6, 4, 6]),
>                   Transformation([2, 1, 2, 2, 2, 4]),
>                   Transformation([4, 4, 1, 2, 1, 2]));;
gap> NrRClasses(S);
150
gap> Size(S);
6342
gap> x := Transformation([1, 3, 3, 1, 3, 5]);;
gap> D := DClass(S, x);
<Green's D-class: Transformation( [ 1, 3, 3, 1, 3, 5 ] )>
gap> NrRClasses(D);
87
gap> S := SymmetricInverseSemigroup(10);;
gap> NrDClasses(S); NrRClasses(S); NrHClasses(S); NrLClasses(S);
11
1024
184756
1024
gap> S := POPI(10);;
gap> NrDClasses(S);
11
gap> NrRClasses(S);
1024

10.1-10 PartialOrderOfXClasses
‣ PartialOrderOfDClasses( S )( attribute )
‣ PartialOrderOfLClasses( S )( attribute )
‣ PartialOrderOfRClasses( S )( attribute )

Returns: A digraph.

Let X be one of Green's \(\mathscr{D}\)-, \(\mathscr{L}\)-, or \(\mathscr{R}\)-relations. Then PartialOrderOfXClasses returns a digraph D where OutNeighbours(D)[i] contains every j such that GreensXClasses(S)[j] is immediately less than GreensXClasses(S)[i] in the partial order of X-classes of S. The reflexive transitive closure of the digraph D is the partial order of X-classes of S (in the sense of the Digraphs package).

The partial order on the X-classes is defined as follows.

Green's \(\mathscr{D}\)-relation:

\(x\leq y\) if and only if \(S ^ 1xS ^ 1\) is a subset of \(S ^ 1yS ^ 1\).

Green's \(\mathscr{L}\)-relation:

\(x\leq y\) if and only if \(S ^ 1x\) is a subset of \(S ^ 1y\).

Green's \(\mathscr{R}\)-relation:

\(x\leq y\) if and only if \(xS ^ 1\) is a subset of \(yS ^ 1\).

See also GreensDClasses (10.1-4), GreensDClasses (Reference: GreensDClasses), IsGreensLessThanOrEqual (Reference: IsGreensLessThanOrEqual), and \< (10.3-1).

gap> S := Semigroup(Transformation([2, 4, 1, 2]),
>                   Transformation([3, 3, 4, 1]));;
gap> PartialOrderOfDClasses(S);
<immutable digraph with 4 vertices, 3 edges>
gap> IsGreensLessThanOrEqual(GreensDClasses(S)[1],
>                            GreensDClasses(S)[2]);
false
gap> IsGreensLessThanOrEqual(GreensDClasses(S)[2],
>                            GreensDClasses(S)[1]);
false
gap> IsGreensLessThanOrEqual(GreensDClasses(S)[3],
>                            GreensDClasses(S)[1]);
true
gap> S := InverseSemigroup(
> PartialPerm([1, 2, 3], [1, 3, 4]),
> PartialPerm([1, 3, 5], [5, 1, 3]));;
gap> Size(S);
58
gap> PartialOrderOfDClasses(S);
<immutable digraph with 5 vertices, 4 edges>
gap> IsGreensLessThanOrEqual(GreensDClasses(S)[1],
>                            GreensDClasses(S)[2]);
false
gap> IsGreensLessThanOrEqual(GreensDClasses(S)[5],
>                            GreensDClasses(S)[2]);
true
gap> IsGreensLessThanOrEqual(GreensDClasses(S)[3],
>                            GreensDClasses(S)[4]);
false
gap> IsGreensLessThanOrEqual(GreensDClasses(S)[4],
>                            GreensDClasses(S)[3]);
true

10.1-11 LengthOfLongestDClassChain
‣ LengthOfLongestDClassChain( S )( attribute )

Returns: A non-negative integer.

If S is a semigroup, then LengthOfLongestDClassChain returns the length of the longest chain in the partial order defined by PartialOrderOfDClasses(S). See PartialOrderOfDClasses (10.1-10).

The partial order on the \(\mathscr{D}\)-classes is defined by \(x\leq y\) if and only if \(S ^ 1xS ^ 1\) is a subset of \(S ^ 1yS ^ 1\). A chain of \(\mathscr{D}\)-classes is a collection of n \(\mathscr{D}\)-classes \(D_{1}, D_{2}, \ldots D_{n}\) such that \(D_{1} < D_{2} < \cdots < D_{n}\). The length of such a chain is n - 1.

gap> S := TrivialSemigroup();;
gap> LengthOfLongestDClassChain(S);
0
gap> T := ZeroSemigroup(5);;
gap> LengthOfLongestDClassChain(T);
1
gap> U := MonogenicSemigroup(14, 7);;
gap> LengthOfLongestDClassChain(U);
13
gap> V := FullTransformationMonoid(6);
<full transformation monoid of degree 6>
gap> LengthOfLongestDClassChain(V);
5

10.1-12 IsGreensDGreaterThanFunc
‣ IsGreensDGreaterThanFunc( S )( attribute )

Returns: A function.

IsGreensDGreaterThanFunc(S) returns a function func such that for any two elements x and y of S, func(x, y) return true if the \(\mathscr{D}\)-class of x in S is greater than or equal to the \(\mathscr{D}\)-class of y in S under the usual ordering of Green's \(\mathscr{D}\)-classes of a semigroup.

gap> S := Semigroup(Transformation([1, 3, 4, 1, 3]),
>                   Transformation([2, 4, 1, 5, 5]),
>                   Transformation([2, 5, 3, 5, 3]),
>                   Transformation([5, 5, 1, 1, 3]));;
gap> reps := ShallowCopy(AsSet(DClassReps(S)));
[ Transformation( [ 1, 1, 1, 1, 1 ] ),
  Transformation( [ 1, 3, 1, 3, 3 ] ),
  Transformation( [ 1, 3, 4, 1, 3 ] ),
  Transformation( [ 2, 4, 1, 5, 5 ] ) ]
gap> Sort(reps, IsGreensDGreaterThanFunc(S));
gap> reps;
[ Transformation( [ 2, 4, 1, 5, 5 ] ),
  Transformation( [ 1, 3, 4, 1, 3 ] ),
  Transformation( [ 1, 3, 1, 3, 3 ] ),
  Transformation( [ 1, 1, 1, 1, 1 ] ) ]
gap> IsGreensLessThanOrEqual(DClass(S, reps[2]),
>                            DClass(S, reps[1]));
true
gap> S := DualSymmetricInverseMonoid(4);;
gap> IsGreensDGreaterThanFunc(S)(S.1, S.3);
true
gap> IsGreensDGreaterThanFunc(S)(S.3, S.1);
false
gap> IsGreensLessThanOrEqual(DClass(S, S.3),
>                            DClass(S, S.1));
true
gap> IsGreensLessThanOrEqual(DClass(S, S.1),
>                            DClass(S, S.3));
false

10.2 Iterators and enumerators of classes and representatives

In this section, we describe the methods in the Semigroups package for incrementally determining Green's classes or their representatives.

10.2-1 IteratorOfXClassReps
‣ IteratorOfDClassReps( S )( operation )
‣ IteratorOfHClassReps( S )( operation )
‣ IteratorOfLClassReps( S )( operation )

Returns: An iterator.

Returns an iterator of the representatives of the Green's classes contained in the semigroup S. See Reference: Iterators for more information on iterators.

See also GreensRClasses (Reference: GreensRClasses), GreensRClasses (10.1-4), and IteratorOfRClasses (10.2-2).

10.2-2 IteratorOfXClasses
‣ IteratorOfDClasses( S )( operation )
‣ IteratorOfRClasses( S )( operation )

Returns: An iterator.

Returns an iterator of the Green's classes in the semigroup S. See Reference: Iterators for more information on iterators.

This function is useful if you are, for example, looking for an \(\mathscr{R}\)-class of a semigroup with a particular property but do not necessarily want to compute all of the \(\mathscr{R}\)-classes.

See also GreensRClasses (10.1-4), GreensRClasses (Reference: GreensRClasses), and NrRClasses (10.1-9).

The transformation semigroup in the example below has 25147892 elements but it only takes a fraction of a second to find a non-trivial \(\mathscr{R}\)-class. The inverse semigroup of partial permutations in the example below has size 158122047816 but it only takes a fraction of a second to find an \(\mathscr{R}\)-class with more than 1000 elements.

gap> gens := [Transformation([2, 4, 1, 5, 4, 4, 7, 3, 8, 1]),
>             Transformation([3, 2, 8, 8, 4, 4, 8, 6, 5, 7]),
>             Transformation([4, 10, 6, 6, 1, 2, 4, 10, 9, 7]),
>             Transformation([6, 2, 2, 4, 9, 9, 5, 10, 1, 8]),
>             Transformation([6, 4, 1, 6, 6, 8, 9, 6, 2, 2]),
>             Transformation([6, 8, 1, 10, 6, 4, 9, 1, 9, 4]),
>             Transformation([8, 6, 2, 3, 3, 4, 8, 6, 2, 9]),
>             Transformation([9, 1, 2, 8, 1, 5, 9, 9, 9, 5]),
>             Transformation([9, 3, 1, 5, 10, 3, 4, 6, 10, 2]),
>             Transformation([10, 7, 3, 7, 1, 9, 8, 8, 4, 10])];;
gap> S := Semigroup(gens);;
gap> iter := IteratorOfRClasses(S);
<iterator>
gap> for R in iter do
>   if Size(R) > 1 then
>     break;
>   fi;
> od;
gap> R;
<Green's R-class: Transformation( [ 6, 4, 1, 6, 6, 8, 9, 6, 2, 2 ] )>
gap> Size(R);
21600
gap> S := InverseSemigroup(
>  PartialPerm([1, 2, 3, 4, 5, 6, 7, 10, 11, 19, 20],
>              [19, 4, 11, 15, 3, 20, 1, 14, 8, 13, 17]),
>  PartialPerm([1, 2, 3, 4, 6, 7, 8, 14, 15, 16, 17],
>              [15, 14, 20, 19, 4, 5, 1, 13, 11, 10, 3]),
>  PartialPerm([1, 2, 4, 6, 7, 8, 9, 10, 14, 15, 18],
>              [7, 2, 17, 10, 1, 19, 9, 3, 11, 16, 18]),
>  PartialPerm([1, 2, 3, 4, 5, 7, 8, 9, 11, 12, 13, 16],
>              [8, 3, 18, 1, 4, 13, 12, 7, 19, 20, 2, 11]),
>  PartialPerm([1, 2, 3, 4, 5, 6, 7, 9, 11, 15, 16, 17, 20],
>              [7, 17, 13, 4, 6, 9, 18, 10, 11, 19, 5, 2, 8]),
>  PartialPerm([1, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 15, 18],
>              [10, 20, 11, 7, 13, 8, 4, 9, 2, 18, 17, 6, 15]),
>  PartialPerm([1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 13, 14, 17, 18],
>              [10, 20, 18, 1, 14, 16, 9, 5, 15, 4, 8, 12, 19, 11]),
>  PartialPerm([1, 2, 3, 4, 5, 6, 7, 9, 10, 11, 12, 15, 16, 19, 20],
>              [13, 6, 1, 2, 11, 7, 16, 18, 9, 10, 4, 14, 15, 5, 17]),
>  PartialPerm([1, 2, 3, 4, 6, 7, 8, 9, 10, 11, 12, 14, 15, 16, 20],
>              [5, 3, 12, 9, 20, 15, 8, 16, 13, 1, 17, 11, 14, 10, 2]),
>  PartialPerm([1, 2, 3, 4, 6, 7, 8, 9, 10, 11, 13, 17, 18, 19, 20],
>              [8, 3, 9, 20, 2, 12, 14, 15, 4, 18, 13, 1, 17, 19, 5]));;
gap> iter := IteratorOfRClasses(S);
<iterator>
gap> repeat
>   R := NextIterator(iter);
> until Size(R) > 1000;
gap> R;
<Green's R-class: [8,19,14][11,4][13,15,5][17,20]>
gap> Size(R);
10020240

10.3 Properties of Green's classes

In this section, we describe the properties and operators of Green's classes that are available in the Semigroups package.

10.3-1 Less than for Green's classes
‣ \<( left-expr, right-expr )( method )

Returns: true or false.

The Green's class left-expr is less than or equal to right-expr if they belong to the same semigroup and the representative of left-expr is less than the representative of right-expr under <; see also Representative (Reference: Representative).

Please note that this is not the usual order on the Green's classes of a semigroup as defined in Reference: Green's Relations. See also IsGreensLessThanOrEqual (Reference: IsGreensLessThanOrEqual).

gap> S := FullTransformationSemigroup(4);;
gap> A := GreensRClassOfElement(S, Transformation([2, 1, 3, 1]));
<Green's R-class: Transformation( [ 2, 1, 3, 1 ] )>
gap> B := GreensRClassOfElement(S, Transformation([1, 2, 3, 4]));
<Green's R-class: IdentityTransformation>
gap> A < B;
false
gap> B < A;
true
gap> IsGreensLessThanOrEqual(A, B);
true
gap> IsGreensLessThanOrEqual(B, A);
false
gap> S := SymmetricInverseSemigroup(4);;
gap> A := GreensJClassOfElement(S, PartialPerm([1, 3, 4]));;
gap> B := GreensJClassOfElement(S, PartialPerm([3, 1]));;
gap> A < B;
true
gap> B < A;
false
gap> IsGreensLessThanOrEqual(A, B);
false
gap> IsGreensLessThanOrEqual(B, A);
true

10.3-2 IsRegularGreensClass
‣ IsRegularGreensClass( class )( property )

Returns: true or false.

This function returns true if class is a regular Green's class and false if it is not. See also IsRegularDClass (Reference: IsRegularDClass), IsGroupHClass (Reference: IsGroupHClass), GroupHClassOfGreensDClass (Reference: GroupHClassOfGreensDClass), GroupHClass (10.4-1), NrIdempotents (11.9-2), Idempotents (11.9-1), and IsRegularSemigroupElement (Reference: IsRegularSemigroupElement).

The function IsRegularDClass produces the same output as the GAP library functions with the same name; see IsRegularDClass (Reference: IsRegularDClass).

gap> S := Monoid(Transformation([10, 8, 7, 4, 1, 4, 10, 10, 7, 2]),
>                Transformation([5, 2, 5, 5, 9, 10, 8, 3, 8, 10]));;
gap> f := Transformation([1, 1, 10, 8, 8, 8, 1, 1, 10, 8]);;
gap> R := RClass(S, f);;
gap> IsRegularGreensClass(R);
true
gap> S := Monoid(Transformation([2, 3, 4, 5, 1, 8, 7, 6, 2, 7]),
>                Transformation([3, 8, 7, 4, 1, 4, 3, 3, 7, 2]));;
gap> f := Transformation([3, 8, 7, 4, 1, 4, 3, 3, 7, 2]);;
gap> R := RClass(S, f);;
gap> IsRegularGreensClass(R);
false
gap> NrIdempotents(R);
0
gap> S := Semigroup(Transformation([2, 1, 3, 1]),
>                   Transformation([3, 1, 2, 1]),
>                   Transformation([4, 2, 3, 3]));;
gap> f := Transformation([4, 2, 3, 3]);;
gap> L := GreensLClassOfElement(S, f);;
gap> IsRegularGreensClass(L);
false
gap> R := GreensRClassOfElement(S, f);;
gap> IsRegularGreensClass(R);
false
gap> g := Transformation([4, 4, 4, 4]);;
gap> IsRegularSemigroupElement(S, g);
true
gap> IsRegularGreensClass(LClass(S, g));
true
gap> IsRegularGreensClass(RClass(S, g));
true
gap> IsRegularDClass(DClass(S, g));
true
gap> DClass(S, g) = RClass(S, g);
false

10.3-3 IsGreensClassNC
‣ IsGreensClassNC( class )( property )

Returns: true or false.

A Green's class class of a semigroup S satisfies IsGreensClassNC if it was not known to GAP that the representative of class was an element of S at the point that class was created.

10.4 Attributes of Green's classes

In this section, we describe the attributes of Green's classes that are available in the Semigroups package.

10.4-1 GroupHClass
‣ GroupHClass( class )( attribute )

Returns: A group \(\mathscr{H}\)-class of the \(\mathscr{D}\)-class class if it is regular and fail if it is not.

GroupHClass is a synonym for GroupHClassOfGreensDClass (Reference: GroupHClassOfGreensDClass).

See also IsGroupHClass (Reference: IsGroupHClass), IsRegularDClass (Reference: IsRegularDClass), IsRegularGreensClass (10.3-2), and IsRegularSemigroup (12.1-17).

gap> S := Semigroup(Transformation([2, 6, 7, 2, 6, 1, 1, 5]),
>                   Transformation([3, 8, 1, 4, 5, 6, 7, 1]));;
gap> IsRegularSemigroup(S);
false
gap> iter := IteratorOfDClasses(S);;
gap> repeat D := NextIterator(iter); until IsRegularDClass(D);
gap> D;
<Green's D-class: Transformation( [ 6, 1, 1, 6, 1, 2, 2, 6 ] )>
gap> NrIdempotents(D);
12
gap> NrRClasses(D);
8
gap> NrLClasses(D);
4
gap> GroupHClass(D);
<Green's H-class: Transformation( [ 1, 2, 2, 1, 2, 6, 6, 1 ] )>
gap> GroupHClassOfGreensDClass(D);
<Green's H-class: Transformation( [ 1, 2, 2, 1, 2, 6, 6, 1 ] )>
gap> StructureDescription(GroupHClass(D));
"S3"
gap> repeat D := NextIterator(iter); until not IsRegularDClass(D);
gap> D;
<Green's D-class: Transformation( [ 7, 5, 2, 2, 6, 1, 1, 2 ] )>
gap> IsRegularDClass(D);
false
gap> GroupHClass(D);
fail
gap> S := InverseSemigroup(
> PartialPerm([2, 1, 6, 0, 3]), PartialPerm([3, 5, 2, 0, 0, 6]));;
gap> x := PartialPerm([1 .. 3], [6, 3, 1]);;
gap> First(DClasses(S), x -> not IsTrivial(GroupHClass(x)));
<Green's D-class: <identity partial perm on [ 1, 2 ]>>
gap> StructureDescription(GroupHClass(last));
"C2"

10.4-2 SchutzenbergerGroup
‣ SchutzenbergerGroup( class )( attribute )

Returns: A group.

SchutzenbergerGroup returns the generalized Schutzenberger group (defined below) of the \(\mathscr{R}\)-, \(\mathscr{D}\)-, \(\mathscr{L}\)-, or \(\mathscr{H}\)-class class.

If f is an element of a semigroup of transformations or partial permutations and im(f) denotes the image of f, then the generalized Schutzenberger group of im(f) is the permutation group

\[ \{\:g|_{\textrm{im}(f)}\::\:\textrm{im}(f*g)=\textrm{im}(f)\:\}. \]

The generalized Schutzenberger group of the kernel ker(f) of a transformation f or the domain dom(f) of a partial permutation f is defined analogously.

The generalized Schutzenberger group of a Green's class is then defined as follows.

\(\mathscr{R}\)-class

The generalized Schutzenberger group of the image or range of the representative of the \(\mathscr{R}\)-class.

\(\mathscr{L}\)-class

The generalized Schutzenberger group of the kernel or domain of the representative of the \(\mathscr{L}\)-class.

\(\mathscr{H}\)-class

The intersection of the generalized Schutzenberger groups of the \(\mathscr{R}\)- and \(\mathscr{L}\)-class containing the \(\mathscr{H}\)-class.

\(\mathscr{D}\)-class

The intersection of the generalized Schutzenberger groups of the \(\mathscr{R}\)- and \(\mathscr{L}\)-class containing the representative of the \(\mathscr{D}\)-class.

The output of this attribute is difficult to describe for other types of semigroup. However, a general description is given in [EENMP19].

gap> S := Semigroup(Transformation([4, 4, 3, 5, 3]),
>                   Transformation([5, 1, 1, 4, 1]),
>                   Transformation([5, 5, 4, 4, 5]));;
gap> f := Transformation([5, 5, 4, 4, 5]);;
gap> SchutzenbergerGroup(RClass(S, f));
Group([ (4,5) ])
gap> S := InverseSemigroup(
> PartialPerm([1, 2, 3, 7],
>             [9, 2, 4, 8]),
> PartialPerm([1, 2, 6, 7, 8, 9, 10],
>             [6, 8, 4, 5, 9, 1, 3]),
> PartialPerm([1, 2, 3, 5, 6, 7, 8, 9],
>             [7, 4, 1, 6, 9, 5, 2, 3]));;
gap> List(DClasses(S), SchutzenbergerGroup);
[ Group(()), Group(()), Group(()), Group(()), Group([ (4,9) ]),
  Group(()), Group(()), Group([ (5,8,6), (5,8) ]), Group(()),
  Group(()), Group(()), Group(()), Group(()), Group(()),
  Group([ (1,7,5,6,9,3) ]), Group([ (1,6)(3,5) ]), Group(()),
  Group(()), Group(()), Group(()), Group(()), Group(()), Group(()) ]

10.4-3 StructureDescriptionSchutzenbergerGroups
‣ StructureDescriptionSchutzenbergerGroups( S )( attribute )

Returns: Distinct structure descriptions of the Schutzenberger groups of a semigroup.

StructureDescriptionSchutzenbergerGroups returns the distinct values of StructureDescription (Reference: StructureDescription) when it is applied to the Schutzenberger groups of the \(\mathscr{R}\)-classes of the semigroup S.

gap> S := Semigroup([
>  PartialPerm([1, 2, 3], [2, 5, 4]),
>  PartialPerm([1, 2, 3], [4, 1, 2]),
>  PartialPerm([1, 2, 3], [5, 2, 3]),
>  PartialPerm([1, 2, 4, 5], [2, 1, 4, 3]),
>  PartialPerm([1, 2, 5], [2, 3, 5]),
>  PartialPerm([1, 2, 3, 5], [2, 3, 5, 4]),
>  PartialPerm([1, 2, 3, 5], [4, 2, 5, 1]),
>  PartialPerm([1, 2, 3, 5], [5, 2, 4, 3]),
>  PartialPerm([1, 2, 5], [5, 4, 3])]);;
gap> StructureDescriptionSchutzenbergerGroups(S);
[ "1", "C2", "S3" ]
gap> S := Monoid(
> Bipartition([[1, 2, 5, -1, -2], [3, 4, -3, -5], [-4]]),
> Bipartition([[1, 2, -2], [3, -1], [4], [5], [-3, -4], [-5]]),
> Bipartition([[1], [2, 3, -5], [4, -3], [5, -2], [-1, -4]]));
<bipartition monoid of degree 5 with 3 generators>
gap> StructureDescriptionSchutzenbergerGroups(S);
[ "1", "C2" ]

10.4-4 StructureDescriptionMaximalSubgroups
‣ StructureDescriptionMaximalSubgroups( S )( attribute )

Returns: Distinct structure descriptions of the maximal subgroups of a semigroup.

StructureDescriptionMaximalSubgroups returns the distinct values of StructureDescription (Reference: StructureDescription) when it is applied to the maximal subgroups of the semigroup S.

gap> S := DualSymmetricInverseSemigroup(6);
<inverse block bijection monoid of degree 6 with 3 generators>
gap> StructureDescriptionMaximalSubgroups(S);
[ "1", "C2", "S3", "S4", "S5", "S6" ]
gap> S := Semigroup(
>  PartialPerm([1, 3, 4, 5, 8],
>              [8, 3, 9, 4, 5]),
>  PartialPerm([1, 2, 3, 4, 8],
>              [10, 4, 1, 9, 6]),
>  PartialPerm([1, 2, 3, 4, 5, 6, 7, 10],
>              [4, 1, 6, 7, 5, 3, 2, 10]),
>  PartialPerm([1, 2, 3, 4, 6, 8, 10],
>              [4, 9, 10, 3, 1, 5, 2]));;
gap> StructureDescriptionMaximalSubgroups(S);
[ "1", "C2", "C3", "C4" ]

10.4-5 MultiplicativeNeutralElement
‣ MultiplicativeNeutralElement( H )( method )

Returns: A semigroup element or fail.

If the \(\mathscr{H}\)-class H of a semigroup S is a subgroup of S, then MultiplicativeNeutralElement returns the identity of H. If H is not a subgroup of S, then fail is returned.

gap> S := Semigroup([PartialPerm([1, 5, 2]),
>  PartialPerm([2, 0, 4]), PartialPerm([4, 1, 5]),
>  PartialPerm([1, 0, 3, 0, 4]), PartialPerm([1, 2, 0, 3, 5]),
>  PartialPerm([1, 3, 2, 0, 5]), PartialPerm([5, 0, 0, 4, 3])]);;
gap> H := HClass(S, PartialPerm([1, 2]));;
gap> MultiplicativeNeutralElement(H);
<identity partial perm on [ 1, 2 ]>
gap> H := HClass(S, PartialPerm([1, 4]));;
gap> MultiplicativeNeutralElement(H);
fail

10.4-6 StructureDescription
‣ StructureDescription( class )( attribute )

Returns: A string or fail.

StructureDescription returns the value of StructureDescription (Reference: StructureDescription) when it is applied to a group isomorphic to the group \(\mathscr{H}\)-class class. If class is not a group \(\mathscr{H}\)-class, then fail is returned.

gap> S := Semigroup(
> PartialPerm([1, 2, 3, 4, 6, 7, 8, 9],
>             [1, 9, 4, 3, 5, 2, 10, 7]),
> PartialPerm([1, 2, 4, 7, 8, 9],
>             [6, 2, 4, 9, 1, 3]));;
gap> H := HClass(S, PartialPerm([1, 2, 3, 4, 7, 9],
>                               [1, 7, 3, 4, 9, 2]));;
gap> StructureDescription(H);
"C6"

10.4-7 InjectionPrincipalFactor
‣ InjectionPrincipalFactor( D )( attribute )
‣ InjectionNormalizedPrincipalFactor( D )( attribute )
‣ IsomorphismReesMatrixSemigroup( D )( attribute )

Returns: A injective mapping.

If the \(\mathscr{D}\)-class D is a subsemigroup of a semigroup S, then the principal factor of D is just D itself. If D is not a subsemigroup of S, then the principal factor of D is the semigroup with elements D and a new element 0 with multiplication of \(x,y\in 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. \]

InjectionPrincipalFactor returns an injective function from the \(\mathscr{D}\)-class D to a Rees (0-)matrix semigroup, which contains the principal factor of D as a subsemigroup.

If D is a subsemigroup of its parent semigroup, then the function returned by InjectionPrincipalFactor or IsomorphismReesMatrixSemigroup is an isomorphism from D to a Rees matrix semigroup; see ReesMatrixSemigroup (Reference: ReesMatrixSemigroup).

If D is not a semigroup, then the function returned by InjectionPrincipalFactor is an injective function from D to a Rees 0-matrix semigroup isomorphic to the principal factor of D; see ReesZeroMatrixSemigroup (Reference: ReesZeroMatrixSemigroup). In this case, IsomorphismReesMatrixSemigroup and IsomorphismReesZeroMatrixSemigroup returns an error.

InjectionNormalizedPrincipalFactor returns the composition of InjectionPrincipalFactor with RZMSNormalization (6.5-6) or RMSNormalization (6.5-7) as appropriate.

See also PrincipalFactor (10.4-8).

gap> S := InverseSemigroup(
> PartialPerm([1, 2, 3, 6, 8, 10],
>             [2, 6, 7, 9, 1, 5]),
> PartialPerm([1, 2, 3, 4, 6, 7, 8, 10],
>             [3, 8, 1, 9, 4, 10, 5, 6]));;
gap> x := PartialPerm([1, 2, 5, 6, 7, 9],
>                     [1, 2, 5, 6, 7, 9]);;
gap> D := GreensDClassOfElement(S, x);
<Green's D-class: <identity partial perm on [ 1, 2, 5, 6, 7, 9 ]>>
gap> R := Range(InjectionPrincipalFactor(D));
<Rees 0-matrix semigroup 3x3 over Group(())>
gap> MatrixOfReesZeroMatrixSemigroup(R);
[ [ (), 0, 0 ], [ 0, (), 0 ], [ 0, 0, () ] ]
gap> Size(R);
10
gap> Size(D);
9
gap> S := Semigroup(
> Bipartition([[1, 2, 3, -3, -5], [4], [5, -2], [-1, -4]]),
> Bipartition([[1, 3, 5], [2, 4, -3], [-1, -2, -4, -5]]),
> Bipartition([[1, 5, -2, -4], [2, 3, 4, -1, -5], [-3]]),
> Bipartition([[1, 5, -1, -2, -3], [2, 4, -4], [3, -5]]));;
gap> D := GreensDClassOfElement(S,
> Bipartition([[1, 5, -2, -4], [2, 3, 4, -1, -5], [-3]]));
<Green's D-class: <bipartition: [ 1, 5, -2, -4 ], [ 2, 3, 4, -1, -5 ]
   , [ -3 ]>>
gap> InjectionNormalizedPrincipalFactor(D);
MappingByFunction( <Green's D-class: <bipartition: [ 1, 5, -2, -4 ],
  [ 2, 3, 4, -1, -5 ], [ -3 ]>>, <Rees matrix semigroup 1x1 over
  Group([ (1,2) ])>, function( x ) ... end, function( x ) ... end )

10.4-8 PrincipalFactor
‣ PrincipalFactor( D )( attribute )
‣ NormalizedPrincipalFactor( D )( attribute )

Returns: A Rees (0-)matrix semigroup.

If D is a \(\mathscr{D}\)-class of semigroup, then PrincipalFactor(D) is just shorthand for Range(InjectionPrincipalFactor(D)), and NormalizedPrincipalFactor(D) is shorthand for Range(InjectionNormalizedPrincipalFactor(D)).

See InjectionPrincipalFactor (10.4-7) and InjectionNormalizedPrincipalFactor (10.4-7) for more details.

gap> S := Semigroup([PartialPerm([1, 2, 3], [1, 3, 4]),
>  PartialPerm([1, 2, 3], [2, 5, 3]),
>  PartialPerm([1, 2, 3, 4], [2, 4, 1, 5]),
>  PartialPerm([1, 3, 5], [5, 1, 3])]);;
gap> PrincipalFactor(MinimalDClass(S));
<Rees matrix semigroup 1x1 over Group(())>
gap> MultiplicativeZero(S);
<empty partial perm>
gap> S := Semigroup(
> Bipartition([[1, 2, 3, 4, 5, -1, -3], [-2, -5], [-4]]),
> Bipartition([[1, -5], [2, 3, 4, 5, -1, -3], [-2, -4]]),
> Bipartition([[1, 5, -4], [2, 4, -1, -5], [3, -2, -3]]));;
gap> D := MinimalDClass(S);
<Green's D-class: <bipartition: [ 1, 2, 3, 4, 5, -1, -3 ],
  [ -2, -5 ], [ -4 ]>>
gap> NormalizedPrincipalFactor(D);
<Rees matrix semigroup 1x5 over Group(())>

10.5 Operations for Green's relations and classes

In this section, we describe some operations related to Green's classes that are available in the Semigroups package.

10.5-1 LeftGreensMultiplier
‣ LeftGreensMultiplier( S, a, b )( operation )
‣ RightGreensMultiplier( S, a, b )( operation )

Returns: An element.

If S is a semigroup, and a and b are \(\mathscr{L}\)-related elements of S, then LeftGreensMultiplier returns an element s such that s * a = b. The element s is of the same type as the elements of S but may or may not be an element of S. In particular, if S is not a monoid and a = b, then One(GeneratorsOfSemigroup(S)) may be returned. Even if a <> b, then it is not guaranteed that the returned element s will belong to S. It is guaranteed that the left action of s on the elements of the \(\mathscr{L}\)-class of a is the same as the left action of an element of S with the identity adjoined.

LeftGreensMultiplier gives an error if a and b are not \(\mathscr{L}\)-related elements of S.

The operation RightGreensMultiplier is defined analogously.

gap> S := Semigroup(Transformation([4, 4, 3, 5, 3]),
>                   Transformation([5, 1, 1, 4, 1]),
>                   Transformation([5, 5, 4, 4, 5]));;
gap> a := Transformation([5, 5, 4, 4, 5]);;
gap> LeftGreensMultiplier(S, a, a);
Transformation( [ 1, 1, 3, 3, 1 ] )
gap> RightGreensMultiplier(S, a, a);
Transformation( [ 5, 5, 5, 4, 5 ] )
gap> b := Transformation([5, 4, 4, 5, 4]);
Transformation( [ 5, 4, 4, 5, 4 ] )
gap> s := LeftGreensMultiplier(S, a, b);
Transformation( [ 1, 3, 3, 1, 3 ] )
gap> s * a;
Transformation( [ 5, 4, 4, 5, 4 ] )
gap> b := Transformation([4, 4, 5, 5, 4]);
Transformation( [ 4, 4, 5, 5, 4 ] )
gap> s := RightGreensMultiplier(S, a, b);
Transformation( [ 4, 4, 4, 5, 4 ] )
gap> a * s = b;
true
 [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 Bib Ind

generated by GAPDoc2HTML