In this chapter we describe the functions in Semigroups for determining the structure of a semigroup, in particular for computing Green's classes and related properties of semigroups.
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.
‣ 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 returns the equivalent of:
Product(List(w, i-> gens[i]));
see also Factorization (4.1-2).
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.
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> f:=Transformation( [ 1, 4, 6, 1, 7, 2, 7, 6 ] );; gap> Factorization(S, f); [ 4, 2 ] gap> EvaluateWord(gens, last); Transformation( [ 1, 4, 6, 1, 7, 2, 7, 6 ] ) gap> S:=SymmetricInverseMonoid(10);; gap> f:=PartialPerm( [ 1, 2, 3, 6, 8, 10 ], [ 2, 6, 7, 9, 1, 5 ] ); [3,7][8,1,2,6,9][10,5] gap> Factorization(S, f); [ -2, -2, -2, -2, -3, -4, -3, -2, -2, -2, -2, -3, -2, 2, 2, 2, 2, 4, 4, 4, 4, 2, 2, 2, 2, 2, 3, 4, -3, -2, -3, -2, -3, -2, 2, 2, 2, 2, 2, 3, 4, -3, -2, -3, -2, -3, -2, 2, 2, 2, 2, 2, 3, 4, -3, -2, -3, -2, -3, -2, 2, 2, 2, 2, 2, 3, 4, -3, -2, -3, -2, -3, -2, 2, 2, 2, 2, 2, 3, 4, -3, -2, -3, -2, -3, -2, 3, 2, 2, 2, 2, 2, 3, 4, -3, -2, -3, -2, -3, -2, 2, 3, 2, 3, 2, 2, 2, 3, 2, 2, 2, 2, 2, 3, 2, 3, 2 ] gap> EvaluateWord(GeneratorsOfSemigroup(S), last); [3,7][8,1,2,6,9][10,5]
‣ Factorization( S, f ) | ( operation ) |
Returns: A word in the generators.
When S is a semigroup and f belongs to S, Factorization return a word in the generators of S that is equal to f. In this case, a word is a list of positive integers where i corresponds to GeneratorsOfSemigroups(S)[i]. More specifically,
EvaluateWord(GeneratorsOfSemigroup(S), Factorization(S, f))=f;
When S is a inverse semigroup and f belongs to S, Factorization return a word in the generators of S that is equal to f. In this case, a word is a list of non-zero integers where i corresponds to GeneratorsOfSemigroup(S)[i] and -i corresponds to GeneratorsOfSemigroup(S)[i]^-1. As in the previous case,
EvaluateWord(GeneratorsOfSemigroup(S), Factorization(S, f))=f;
Note that Factorization does not return a word of minimum length.
See also EvaluateWord (4.1-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> f:=Transformation( [ 1, 10, 2, 10, 1, 2, 7, 10, 2, 7 ] );; gap> Factorization(S, f); [ 2, 2, 1, 2 ] gap> EvaluateWord(gens, last); Transformation( [ 1, 10, 2, 10, 1, 2, 7, 10, 2, 7 ] ) gap> S:=SymmetricInverseMonoid(8); <symmetric inverse monoid of degree 8> gap> f:=PartialPerm( [ 1, 2, 3, 4, 5, 8 ], [ 7, 1, 4, 3, 2, 6 ] ); [5,2,1,7][8,6](3,4) gap> Factorization(S, f); [ -2, -2, -2, -2, -2, -2, -2, 2, 2, 4, 4, 2, 3, 2, 3, -2, -2, -2, 2, 3, 2, 3, -2, -2, -2, 2, 3, 2, 3, -2, -2, -2, 3, 2, 3, 2, 3, -2, -2, -2, 3, 2, 3, 2, 3, -2, -2, -2, 2, 3, 2, 3, -2, -2, -2, 2, 3, 2, 3, -2, -2, -2, 2, 3, 2, 3, -2, -2, -2, 2, 3, 2, 3, -2, -2, -2, 3, 2, 3, 2, 3, -2, -2, -2, 2, 3, 2, 3, -2, -2, -2, 2, 3, 2, 3, -2, -2, -2, 2, 3, 2, 3, -2, -2, -2, 2, 3, 2, 2, 3, 2, 2, 2, 2 ] gap> EvaluateWord(GeneratorsOfSemigroup(S), last); [5,2,1,7][8,6](3,4) gap> S:=DualSymmetricInverseMonoid(6);; gap> f:=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> Factorization(S, f); [ -2, -2, -2, -2, -2, 4, 2 ] gap> EvaluateWord(GeneratorsOfSemigroup(S), last); <block bijection: [ 1, 6, -4 ], [ 2, -2, -3 ], [ 3, -5 ], [ 4, -6 ], [ 5, -1 ]>
‣ 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 (4.2-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([ 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 ])); <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); <Green's L-class: <identity partial perm on [ 1, 2, 5, 6, 7, 9 ]>> gap> DClass(R) = DClass(L); true gap> DClass(H) = DClass(L); true
‣ GreensDClassOfElement( X, f ) | ( operation ) |
‣ DClass( X, f ) | ( function ) |
‣ GreensHClassOfElement( X, f ) | ( operation ) |
‣ GreensHClassOfElement( R, i, j ) | ( operation ) |
‣ HClass( X, f ) | ( function ) |
‣ HClass( R, i, j ) | ( function ) |
‣ GreensLClassOfElement( X, f ) | ( operation ) |
‣ LClass( X, f ) | ( function ) |
‣ GreensRClassOfElement( X, f ) | ( operation ) |
‣ RClass( X, f ) | ( function ) |
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 DClassX must be a semigroup.
GreensHClassOfElement and HClassX 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 LClassX can be a semigroup or \(\mathscr{D}\)-class.
GreensRClassOfElement and RClassX 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.
‣ GreensDClassOfElementNC( X, f ) | ( operation ) |
‣ DClassNC( X, f ) | ( function ) |
‣ GreensHClassOfElementNC( X, f ) | ( operation ) |
‣ HClassNC( X, f ) | ( function ) |
‣ GreensLClassOfElementNC( X, f ) | ( operation ) |
‣ LClassNC( X, f ) | ( function ) |
‣ GreensRClassOfElementNC( X, f ) | ( operation ) |
‣ RClassNC( X, f ) | ( function ) |
Returns: A Green's class.
These functions are essentially the same as GreensDClassOfElement (4.2-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 signficant amount of time to return a value.
See also GreensRClassOfElement (Reference: GreensRClassOfElement) and RClassOfHClass (4.2-1).
gap> S := RandomTransformationSemigroup(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([ 1, 2, 3, 4, 7, 8, 9, 10 ], > [ 2, 3, 4, 5, 6, 8, 10, 11 ]);; gap> L := LClass(POI(13), x); <Green's L-class: [1,2,3,4,5,6,8,11][7,10]> gap> Size(L); 1287
‣ 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), IsRegularClass (4.4-4), and IsRegularSemigroup (4.6-14).
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( [ 1, 2, 3, 5 ], [ 2, 1, 6, 3 ] ), > PartialPerm( [ 1, 2, 3, 6 ], [ 3, 5, 2, 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"
‣ 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 DClassesX should be a semigroup.
GreensHClasses and HClassesX can be a semigroup, \(\mathscr{R}\)-class, \(\mathscr{L}\)-class, or \(\mathscr{D}\)-class.
GreensLClasses and LClassesX can be a semigroup or \(\mathscr{D}\)-class.
GreensRClasses and RClassesX 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 (4.3-4), IteratorOfDClassReps (4.3-2), IteratorOfDClasses (4.3-3), and NrDClasses (4.4-6).
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( [ 1, 2, 3 ], [ 2, 4, 1 ] ), > PartialPerm( [ 1, 3, 4 ], [ 3, 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 [ 2, 4 ]>>, <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 [ 2, 4 ]>>, <Green's L-class: [2,3][4,1]>, <Green's L-class: [4,2,1]>, <Green's L-class: [4,2,3]>, <Green's L-class: [2,4,3]>, <Green's L-class: [2,1](4)>, <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 [ 2, 4 ]>> gap> GreensLClasses(D); [ <Green's L-class: <identity partial perm on [ 2, 4 ]>>, <Green's L-class: [2,3][4,1]>, <Green's L-class: [4,2,1]>, <Green's L-class: [4,2,3]>, <Green's L-class: [2,4,3]>, <Green's L-class: [2,1](4)> ] gap> GreensRClasses(D); [ <Green's R-class: <identity partial perm on [ 2, 4 ]>>, <Green's R-class: [1,4][3,2]>, <Green's R-class: [1,2,4]>, <Green's R-class: [3,2,4]>, <Green's R-class: [3,4,2]>, <Green's R-class: [1,2](4)> ]
‣ IteratorOfDClassReps( S ) | ( function ) |
‣ IteratorOfHClassReps( S ) | ( function ) |
‣ IteratorOfLClassReps( S ) | ( function ) |
‣ IteratorOfRClassReps( S ) | ( function ) |
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 (4.3-1), and IteratorOfRClasses (4.3-3).
gap> gens := [ Transformation( [ 3, 2, 1, 5, 4 ] ), > Transformation( [ 5, 4, 3, 2, 1 ] ), > Transformation( [ 5, 4, 3, 2, 1 ] ), Transformation( [ 5, 5, 4, 5, 1 ] ), > Transformation( [ 4, 5, 4, 3, 3 ] ) ];; gap> S := Semigroup(gens);; gap> iter := IteratorOfRClassReps(S); <iterator> gap> NextIterator(iter); Transformation( [ 3, 2, 1, 5, 4 ] ) gap> NextIterator(iter); Transformation( [ 5, 5, 4, 5, 1 ] ) gap> iter; <iterator> gap> file := Concatenation(SemigroupsDir(), "/tst/test.gz");; gap> S := InverseSemigroup(ReadGenerators(file, 1377)); <inverse partial perm semigroup of rank 983 with 2 generators> gap> NrMovedPoints(S); 983 gap> iter := IteratorOfLClassReps(S); <iterator> gap> NextIterator(iter); <partial perm on 634 pts with degree 1000, codegree 1000>
‣ IteratorOfDClasses( S ) | ( function ) |
‣ IteratorOfHClasses( S ) | ( function ) |
‣ IteratorOfLClasses( S ) | ( function ) |
‣ IteratorOfRClasses( S ) | ( function ) |
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 (4.3-1), GreensRClasses (Reference: GreensRClasses), NrRClasses (4.4-6), and IteratorOfRClassReps (4.3-2).
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,3][11,5][13,1][15,2][17,6][19,7]> gap> Size(r); 10020240
‣ 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 (4.3-1), IteratorOfDClassReps (4.3-2), IteratorOfDClasses (4.3-3), and NrDClasses (4.4-6).
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> DClassReps(M); [ <identity partial perm on [ 51 ]>, <identity partial perm on [ 27, 51 ]>, <identity partial perm on [ 15, 27, 50, 51 ]>, <identity partial perm on [ 8, 15, 26, 27, 49, 50, 51, 64 ]>, <identity partial perm on [ 4, 8, 14, 15, 25, 26, 27, 48, 49, 50, 51, 60, 61, 62, 63, 64 ]>, <identity partial perm on [ 2, 4, 7, 8, 13, 14, 15, 21, 25, 26, 27, 29, 34, 39, 44, 48, 49, \ 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64 ]>, <identity partial perm on [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 1\ 9, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36,\ 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 5\ 4, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64 ]> ] gap> L := LClassNC(M, PartialPerm( [ 51, 63 ], [ 51, 47 ] ));; gap> HClassReps(L); [ <identity partial perm on [ 47, 51 ]>, [27,47](51), [50,47](51), [59,47](51), [63,47](51), [64,47](51) ]
‣ \<( 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 ], [ 1, 3, 4 ]) ); <Green's D-class: <identity partial perm on [ 1, 2, 3 ]>> gap> B := GreensJClassOfElement(S, PartialPerm([ 1, 2 ], [ 3, 1 ]) ); <Green's D-class: <identity partial perm on [ 1, 2 ]>> gap> A < B; false gap> B < A; true gap> IsGreensLessThanOrEqual(A, B); false gap> IsGreensLessThanOrEqual(B, A); true
‣ InjectionPrincipalFactor( 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∈ 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 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 returns an error.
See also PrincipalFactor (4.4-3).
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> InjectionPrincipalFactor(d);;
gap> rms := Range(last);
<Rees 0-matrix semigroup 3x3 over Group(())>
gap> MatrixOfReesZeroMatrixSemigroup(rms);
[ [ (), 0, 0 ], [ 0, (), 0 ], [ 0, 0, () ] ]
gap> Size(rms);
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 := DClasses(S)[3];
<Green's D-class: <bipartition: [ 1, 5, -2, -4 ], [ 2, 3, 4, -1, -5 ]
, [ -3 ]>>
gap> inj := InjectionPrincipalFactor(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( f ) ... end, function( x ) ... end )‣ PrincipalFactor( D ) | ( attribute ) |
Returns: A Rees matrix semigroup.
PrincipalFactor(D) is just shorthand for Range(InjectionPrincipalFactor(D)), where D is a \(\mathscr{D}\)-class of semigroup; see InjectionPrincipalFactor (4.4-2) 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> PrincipalFactor(D); <Rees matrix semigroup 1x5 over Group(())>
‣ IsRegularClass( 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 (4.2-4), NrIdempotents (4.5-4), Idempotents (4.5-3), 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> IsRegularClass(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> IsRegularClass(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> IsRegularClass(L); false gap> R := GreensRClassOfElement(S, f);; gap> IsRegularClass(R); false gap> g := Transformation( [ 4, 4, 4, 4 ] );; gap> IsRegularSemigroupElement(S, g); true gap> IsRegularClass(LClass(S, g)); true gap> IsRegularClass(RClass(S, g)); true gap> IsRegularDClass(DClass(S, g)); true gap> DClass(S, g)=RClass(S, g); true
‣ 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 IsRegularClass (4.4-4) 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> RegularDClasses(S); [ <Green's D-class: Transformation( [ 1, 4, 1, 1, 4, 3 ] )>, <Green's D-class: Transformation( [ 1, 1, 1, 1, 1, 4 ] )>, <Green's D-class: Transformation( [ 1, 1, 1, 1, 1, 1 ] )> ]
‣ 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 (4.3-1), GreensRClasses (Reference: GreensRClasses), IteratorOfRClasses (4.3-3), and IteratorOfRClassReps (4.3-2).
gap> gens := [ 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> S := Semigroup(gens);; 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> gens := [ 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> S := Semigroup(gens);; 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( [ 2, 4, 2, 2, 2, 1 ] )> 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
‣ PartialOrderOfDClasses( S ) | ( attribute ) |
Returns: The partial order of the \(\mathscr{D}\)-classes of S.
Returns a list list where list[i] contains every j such that GreensDClasses(S)[j] is immediately less than GreensDClasses(S)[i] in the partial order of \(\mathscr{D}\)- classes of S. There might be other indices in list, and it may or may not include i. The reflexive transitive closure of the relation defined by list is the partial order of \(\mathscr{D}\)-classes of S.
The partial order on the \(\mathscr{D}\)-classes is defined by x≤ y if and only if S^1xS^1 is a subset of S^1yS^1.
See also GreensDClasses (4.3-1), GreensDClasses (Reference: GreensDClasses), IsGreensLessThanOrEqual (Reference: IsGreensLessThanOrEqual), and \< (4.4-1).
gap> S := Semigroup( Transformation( [ 2, 4, 1, 2 ] ), > Transformation( [ 3, 3, 4, 1 ] ) );; gap> PartialOrderOfDClasses(S); [ [ 3 ], [ 2, 3 ], [ 3, 4 ], [ 4 ] ] 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); [ [ 1, 3 ], [ 2, 3 ], [ 3, 4 ], [ 4, 5 ], [ 5 ] ] 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
‣ 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.
The generalized Schutzenberger group of the image or range of the representative of the \(\mathscr{R}\)-class.
The generalized Schutzenberger group of the kernel or domain of the representative of the \(\mathscr{L}\)-class.
The intersection of the generalized Schutzenberger groups of the \(\mathscr{R}\)- and \(\mathscr{L}\)-class containing the \(\mathscr{H}\)-class.
The intersection of the generalized Schutzenberger groups of the \(\mathscr{R}\)- and \(\mathscr{L}\)-class containing the representative of the \(\mathscr{D}\)-class.
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([ (1,9,8), (8, 9) ]), Group([ (4,9) ]), Group(()), Group(()), Group(()), Group(()), Group(()), Group(()), Group(()), Group(()), Group(()), Group(()), Group([ (2,5)(3,7) ]), Group([ (1,7,5,6,9,3) ]), Group(()), Group(()), Group(()), Group(()), Group(()) ]
‣ 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 (4.4-7), IsGreensLessThanOrEqual (Reference: IsGreensLessThanOrEqual), MinimalIdeal (4.5-10) and RepresentativeOfMinimalIdeal (4.5-11).
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>>
‣ MaximalDClasses( S ) | ( attribute ) |
Returns: The maximal \(\mathscr{D}\)-classes of a semigroup.
MaximalDClasses returns the maximal \(\mathscr{D}\)-classes with respect to the partial order of \(\mathscr{D}\)-classes.
See also PartialOrderOfDClasses (4.4-7), IsGreensLessThanOrEqual (Reference: IsGreensLessThanOrEqual), and MinimalDClass (4.4-9).
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)> ]
‣ 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" ]
‣ 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 bipartition 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" ]
‣ 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, 2, 3 ], [ 1, 5, 2 ] ), > PartialPerm( [ 1, 3 ], [ 2, 4 ] ), > PartialPerm( [ 1, 2, 3 ], [ 4, 1, 5 ] ), > PartialPerm( [ 1, 3, 5 ], [ 1, 3, 4 ] ), > PartialPerm( [ 1, 2, 4, 5 ], [ 1, 2, 3, 5 ] ), > PartialPerm( [ 1, 2, 3, 5 ], [ 1, 3, 2, 5 ] ), > PartialPerm( [ 1, 4, 5 ], [ 5, 4, 3 ] ) );; gap> H := HClass(S, PartialPerm( [ 1, 2 ], [ 1, 2 ] ));; gap> MultiplicativeNeutralElement(H); <identity partial perm on [ 1, 2 ]> gap> H := HClass(S, PartialPerm( [ 1, 2 ], [ 1, 4 ] ));; gap> MultiplicativeNeutralElement(H); fail
‣ 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.
‣ IsTransformationSemigroupGreensClass( class ) | ( property ) |
Returns: true or false.
A Green's class class of a semigroup S satisfies the property IsTransformationSemigroupGreensClass if and only if S is a semigroup of transformations.
‣ IsBipartitionSemigroupGreensClass( class ) | ( property ) |
Returns: true or false.
A Green's class class of a semigroup S satisfies the property IsBipartitionSemigroupGreensClass if and only if S is a semigroup of bipartitions.
‣ IsPartialPermSemigroupGreensClass( class ) | ( property ) |
Returns: true or false.
A Green's class class of a semigroup S satisfies the property IsPartialPermSemigroupGreensClass if and only if S is a semigroup of partial perms.
‣ IsMatrixSemigroupGreensClass( class ) | ( property ) |
Returns: true or false.
A Green's class class of a semigroup S satisfies the property IsMatrixSemigroupGreensClass if and only if S is belongs to the category IsMatrixSemigroup.
‣ 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"
‣ IsGreensDLeq( S ) | ( attribute ) |
Returns: A function.
IsGreensDLeq(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(DClassReps(S)); [ Transformation( [ 1, 3, 4, 1, 3 ] ), Transformation( [ 2, 4, 1, 5, 5 ] ), Transformation( [ 1, 4, 1, 1, 4 ] ), Transformation( [ 1, 1, 1, 1, 1 ] ) ] gap> Sort(reps, IsGreensDLeq(S)); gap> reps; [ Transformation( [ 2, 4, 1, 5, 5 ] ), Transformation( [ 1, 3, 4, 1, 3 ] ), Transformation( [ 1, 4, 1, 1, 4 ] ), Transformation( [ 1, 1, 1, 1, 1 ] ) ] gap> IsGreensLessThanOrEqual(DClass(S, reps[2]), DClass(S, reps[1])); true gap> S := DualSymmetricInverseMonoid(4);; gap> IsGreensDLeq(S)(S.1, S.3); true gap> IsGreensDLeq(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
In this section we describe the attributes of a semigroup that can be found using the Semigroups package.
‣ 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.
Generators(S) is a synonym for GeneratorsOfGroup (Reference: GeneratorsOfGroup).
Generators(S) is a synonym for GeneratorsOfSemigroupIdeal (3.2-1).
Generators(S) is a synonym for GeneratorsOfSemigroup (Reference: GeneratorsOfSemigroup).
Generators(S) is a synonym for GeneratorsOfMonoid (Reference: GeneratorsOfMonoid).
Generators(S) is a synonym for GeneratorsOfInverseSemigroup (Reference: GeneratorsOfInverseSemigroup).
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 ] ) ]
‣ GroupOfUnits( S ) | ( attribute ) |
Returns: The group of units of a semigroup.
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 (2.4-2) 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 (4.6-11), 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"
‣ 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), IsRegularClass (4.4-4) IsGroupHClass (Reference: IsGroupHClass), NrIdempotents (4.5-4), and GroupHClass (4.2-4).
gap> S := Semigroup([ Transformation( [ 2, 3, 4, 1 ] ), > Transformation( [ 3, 3, 1, 1 ] ) ]);; gap> Idempotents(S, 1); [ ] gap> Idempotents(S, 2); [ Transformation( [ 1, 1, 3, 3 ] ), Transformation( [ 1, 3, 3, 1 ] ), Transformation( [ 2, 2, 4, 4 ] ), Transformation( [ 4, 2, 2, 4 ] ) ] gap> Idempotents(S); [ IdentityTransformation, Transformation( [ 1, 1, 3, 3 ] ), 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); <Green's R-class: Transformation( [ 3, 3, 1, 1 ] )> 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> Idempotents(L); [ Transformation( [ 2, 2, 4, 4 ] ), Transformation( [ 4, 2, 2, 4 ] ) ] gap> D := DClassOfLClass(L); <Green's D-class: Transformation( [ 1, 1, 3, 3 ] )> gap> Idempotents(D); [ Transformation( [ 1, 1, 3, 3 ] ), Transformation( [ 2, 2, 4, 4 ] ), Transformation( [ 1, 3, 3, 1 ] ), Transformation( [ 4, 2, 2, 4 ] ) ] gap> L := GreensLClassOfElement(S, Transformation( [ 3, 1, 1, 3 ] ));; gap> 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( [ 1, 2, 3, 4, 5, 7 ], [ 10, 6, 3, 4, 9, 1 ] ), > PartialPerm( [ 1, 2, 3, 4, 5, 6, 7, 8 ], > [ 6, 10, 7, 4, 8, 2, 9, 1 ] ) ]);; gap> Idempotents(S, 1); [ <identity partial perm on [ 4 ]> ] gap> Idempotents(S, 0); [ ]
‣ 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 (4.5-3), IsRegularDClass (Reference: IsRegularDClass), IsRegularClass (4.4-4) IsGroupHClass (Reference: IsGroupHClass), and GroupHClass (4.2-4).
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
‣ IdempotentGeneratedSubsemigroup( S ) | ( attribute ) |
Returns: A semigroup.
IdempotentGeneratedSubsemigroup returns the subsemigroup of the semigroup S generated by the idempotents of S.
See also Idempotents (4.5-3) and SmallGeneratingSet (4.5-14).
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 bipartition monoid of degree 5 with 3 generators> gap> IdempotentGeneratedSubsemigroup(S); <inverse bipartition monoid of degree 5 with 10 generators> gap> IsSemilattice(last); true
‣ 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(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 := RandomBipartitionSemigroup(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 ]> ]
‣ MaximalSubsemigroups( S ) | ( attribute ) |
Returns: The maximal subsemigroups of S.
If S is a semigroup, then MaximalSubsemigroups returns a list of the maximal subsemigroups of S.
A maximal subsemigroup of S is a proper subsemigroup of S which is contained in no other proper subsemigroups of S.
The method for this function are based on [GGR68].
Please note: the Grape package version 4.5 or higher must be available and compiled for this function to work.
gap> S := FullTransformationSemigroup(4); <full transformation monoid of degree 4> gap> MaximalSubsemigroups(S); [ <transformation semigroup of degree 4 with 3 generators>, <transformation semigroup of degree 4 with 4 generators>, <transformation semigroup of degree 4 with 4 generators>, <transformation semigroup of degree 4 with 4 generators>, <transformation semigroup of degree 4 with 5 generators>, <transformation semigroup of degree 4 with 4 generators>, <transformation semigroup of degree 4 with 5 generators>, <transformation semigroup of degree 4 with 5 generators>, <transformation semigroup of degree 4 with 4 generators> ] gap> D := DClass(S, Transformation([ 2, 2 ])); <Green's D-class: Transformation( [ 2, 3, 1, 2 ] )> gap> R := PrincipalFactor(D); <Rees 0-matrix semigroup 6x4 over Group([ (1,2,3), (1,2) ])> gap> MaximalSubsemigroups(R); [ <Rees 0-matrix semigroup 6x3 over Group([ (1,2,3), (1,2) ])>, <Rees 0-matrix semigroup 6x3 over Group([ (1,2,3), (1,2) ])>, <Rees 0-matrix semigroup 6x3 over Group([ (1,2,3), (1,2) ])>, <Rees 0-matrix semigroup 6x3 over Group([ (1,2,3), (1,2) ])>, <Rees 0-matrix semigroup 5x4 over Group([ (1,2,3), (1,2) ])>, <Rees 0-matrix semigroup 5x4 over Group([ (1,2,3), (1,2) ])>, <Rees 0-matrix semigroup 5x4 over Group([ (1,2,3), (1,2) ])>, <Rees 0-matrix semigroup 5x4 over Group([ (1,2,3), (1,2) ])>, <Rees 0-matrix semigroup 5x4 over Group([ (1,2,3), (1,2) ])>, <Rees 0-matrix semigroup 5x4 over Group([ (1,2,3), (1,2) ])>, <subsemigroup of 6x4 Rees 0-matrix semigroup with 23 generators>, <subsemigroup of 6x4 Rees 0-matrix semigroup with 23 generators>, <subsemigroup of 6x4 Rees 0-matrix semigroup with 21 generators>, <subsemigroup of 6x4 Rees 0-matrix semigroup with 23 generators>, <subsemigroup of 6x4 Rees 0-matrix semigroup with 21 generators>, <subsemigroup of 6x4 Rees 0-matrix semigroup with 21 generators>, <subsemigroup of 6x4 Rees 0-matrix semigroup with 23 generators>, <subsemigroup of 6x4 Rees 0-matrix semigroup with 21 generators>, <subsemigroup of 6x4 Rees 0-matrix semigroup with 21 generators>, <subsemigroup of 6x4 Rees 0-matrix semigroup with 21 generators> ]
‣ MaximalSubsemigroups( R, H ) | ( operation ) |
Returns: The maximal subsemigroups of a Rees (0)-matrix semigroup corresponding to a maximal subgroup of the underlying group.
Suppose that R is a regular Rees (0-)matrix semigroup of the form mathcalM[G; I, J; P] where G is a group and P is a |J| by |I| matrix with entries in G∪{0} . If H is a maximal subgroup of G, then this function returns the maximal subsemigroups of R which are isomorphic to mathcalM[H; I, J; P].
The method used in this function is based on Remark 1 of [GGR68].
Please note: the Grape package version 4.5 or higher must be available and compiled for this function to work, when the argument R is a Rees 0-matrix semigroup.
gap> R := ReesZeroMatrixSemigroup(Group([ (1,2), (3,4) ]), > [ [ (), (1,2) ], [ (), (1,2) ] ]); <Rees 0-matrix semigroup 2x2 over Group([ (1,2), (3,4) ])> gap> G := UnderlyingSemigroup(R); Group([ (1,2), (3,4) ]) gap> H := Group((1,2)); Group([ (1,2) ]) gap> max := MaximalSubsemigroups(R, H); [ <subsemigroup of 2x2 Rees 0-matrix semigroup with 6 generators> ] gap> IsMaximalSubsemigroup(R, max[1]); true
‣ 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 proper subsemigroup T of a semigroup S is a maximal if T is not contained in any other proper subsemigroups of S.
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
‣ 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 (4.5-11), PartialOrderOfDClasses (4.4-7), IsGreensLessThanOrEqual (Reference: IsGreensLessThanOrEqual), and MinimalDClass (4.4-9).
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); <Green's D-class: Transformation( [ 3, 3, 3, 3, 3, 3, 3, 3, 3, 3 ] )> 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>
‣ 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 (4.5-10) and MinimalDClass (4.4-9).
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 ] )>
‣ 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 degree 6 with 4 generators> gap> MultiplicativeZero(S); fail gap> S := DualSymmetricInverseMonoid(6); <inverse bipartition monoid of degree 6 with 3 generators> gap> MultiplicativeZero(S); <block bijection: [ 1, 2, 3, 4, 5, 6, -1, -2, -3, -4, -5, -6 ]>
‣ 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.
‣ 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 (4.5-1).
As neither irredundancy, nor minimal length are proven, these functions usually return an answer much more quickly than IrredundantGeneratingSubset (4.5-6). 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(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(G));; gap> Append(mat, [1..1000]*0); gap> mat := List([1..138], x-> List([1..57], x-> Random(mat)));; gap> R := ReesZeroMatrixSemigroup(G, 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 := RandomBipartitionSemigroup(100,4); <bipartition semigroup of degree 4 with 96 generators> gap> Length(SmallGeneratingSet(S)); 13
‣ 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 ]
‣ 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 ] ]
‣ 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); [ [ 1, 11, 12, 5, 4, 6, 10, 7, 9 ] ]
‣ IsTransitive( S[, X] ) | ( operation ) |
‣ IsTransitive( S[, n] ) | ( operation ) |
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> AsTransformationSemigroup(S); <transformation semigroup of degree 12 with 2 generators> gap> IsTransitive(last); false gap> IsTransitive(AsSemigroup(Group((1,2,3)))); true
‣ 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 ]
‣ 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 ] ]
‣ 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( [ 1, 2, 3, 4, 5, 8, 10 ], [ 3, 1, 4, 2, 5, 6, 7 ] ); [8,6][10,7](1,3,4,2)(5) gap> CyclesOfPartialPerm(x); [ [ 3, 4, 2, 1 ], [ 5 ] ]
‣ 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, 20, 2, 19, 3, 8, 11 ] ]
‣ 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:
If this option has the value true and the genss package is loaded, 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.
If genss is not loaded, then this option is ignored.
The default value for this option is false.
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.
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( [ 1, 2, 3, 4, 5 ], [ 2, 5, 6, 3, 8 ] ), > PartialPerm( [ 1, 2, 4, 7, 8 ], [ 3, 6, 2, 5, 7 ] ) );; gap> Normalizer(S, rec(random:=true, lambdastab:=false)); #I Have 33389 points. #I Have 40136 points in new orbit. Group(())
‣ 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 ] )
‣ GeneratorsSmallest( S ) | ( attribute ) |
Returns: A generating set of transformations.
GeneratorsSmallest returns the lexicographically least collection X of transformations such that S is generated by X and each X[i] is not generated by X[1], X[2], ..., X[i-1].
Note that it can be difficult to find this set of generators, and that it might contain a substantial proportion of the elements of the semigroup.
The comparison of two transformation semigroups via the lexicographic comparison of their sets of elements is the same relation as the lexicographic comparison of their GeneratorsSmallest. However, due to the complexity of determining the GeneratorsSmallest, this is not the method used by the Semigroups package when comparing transformation 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 ] ) ]
‣ UnderlyingSemigroupOfSemigroupWithAdjoinedZero( S ) | ( attribute ) |
Returns: A semigroup, or fail.
If S is a semigroup for which the property IsSemigroupWithAdjoinedZero (4.6-17) is true, (i.e. S has a MultiplicativeZero (4.5-12) 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 (4.6-17) 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
In this section we describe the properties of a semigroup that can be determined using the Semigroups package.
‣ IsBand( S ) | ( property ) |
Returns: true or false.
IsBand returns true if every element of the semigroup S is an idempotent and false if it is not. An inverse semigroup is band if and only if it is a semilattice; see IsSemilattice (4.6-18).
gap> gens := [ Transformation( [ 1, 1, 1, 4, 4, 4, 7, 7, 7, 1 ] ), > Transformation( [ 2, 2, 2, 5, 5, 5, 8, 8, 8, 2 ] ), > Transformation( [ 3, 3, 3, 6, 6, 6, 9, 9, 9, 3 ] ), > Transformation( [ 1, 1, 1, 4, 4, 4, 7, 7, 7, 4 ] ), > Transformation( [ 1, 1, 1, 4, 4, 4, 7, 7, 7, 7 ] ) ];; gap> S := Semigroup(gens);; gap> IsBand(S); true gap> S := InverseSemigroup( > PartialPerm( [ 1, 2, 3, 4, 8, 9 ], [ 5, 8, 7, 6, 9, 1 ] ), > PartialPerm( [ 1, 3, 4, 7, 8, 9, 10 ], [ 2, 3, 8, 7, 10, 6, 1 ] ) );; gap> IsBand(S); false gap> IsBand(IdempotentGeneratedSubsemigroup(S)); true gap> S := PartitionMonoid(4); <regular bipartition monoid of degree 4 with 4 generators> gap> M := MinimalIdeal(S); <simple bipartition semigroup ideal of degree 4 with 1 generator> gap> IsBand(M); true
‣ IsBlockGroup( S ) | ( property ) |
‣ IsSemigroupWithCommutingIdempotents( S ) | ( property ) |
Returns: true or false.
IsBlockGroup and IsSemigroupWithCommutingIdempotents return true if the semigroup S is a block group and false if it is not.
A semigroup S is a block group if every \(\mathscr{L}\)-class and every \(\mathscr{R}\)-class of S contains at most one idempotent. Every semigroup of partial permutations is a block group.
gap> S := Semigroup(Transformation( [ 5, 6, 7, 3, 1, 4, 2, 8 ] ), > Transformation( [ 3, 6, 8, 5, 7, 4, 2, 8 ] ));; gap> IsBlockGroup(S); true gap> S := Semigroup(Transformation( [ 2, 1, 10, 4, 5, 9, 7, 4, 8, 4 ] ), > Transformation( [ 10, 7, 5, 6, 1, 3, 9, 7, 10, 2 ] ));; gap> IsBlockGroup(S); false gap> S := Semigroup( > PartialPerm( [ 1, 2 ], [ 5, 4 ] ), > PartialPerm( [ 1, 2, 3 ], [ 1, 2, 5 ] ), > PartialPerm( [ 1, 2, 3 ], [ 2, 1, 5 ] ), > PartialPerm( [ 1, 3, 4 ], [ 3, 1, 2 ] ), > PartialPerm( [ 1, 3, 4, 5 ], [ 5, 4, 3, 2 ] ) );; gap> T := Range(IsomorphismBlockBijectionSemigroup(S)); <bipartition semigroup of degree 6 with 5 generators> gap> IsBlockGroup(T); true gap> IsBlockGroup(Range(IsomorphismBipartitionSemigroup(S))); true gap> S := Semigroup( > Bipartition( [ [ 1, -2 ], [ 2, -3 ], [ 3, -4 ], [ 4, -1 ] ] ), > Bipartition( [ [ 1, -2 ], [ 2, -1 ], [ 3, -3 ], [ 4, -4 ] ] ), > Bipartition( [ [ 1, 2, -3 ], [ 3, -1, -2 ], [ 4, -4 ] ] ), > Bipartition( [ [ 1, -1 ], [ 2, -2 ], [ 3, -3 ], [ 4, -4 ] ] ) );; gap> IsBlockGroup(S); true
‣ IsCommutativeSemigroup( S ) | ( property ) |
Returns: true or false.
IsCommutativeSemigroup returns true if the semigroup S is commutative and false if it is not. The function IsCommutative (Reference: IsCommutative) can also be used to test if a semigroup is commutative.
A semigroup S is commutative if x*y=y*x for all x,y in S.
gap> gens := [ Transformation( [ 2, 4, 5, 3, 7, 8, 6, 9, 1 ] ), > Transformation( [ 3, 5, 6, 7, 8, 1, 9, 2, 4 ] ) ];; gap> S := Semigroup(gens);; gap> IsCommutativeSemigroup(S); true gap> IsCommutative(S); true gap> S := InverseSemigroup( > PartialPerm( [ 1, 2, 3, 4, 5, 6 ], [ 2, 5, 1, 3, 9, 6 ] ), > PartialPerm( [ 1, 2, 3, 4, 6, 8 ], [ 8, 5, 7, 6, 2, 1 ] ) );; gap> IsCommutativeSemigroup(S); false gap> S := Semigroup( > Bipartition( [ [ 1, 2, 3, 6, 7, -1, -4, -6 ], > [ 4, 5, 8, -2, -3, -5, -7, -8 ] ] ), > Bipartition( [ [ 1, 2, -3, -4 ], [ 3, -5 ], [ 4, -6 ], [ 5, -7 ], > [ 6, -8 ], [ 7, -1 ], [ 8, -2 ] ] ) );; gap> IsCommutativeSemigroup(S); true
‣ IsCompletelyRegularSemigroup( S ) | ( property ) |
Returns: true or false.
IsCompletelyRegularSemigroup returns true if every element of the semigroup S is contained in a subgroup of S.
An inverse semigroup is completely regular if and only if it is a Clifford semigroup; see IsCliffordSemigroup (4.7-1).
gap> gens := [ Transformation( [ 1, 2, 4, 3, 6, 5, 4 ] ), > Transformation( [ 1, 2, 5, 6, 3, 4, 5 ] ), > Transformation( [ 2, 1, 2, 2, 2, 2, 2 ] ) ];; gap> S := Semigroup(gens);; gap> IsCompletelyRegularSemigroup(S); true gap> IsInverseSemigroup(S); true gap> T := Range(IsomorphismPartialPermSemigroup(S));; gap> IsCompletelyRegularSemigroup(T); true gap> IsCliffordSemigroup(T); true gap> S := Semigroup( > Bipartition( [ [ 1, 3, -4 ], [ 2, 4, -1, -2 ], [ -3 ] ] ), > Bipartition( [ [ 1, -1 ], [ 2, 3, 4, -3 ], [ -2, -4 ] ] ) );; gap> IsCompletelyRegularSemigroup(S); false
‣ IsCongruenceFreeSemigroup( S ) | ( property ) |
Returns: true or false.
IsCongruenceFreeSemigroup returns true if the semigroup S is a congruence-free semigroup and false if it is not.
A semigroup S is congruence-free if it has no non-trivial proper congruences.
A semigroup with zero is congruence-free if and only if it is isomorphic to a regular Rees 0-matrix semigroup R whose underlying semigroup is the trivial group, no two rows of the matrix of R are identical, and no two columns are identical; see Theorem 3.7.1 in [How95].
A semigroup without zero is congruence-free if and only if it is a simple group or has order 2; see Theorem 3.7.2 in [How95].
gap> S := Semigroup( Transformation( [ 4, 2, 3, 3, 4 ] ) );; gap> IsCongruenceFreeSemigroup(S); true gap> S := Semigroup( Transformation( [ 2, 2, 4, 4 ] ), > Transformation( [ 5, 3, 4, 4, 6, 6 ] ) );; gap> IsCongruenceFreeSemigroup(S); false
‣ IsGroupAsSemigroup( S ) | ( property ) |
Returns: true or false.
IsGroupAsSemigroup returns true if and only if the semigroup S is mathematically a group.
gap> gens := [ Transformation( [ 2, 4, 5, 3, 7, 8, 6, 9, 1 ] ), > Transformation( [ 3, 5, 6, 7, 8, 1, 9, 2, 4 ] ) ];; gap> S := Semigroup(gens);; gap> IsGroupAsSemigroup(S); true gap> G := SymmetricGroup(5);; gap> S := Range(IsomorphismPartialPermSemigroup(G)); <inverse partial perm semigroup of rank 5 with 2 generators> gap> IsGroupAsSemigroup(S); true gap> S := SymmetricGroup([1,2,10]);; gap> T := Range(IsomorphismBlockBijectionSemigroup( > Range(IsomorphismPartialPermSemigroup(S)))); <inverse bipartition semigroup of degree 11 with 2 generators> gap> IsGroupAsSemigroup(T); true
‣ IsIdempotentGenerated( S ) | ( property ) |
‣ IsSemiBand( S ) | ( property ) |
Returns: true or false.
IsIdempotentGenerated and IsSemiBand return true if the semigroup S is generated by its idempotents and false if it is not. See also Idempotents (4.5-3) and IdempotentGeneratedSubsemigroup (4.5-5).
An inverse semigroup is idempotent-generated if and only if it is a semilattice; see IsSemilattice (4.6-18).
Semiband and idempotent-generated are synonymous in this context.
gap> S := SingularTransformationSemigroup(4); <regular transformation semigroup ideal of degree 4 with 1 generator> gap> IsIdempotentGenerated(S); true gap> S := SingularBrauerMonoid(5); <regular bipartition semigroup ideal of degree 5 with 1 generator> gap> IsIdempotentGenerated(S); true
‣ IsLeftSimple( S ) | ( property ) |
‣ IsRightSimple( S ) | ( property ) |
Returns: true or false.
IsLeftSimple and IsRightSimple returns true if the semigroup S has only one \(\mathscr{L}\)-class or one \(\mathscr{R}\)-class, respectively, and returns false if it has more than one.
An inverse semigroup is left simple if and only if it is right simple if and only if it is a group; see IsGroupAsSemigroup (4.6-6).
gap> S := Semigroup( Transformation( [ 6, 7, 9, 6, 8, 9, 8, 7, 6 ] ), > Transformation( [ 6, 8, 9, 6, 8, 8, 7, 9, 6 ] ), > Transformation( [ 6, 8, 9, 7, 8, 8, 7, 9, 6 ] ), > Transformation( [ 6, 9, 8, 6, 7, 9, 7, 8, 6 ] ), > Transformation( [ 6, 9, 9, 6, 8, 8, 7, 9, 6 ] ), > Transformation( [ 6, 9, 9, 7, 8, 8, 6, 9, 7 ] ), > Transformation( [ 7, 8, 8, 7, 9, 9, 7, 8, 6 ] ), > Transformation( [ 7, 9, 9, 7, 6, 9, 6, 8, 7 ] ), > Transformation( [ 8, 7, 6, 9, 8, 6, 8, 7, 9 ] ), > Transformation( [ 9, 6, 6, 7, 8, 8, 7, 6, 9 ] ), > Transformation( [ 9, 6, 6, 7, 9, 6, 9, 8, 7 ] ), > Transformation( [ 9, 6, 7, 9, 6, 6, 9, 7, 8 ] ), > Transformation( [ 9, 6, 8, 7, 9, 6, 9, 8, 7 ] ), > Transformation( [ 9, 7, 6, 8, 7, 7, 9, 6, 8 ] ), > Transformation( [ 9, 7, 7, 8, 9, 6, 9, 7, 8 ] ), > Transformation( [ 9, 8, 8, 9, 6, 7, 6, 8, 9 ] ) );; gap> IsRightSimple(S); false gap> IsLeftSimple(S); true gap> IsGroupAsSemigroup(S); false gap> NrRClasses(S); 16 gap> S := BrauerMonoid(6);; gap> S := Semigroup(RClass(S, Random(MinimalDClass(S))));; gap> IsLeftSimple(S); false gap> IsRightSimple(S); true
‣ IsLeftZeroSemigroup( S ) | ( property ) |
Returns: true or false.
IsLeftZeroSemigroup returns true if the semigroup S is a left zero semigroup and false if it is not.
A semigroup is a left zero semigroup if x*y=x for all x,y. An inverse semigroup is a left zero semigroup if and only if it is trivial.
gap> gens := [ Transformation( [ 2, 1, 4, 3, 5 ] ), > Transformation( [ 3, 2, 3, 1, 1 ] ) ];; gap> S := Semigroup(gens);; gap> IsRightZeroSemigroup(S); false gap> gens := [Transformation( [ 1, 2, 3, 3, 1 ] ), > Transformation( [ 1, 2, 3, 3, 3 ] ) ];; gap> S := Semigroup(gens);; gap> IsLeftZeroSemigroup(S); true
‣ IsMonogenicSemigroup( S ) | ( property ) |
Returns: true or false.
IsMonogenicSemigroup returns true if the semigroup S is monogenic and it returns false if it is not.
A semigroup is monogenic if it is generated by a single element. See also IsMonogenicInverseSemigroup (4.7-7) and IndexPeriodOfTransformation (Reference: IndexPeriodOfTransformation).
gap> S := Semigroup( > Transformation([ 2, 2, 2, 11, 10, 8, 10, 11, 2, 11, 10, 2, 11, 11, 10 ]), > Transformation([ 2, 2, 2, 8, 11, 15, 11, 10, 2, 10, 11, 2, 10, 4, 7 ]), > Transformation([ 2, 2, 2, 11, 10, 8, 10, 11, 2, 11, 10, 2, 11, 11, 10 ]), > Transformation([ 2, 2, 12, 7, 8, 14, 8, 11, 2, 11, 10, 2, 11, 15, 4 ]));; gap> IsMonogenicSemigroup(S); true gap> S := Semigroup( > Bipartition( [ [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, -2, -5, -7, -9 ], > [ -1, -10 ], [ -3, -4, -6, -8 ] ] ), > Bipartition( [ [ 1, 4, 7, 8, -2 ], [ 2, 3, 5, 10, -5 ], > [ 6, 9, -7, -9 ], [ -1, -10 ], [ -3, -4, -6, -8 ] ] ) );; gap> IsMonogenicSemigroup(S); true
‣ IsMonoidAsSemigroup( S ) | ( property ) |
Returns: true or false.
IsMonoidAsSemigroup returns true if and only if the semigroup S is mathematically a monoid, i.e. if and only if it contains a MultiplicativeNeutralElement (Reference: MultiplicativeNeutralElement).
It is possible that a semigroup which satisfies IsMonoidAsSemigroup is not in the GAP category IsMonoid (Reference: IsMonoid). This is possible if the MultiplicativeNeutralElement (Reference: MultiplicativeNeutralElement) of S is not equal to the One (Reference: One) of any element in S. Therefore a semigroup satisfying IsMonoidAsSemigroup may not possess the attributes of a monoid (such as, GeneratorsOfMonoid (Reference: GeneratorsOfMonoid)).
See also One (Reference: One), IsInverseMonoid (Reference: IsInverseMonoid) and IsomorphismTransformationMonoid (Reference: IsomorphismTransformationMonoid).
gap> S := Semigroup( Transformation( [ 1, 4, 6, 2, 5, 3, 7, 8, 9, 9 ] ), > Transformation( [ 6, 3, 2, 7, 5, 1, 8, 8, 9, 9 ] ) );; gap> IsMonoidAsSemigroup(S); true gap> IsMonoid(S); false gap> MultiplicativeNeutralElement(S); Transformation( [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 9 ] ) gap> T := Range(IsomorphismBipartitionSemigroup(S));; gap> IsMonoidAsSemigroup(T); true gap> IsMonoid(T); false gap> One(T); fail gap> S := Monoid(Transformation( [ 8, 2, 8, 9, 10, 6, 2, 8, 7, 8 ] ), > Transformation( [ 9, 2, 6, 3, 6, 4, 5, 5, 3, 2 ] ));; gap> IsMonoidAsSemigroup(S); true
‣ IsOrthodoxSemigroup( S ) | ( property ) |
Returns: true or false.
IsOrthodoxSemigroup returns true if the semigroup S is orthodox and false if it is not.
A semigroup is orthodox if it is regular and its idempotent elements form a subsemigroup. Every inverse semigroup is also an orthodox semigroup.
See also IsRegularSemigroup (4.6-14) and IsRegularSemigroup (Reference: IsRegularSemigroup).
gap> gens := [ Transformation( [ 1, 1, 1, 4, 5, 4 ] ), > Transformation( [ 1, 2, 3, 1, 1, 2 ] ), > Transformation( [ 1, 2, 3, 1, 1, 3 ] ), > Transformation( [ 5, 5, 5, 5, 5, 5 ] ) ];; gap> S := Semigroup(gens);; gap> IsOrthodoxSemigroup(S); true gap> S := Semigroup(GeneratorsOfSemigroup(DualSymmetricInverseMonoid(5)));; gap> IsOrthodoxSemigroup(S); true
‣ IsRectangularBand( S ) | ( property ) |
Returns: true or false.
IsRectangularBand returns true if the semigroup S is a rectangular band and false if it is not.
A semigroup S is a rectangular band if for all x, y, z in S we have that x^2 = x and xyz = xz.
Equivalently, S is a rectangular band if S is isomorphic to a semigroup of the form I × Λ with multiplication (i,λ)(j,μ) = (i,μ). In this case, S is called an |I| × |Λ| rectangular band.
An inverse semigroup is a rectangular band if and only if it is a group.
gap> gens := [ Transformation( [ 1, 1, 1, 4, 4, 4, 7, 7, 7, 1 ] ), > Transformation( [ 2, 2, 2, 5, 5, 5, 8, 8, 8, 2 ] ), > Transformation( [ 3, 3, 3, 6, 6, 6, 9, 9, 9, 3 ] ), > Transformation( [ 1, 1, 1, 4, 4, 4, 7, 7, 7, 4 ] ), > Transformation( [ 1, 1, 1, 4, 4, 4, 7, 7, 7, 7 ] ) ];; gap> S := Semigroup(gens);; gap> IsRectangularBand(S); true gap> IsRectangularBand(MinimalIdeal(PartitionMonoid(4))); true
‣ IsRegularSemigroup( S ) | ( property ) |
Returns: true or false.
IsRegularSemigroup returns true if the semigroup S is regular and false if it is not.
A semigroup S is regular if for all x in S there exists y in S such that x*y*x=x. Every inverse semigroup is regular, and a semigroup of partial permutations is regular if and only if it is an inverse semigroup.
See also IsRegularDClass (Reference: IsRegularDClass), IsRegularClass (4.4-4), and IsRegularSemigroupElement (Reference: IsRegularSemigroupElement).
gap> IsRegularSemigroup(FullTransformationSemigroup(5)); true gap> IsRegularSemigroup(JonesMonoid(5)); true
‣ IsRightZeroSemigroup( S ) | ( property ) |
Returns: true or false.
IsRightZeroSemigroup returns true if the S is a right zero semigroup and false if it is not.
A semigroup S is a right zero semigroup if x*y=y for all x,y in S. An inverse semigroup is a right zero semigroup if and only if it is trivial.
gap> gens := [ Transformation( [ 2, 1, 4, 3, 5 ] ), > Transformation( [ 3, 2, 3, 1, 1 ] ) ];; gap> S := Semigroup(gens);; gap> IsRightZeroSemigroup(S); false gap> gens := [Transformation( [ 1, 2, 3, 3, 1 ] ), > Transformation( [ 1, 2, 4, 4, 1 ] )];; gap> S := Semigroup(gens);; gap> IsRightZeroSemigroup(S); true
‣ IsRTrivial( S ) | ( property ) |
‣ IsLTrivial( S ) | ( property ) |
‣ IsHTrivial( S ) | ( property ) |
‣ IsDTrivial( S ) | ( property ) |
‣ IsAperiodicSemigroup( S ) | ( property ) |
‣ IsCombinatorialSemigroup( S ) | ( property ) |
Returns: true or false.
IsXTrivial returns true if Green's \(\mathscr{R}\)-relation, \(\mathscr{L}\)-relation, \(\mathscr{H}\)-relation, \(\mathscr{D}\)-relation, respectively, on the semigroup S is trivial and false if it is not. These properties can also be applied to a Green's class instead of a semigroup where applicable.
For inverse semigroups, the properties of being \(\mathscr{R}\)-trivial, \(\mathscr{L}\)-trivial, \(\mathscr{D}\)-trivial, and a semilattice are equivalent; see IsSemilattice (4.6-18).
A semigroup is aperiodic if its contains no non-trivial subgroups (equivalently, all of its group \(\mathscr{H}\)-classes are trivial). A finite semigroup is aperiodic if and only if it is \(\mathscr{H}\)-trivial.
Combinatorial is a synonym for aperiodic in this context.
gap> S := Semigroup( Transformation( [ 1, 5, 1, 3, 7, 10, 6, 2, 7, 10 ] ), > Transformation( [ 4, 4, 5, 6, 7, 7, 7, 4, 3, 10 ] ) );; gap> IsHTrivial(S); true gap> Size(S); 108 gap> IsRTrivial(S); false gap> IsLTrivial(S); false
‣ IsSemigroupWithAdjoinedZero( S ) | ( property ) |
Returns: true or false.
IsSemigroupWithAdjoinedZero returns true if the semigroup S can be expressed as the disjoint union of subsemigroups S ∖ { 0 } and { 0 } (where 0 is the MultiplicativeZero (4.5-12) of S).
If this is not the case, then either S lacks a multiplicative zero, or the set S ∖ { 0 } is not a subsemigroup of S, and so IsSemigroupWithAdjoinedZero returns false.
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> IsZeroGroup(S); true gap> IsSemigroupWithAdjoinedZero(S); true gap> S := FullTransformationMonoid(4);; gap> IsSemigroupWithAdjoinedZero(S); false
‣ IsSemilattice( S ) | ( property ) |
Returns: true or false.
IsSemilattice returns true if the semigroup S is a semilattice and false if it is not.
A semigroup is a semilattice if it is commutative and every element is an idempotent. The idempotents of an inverse semigroup form a semilattice.
gap> S := Semigroup(Transformation( [ 2, 5, 1, 7, 3, 7, 7 ] ), > Transformation( [ 3, 6, 5, 7, 2, 1, 7 ] ) );; gap> Size(S); 631 gap> IsInverseSemigroup(S); true gap> A := Semigroup(Idempotents(S)); <transformation semigroup of degree 7 with 32 generators> gap> IsSemilattice(A); true gap> S := FactorisableDualSymmetricInverseSemigroup(5);; gap> S := IdempotentGeneratedSubsemigroup(S);; gap> IsSemilattice(S); true
‣ IsSimpleSemigroup( S ) | ( property ) |
‣ IsCompletelySimpleSemigroup( S ) | ( property ) |
Returns: true or false.
IsSimpleSemigroup returns true if the semigroup S is simple and false if it is not.
A semigroup is simple if it has no proper 2-sided ideals. A semigroup is completely simple if it is simple and possesses minimal left and right ideals. A finite semigroup is simple if and only if it is completely simple. An inverse semigroup is simple if and only if it is a group.
gap> S := Semigroup( > Transformation( [ 2, 2, 4, 4, 6, 6, 8, 8, 10, 10, 12, 12, 2 ] ), > Transformation( [ 1, 1, 3, 3, 5, 5, 7, 7, 9, 9, 11, 11, 3 ] ), > Transformation( [ 1, 7, 3, 9, 5, 11, 7, 1, 9, 3, 11, 5, 5 ] ), > Transformation( [ 7, 7, 9, 9, 11, 11, 1, 1, 3, 3, 5, 5, 7 ] ) );; gap> IsSimpleSemigroup(S); true gap> IsCompletelySimpleSemigroup(S); true gap> IsSimpleSemigroup(MinimalIdeal(BrauerMonoid(6))); true gap> R := Range(IsomorphismReesMatrixSemigroup( > MinimalIdeal(BrauerMonoid(6)))); <Rees matrix semigroup 15x15 over Group(())>
‣ IsSynchronizingSemigroup( S[, n] ) | ( operation ) |
‣ IsSynchronizingTransformationCollection( coll[, n] ) | ( operation ) |
Returns: true or false.
For a positive integer n, IsSynchronizingSemigroup returns true if the semigroup of transformations S contains a transformation with constant value on [1..n]. Note that this function will return true whenever n = 1. See also ConstantTransformation (Reference: ConstantTransformation).
If the optional second argument is not specified, then n will be taken to be the value of DegreeOfTransformationSemigroup (Reference: DegreeOfTransformationSemigroup) for S.
The operation IsSynchronizingTransformationCollection behaves in the same way as IsSynchronizingSemigroup but can be applied to any collection of transformations and not only semigroups.
Note that the semigroup consisting of the identity transformation has degree 0, and for this special case the function IsSynchronizingSemigroup will return false.
gap> S:=Semigroup( Transformation( [ 1, 1, 8, 7, 6, 6, 4, 1, 8, 9 ] ), > Transformation( [ 5, 8, 7, 6, 10, 8, 7, 6, 9, 7 ] ) );; gap> IsSynchronizingSemigroup(S, 10); true gap> S:=Semigroup( Transformation( [ 3, 8, 1, 1, 9, 9, 8, 7, 9, 6 ] ), > Transformation( [ 7, 6, 8, 7, 5, 6, 8, 7, 8, 9 ] ) );; gap> IsSynchronizingSemigroup(S, 10); false gap> Representative(MinimalIdeal(S)); Transformation( [ 7, 8, 8, 7, 8, 8, 8, 7, 8, 8 ] )
‣ IsZeroGroup( S ) | ( property ) |
Returns: true or false.
IsZeroGroup returns true if the semigroup S is a zero group and false if it is not.
A semigroup S is a zero group if there exists an element z in S such that S without z is a group and x*z=z*x=z for all x in S. Every zero group is an inverse semigroup.
gap> S := Semigroup(Transformation( [ 2, 2, 3, 4, 6, 8, 5, 5, 9 ] ), > Transformation( [ 3, 3, 8, 2, 5, 6, 4, 4, 9 ] ), > ConstantTransformation(9, 9));; gap> IsZeroGroup(S); true gap> T := Range(IsomorphismPartialPermSemigroup(S));; gap> IsZeroGroup(T); true gap> IsZeroGroup(JonesMonoid(2)); true
‣ IsZeroRectangularBand( S ) | ( property ) |
Returns: true or false.
IsZeroRectangularBand returns true if the semigroup S is a zero rectangular band and false if it is not.
A semigroup is a 0-rectangular band if it is 0-simple and \(\mathscr{H}\)-trivial; see also IsZeroSimpleSemigroup (4.6-24) and IsHTrivial (4.6-16). An inverse semigroup is a 0-rectangular band if and only if it is a 0-group; see IsZeroGroup (4.6-21).
gap> S := Semigroup( > Transformation( [ 1, 3, 7, 9, 1, 12, 13, 1, 15, 9, 1, 18, 1, 1, 13, > 1, 1, 21, 1, 1, 1, 1, 1, 25, 26, 1 ] ), > Transformation( [ 1, 5, 1, 5, 11, 1, 1, 14, 1, 16, 17, 1, 1, 19, 1, > 11, 1, 1, 1, 23, 1, 16, 19, 1, 1, 1 ] ), > Transformation( [ 1, 4, 8, 1, 10, 1, 8, 1, 1, 1, 10, 1, 8, 10, 1, 1, > 20, 1, 22, 1, 8, 1, 1, 1, 1, 1 ] ), > Transformation( [ 1, 6, 6, 1, 1, 1, 6, 1, 1, 1, 1, 1, 6, 1, 6, 1, 1, > 6, 1, 1, 24, 1, 1, 1, 1, 6 ] ) );; gap> IsZeroRectangularBand(Semigroup(Elements(GreensDClasses(S)[7]))); true gap> IsZeroRectangularBand(Semigroup(Elements(GreensDClasses(S)[1]))); false
‣ IsZeroSemigroup( S ) | ( property ) |
Returns: true or false.
IsZeroSemigroup returns true if the semigroup S is a zero semigroup and false if it is not.
A semigroup S is a zero semigroup if there exists an element z in S such that x*y=z for all x,y in S. An inverse semigroup is a zero semigroup if and only if it is trivial.
gap> S := Semigroup( Transformation( [ 4, 7, 6, 3, 1, 5, 3, 6, 5, 9 ] ), > Transformation( [ 5, 3, 5, 1, 9, 3, 8, 7, 4, 3 ] ) );; gap> IsZeroSemigroup(S); false gap> S := Semigroup( Transformation( [ 7, 8, 8, 8, 5, 8, 8, 8 ] ), > Transformation( [ 8, 8, 8, 8, 5, 7, 8, 8 ] ), > Transformation( [ 8, 7, 8, 8, 5, 8, 8, 8 ] ), > Transformation( [ 8, 8, 8, 7, 5, 8, 8, 8 ] ), > Transformation( [ 8, 8, 7, 8, 5, 8, 8, 8 ] ) );; gap> IsZeroSemigroup(S); true gap> MultiplicativeZero(S); Transformation( [ 8, 8, 8, 8, 5, 8, 8, 8 ] )
‣ IsZeroSimpleSemigroup( S ) | ( property ) |
Returns: true or false.
IsZeroSimpleSemigroup returns true if the semigroup S is 0-simple and false if it is not.
A semigroup is a 0-simple if it has no two-sided ideals other than itself and the set containing the zero element; see also MultiplicativeZero (4.5-12). An inverse semigroup is 0-simple if and only if it is a Brandt semigroup; see IsBrandtSemigroup (4.7-2).
gap> S := Semigroup( > Transformation( [ 1, 17, 17, 17, 17, 17, 17, 17, 17, 17, 5, 17, > 17, 17, 17, 17, 17 ] ), > Transformation( [ 1, 17, 17, 17, 11, 17, 17, 17, 17, 17, 17, 17, > 17, 17, 17, 17, 17 ] ), > Transformation( [ 1, 17, 17, 17, 17, 17, 17, 17, 17, 17, 4, 17, > 17, 17, 17, 17, 17 ] ), > Transformation( [ 1, 17, 17, 5, 17, 17, 17, 17, 17, 17, 17, 17, > 17, 17, 17, 17, 17 ] ));; gap> IsZeroSimpleSemigroup(S); true gap> S := Semigroup( > Transformation( [ 2, 3, 4, 5, 1, 8, 7, 6, 2, 7 ] ), > Transformation([ 2, 3, 4, 5, 6, 8, 7, 1, 2, 2 ] ));; gap> IsZeroSimpleSemigroup(S); false
In this section we describe properties and attributes specific to inverse semigroups that can be determined using Semigroups.
The functions
IsJoinIrreducible (4.7-5)
IsMajorantlyClosed (4.7-6)
JoinIrreducibleDClasses (4.7-8)
MajorantClosure (4.7-9)
Minorants (4.7-10)
RightCosetsOfInverseSemigroup (4.7-12)
SmallerDegreePartialPermRepresentation (4.7-14)
VagnerPrestonRepresentation (4.7-15)
were written by Wilf Wilson and Robert Hancock.
The function CharacterTableOfInverseSemigroup (4.7-16) was written by Jhevon Smith and Ben Steinberg.
‣ IsCliffordSemigroup( S ) | ( property ) |
Returns: true or false.
IsCliffordSemigroup returns true if the semigroup S is regular and its idempotents are central, and false if it is not.
gap> S := Semigroup( Transformation( [ 1, 2, 4, 5, 6, 3, 7, 8 ] ), > Transformation( [ 3, 3, 4, 5, 6, 2, 7, 8 ] ), > Transformation( [ 1, 2, 5, 3, 6, 8, 4, 4 ] ) );; gap> IsCliffordSemigroup(S); true gap> T := Range(IsomorphismPartialPermSemigroup(S));; gap> IsCliffordSemigroup(S); true gap> S := DualSymmetricInverseMonoid(5);; gap> T := IdempotentGeneratedSubsemigroup(S);; gap> IsCliffordSemigroup(T); true
‣ IsBrandtSemigroup( S ) | ( property ) |
Returns: true or false.
IsBrandtSemigroup return true if the semigroup S is a 0-simple inverse semigroup, and false if it is not. See also IsZeroSimpleSemigroup (4.6-24) and IsInverseSemigroup (Reference: IsInverseSemigroup).
gap> S := Semigroup(Transformation( [ 2, 8, 8, 8, 8, 8, 8, 8 ] ), > Transformation( [ 5, 8, 8, 8, 8, 8, 8, 8 ] ), > Transformation( [ 8, 3, 8, 8, 8, 8, 8, 8 ] ), > Transformation( [ 8, 6, 8, 8, 8, 8, 8, 8 ] ), > Transformation( [ 8, 8, 1, 8, 8, 8, 8, 8 ] ), > Transformation( [ 8, 8, 8, 1, 8, 8, 8, 8 ] ), > Transformation( [ 8, 8, 8, 8, 4, 8, 8, 8 ] ), > Transformation( [ 8, 8, 8, 8, 8, 7, 8, 8 ] ), > Transformation( [ 8, 8, 8, 8, 8, 8, 2, 8 ] ));; gap> IsBrandtSemigroup(S); true gap> T := Range(IsomorphismPartialPermSemigroup(S));; gap> IsBrandtSemigroup(T); true gap> S := DualSymmetricInverseMonoid(4);; gap> D := DClasses(S)[3]; <Green's D-class: <block bijection: [ 1, 2, 3, -1, -2, -3 ], [ 4, -4 ]>> gap> R := InjectionPrincipalFactor(D);; gap> S := Semigroup(PreImages(R, GeneratorsOfSemigroup(Range(R))));; gap> IsBrandtSemigroup(S); true
‣ IsEUnitaryInverseSemigroup( S ) | ( property ) |
Returns: true or false.
As described in Section 5.9 of [How95], an inverse semigroup S with semilattice of idempotents E is E-unitary if for
s \in S\textrm{ and }e \in E\textrm{: }es \in E \Rightarrow s \in E.
Equivalently, S is E-unitary if E is closed in the natural partial order (see Proposition 5.9.1 in [How95]):
\textrm{for } s \in S\textrm{ and }e \in E\textrm{: }e \le s \Rightarrow s \in E.
This condition is equivalent to E being majorantly closed in S. See IdempotentGeneratedSubsemigroup (4.5-5) and IsMajorantlyClosed (4.7-6). Hence an inverse semigroup of partial permutations, block bijections or partial permutation bipartitions is E-unitary if and only if the idempotent semilattice is majorantly closed.
gap> S := InverseSemigroup( [ PartialPerm( [ 1, 2, 3, 4 ], [ 2, 3, 1, 6 ] ), > PartialPerm( [ 1, 2, 3, 5 ], [ 3, 2, 1, 6 ] ) ]);; gap> IsEUnitaryInverseSemigroup(S); true gap> e := IdempotentGeneratedSubsemigroup(S);; gap> ForAll(Difference(S,e), x->not ForAny(e, y->y*x in e)); true gap> T := InverseSemigroup( [ > PartialPerm( [ 1, 3, 4, 6, 8 ], [ 2, 5, 10, 7, 9 ] ), > PartialPerm( [ 1, 2, 3, 5, 6, 7, 8 ], [ 5, 8, 9, 2, 10, 1, 3 ] ), > PartialPerm( [ 1, 2, 3, 5, 6, 7, 9 ], [ 9, 8, 4, 1, 6, 7, 2 ] ) ]);; gap> IsEUnitaryInverseSemigroup(T); false gap> U := InverseSemigroup( [ > PartialPerm( [ 1, 2, 3, 4, 5 ], [ 2, 3, 4, 5, 1 ] ), > PartialPerm( [ 1, 2, 3, 4, 5 ], [ 2, 1, 3, 4, 5 ] ) ]);; gap> IsEUnitaryInverseSemigroup(U); true gap> IsGroupAsSemigroup(U); true gap> StructureDescription(U); "S5"
‣ IsFactorisableSemigroup( S ) | ( property ) |
Returns: true or false.
An inverse monoid is factorisable if every element is the product of an element of the group of units and an idempotent; see also GroupOfUnits (4.5-2) and Idempotents (4.5-3). Hence an inverse semigroup of partial permutations is factorisable if and only if each of its generators is the restriction of some element in the group of units.
gap> S := InverseSemigroup( PartialPerm( [ 1, 2, 4 ], [ 3, 1, 4 ] ), > PartialPerm( [ 1, 2, 3, 5 ], [ 4, 1, 5, 2 ] ) );; gap> IsFactorisableSemigroup(S); false gap> IsFactorisableSemigroup(SymmetricInverseSemigroup(5)); true gap> IsFactorisableSemigroup(DualSymmetricInverseMonoid(5)); false gap> IsFactorisableSemigroup(FactorisableDualSymmetricInverseSemigroup(5)); true
‣ IsJoinIrreducible( S, x ) | ( operation ) |
Returns: true or false.
IsJoinIrreducible determines whether an element x of an inverse semigroup S of partial permutations, block bijections or partial permutation bipartitions is join irreducible.
An element x is join irreducible when it is not the least upper bound (with respect to the natural partial order NaturalLeqPartialPerm (Reference: NaturalLeqPartialPerm)) of any subset of S not containing x.
gap> S := SymmetricInverseSemigroup(3); <symmetric inverse monoid of degree 3> gap> x := PartialPerm([1,2,3]); <identity partial perm on [ 1, 2, 3 ]> gap> IsJoinIrreducible(S, x); false gap> T := InverseSemigroup(PartialPerm([1,2,4,3]), PartialPerm([1]), > PartialPerm([0,2])); <inverse partial perm semigroup of rank 4 with 3 generators> gap> y := PartialPerm([1,2,3,4]); <identity partial perm on [ 1, 2, 3, 4 ]> gap> IsJoinIrreducible(T, y); true gap> B := InverseSemigroup([ > Bipartition( [ [ 1, -5 ], [ 2, -2 ], > [ 3, 5, 6, 7, -1, -4, -6, -7 ], [ 4, -3 ] ] ), > Bipartition( [ [ 1, -1 ], [ 2, -3 ], [ 3, -4 ], > [ 4, 5, 7, -2, -6, -7 ], [ 6, -5 ] ] ), > Bipartition( [ [ 1, -2 ], [ 2, -4 ], [ 3, -6 ], > [ 4, -1 ], [ 5, 7, -3, -7 ], [ 6, -5 ] ] ), > Bipartition( [ [ 1, -5 ], [ 2, -1 ], [ 3, -6 ], > [ 4, 5, 7, -2, -4, -7 ], [ 6, -3 ] ] )]); <inverse bipartition semigroup of degree 7 with 4 generators> gap> x := Bipartition( [ [ 1, 2, 3, 5, 6, 7, -2, -3, -4, -5, -6, -7 ], > [ 4, -1 ] ] ); <block bijection: [ 1, 2, 3, 5, 6, 7, -2, -3, -4, -5, -6, -7 ], [ 4, -1 ]> gap> IsJoinIrreducible(B, x); true gap> IsJoinIrreducible(B, B.1); false
‣ IsMajorantlyClosed( S, T ) | ( operation ) |
Returns: true or false.
IsMajorantlyClosed determines whether the subset T of the inverse semigroup of partial permutations, block bijections or partial permutation bipartitions S is majorantly closed in S. See also MajorantClosure (4.7-9).
We say that T is majorantly closed in S if it contains all elements of S which are greater than or equal to any element of T, with respect to the natural partial order. See NaturalLeqPartialPerm (Reference: NaturalLeqPartialPerm).
Note that T can be a subset of S or a subsemigroup of S.
gap> S := SymmetricInverseSemigroup(2); <symmetric inverse monoid of degree 2> gap> T := [Elements(S)[2]]; [ <identity partial perm on [ 1 ]> ] gap> IsMajorantlyClosed(S,T); false gap> U := [Elements(S)[2],Elements(S)[6]]; [ <identity partial perm on [ 1 ]>, <identity partial perm on [ 1, 2 ] > ] gap> IsMajorantlyClosed(S,U); true gap> D := DualSymmetricInverseSemigroup(3); <inverse bipartition monoid of degree 3 with 3 generators> gap> x := Bipartition( [ [ 1, -2 ], [ 2, -3 ], [ 3, -1 ] ] );; gap> IsMajorantlyClosed(D, [x]); true gap> y := Bipartition( [ [ 1, 2, -1, -2 ], [ 3, -3 ] ] );; gap> IsMajorantlyClosed(D, [x,y]); false
‣ IsMonogenicInverseSemigroup( S ) | ( property ) |
Returns: true or false.
IsMonogenicInverseSemigroup returns true if the semigroup S is an inverse monogenic semigroup and it returns false if it is not.
A inverse semigroup is monogenic if it is generated as an inverse semigroup by a single element. See also IsMonogenicSemigroup (4.6-10) and IndexPeriodOfTransformation (Reference: IndexPeriodOfTransformation).
gap> f := PartialPerm( [ 1, 2, 3, 6, 8, 10 ], [ 2, 6, 7, 9, 1, 5 ] );; gap> S := InverseSemigroup(f, f^2, f^3);; gap> IsMonogenicSemigroup(S); false gap> IsMonogenicInverseSemigroup(S); true gap> x := Random(DualSymmetricInverseMonoid(100));; gap> S := InverseSemigroup(x, x^2, x^20);; gap> IsMonogenicInverseSemigroup(S); true
‣ JoinIrreducibleDClasses( S ) | ( attribute ) |
Returns: A list of \(\mathscr{D}\)-classes.
JoinIrreducibleDClasses returns a list of the join irreducible \(\mathscr{D}\)-classes of the inverse semigroup of partial permutations, block bijections or partial permutation bipartitions S.
A join irreducible \(\mathscr{D}\)-class is a \(\mathscr{D}\)-class containing only join irreducible elements. See IsJoinIrreducible (4.7-5). If a \(\mathscr{D}\)-class contains one join irreducible element, then all of the elements in the \(\mathscr{D}\)-class are join irreducible.
gap> S := SymmetricInverseSemigroup(3); <symmetric inverse monoid of degree 3> gap> JoinIrreducibleDClasses(S); [ <Green's D-class: <identity partial perm on [ 1 ]>> ] gap> T := InverseSemigroup( > PartialPerm( [ 1, 2, 3, 4 ], [ 1, 2, 4, 3 ] ), > PartialPerm( [ 1 ], [ 1 ] ), PartialPerm( [ 2 ], [ 2 ] ) ); <inverse partial perm semigroup of rank 4 with 3 generators> gap> JoinIrreducibleDClasses(T); [ <Green's D-class: <identity partial perm on [ 1, 2, 3, 4 ]>>, <Green's D-class: <identity partial perm on [ 1 ]>>, <Green's D-class: <identity partial perm on [ 2 ]>> ] gap> D := DualSymmetricInverseSemigroup(3); <inverse bipartition monoid of degree 3 with 3 generators> gap> JoinIrreducibleDClasses(D); [ <Green's D-class: <block bijection: [ 1, 2, -1, -2 ], [ 3, -3 ]>> ]
‣ MajorantClosure( S, T ) | ( operation ) |
Returns: A majorantly closed list of elements.
MajorantClosure returns a majorantly closed subset of an inverse semigroup of partial permutations, block bijections or partial permutation bipartitions, S, as a list. See IsMajorantlyClosed (4.7-6).
The result contains all elements of S which are greater than or equal to any element of T (with respect to the natural partial order NaturalLeqPartialPerm (Reference: NaturalLeqPartialPerm)). In particular, the result is a superset of T.
Note that T can be a subset of S or a subsemigroup of S.
gap> S := SymmetricInverseSemigroup(4); <symmetric inverse monoid of degree 4> gap> T := [PartialPerm([1,0,3,0])]; [ <identity partial perm on [ 1, 3 ]> ] gap> U := MajorantClosure(S,T); [ <identity partial perm on [ 1, 3 ]>, <identity partial perm on [ 1, 2, 3 ]>, [2,4](1)(3), [4,2](1)(3), <identity partial perm on [ 1, 3, 4 ]>, <identity partial perm on [ 1, 2, 3, 4 ]>, (1)(2,4)(3) ] gap> B := InverseSemigroup([ > Bipartition( [ [ 1, -2 ], [ 2, -1 ], [ 3, -3 ], [ 4, 5, -4, -5 ] ] ), > Bipartition( [ [ 1, -3 ], [ 2, -4 ], [ 3, -2 ], > [ 4, -1 ], [ 5, -5 ] ] ) ]);; gap> T := [ > Bipartition( [ [ 1, -2 ], [ 2, 3, 5, -1, -3, -5 ], [ 4, -4 ] ] ), > Bipartition( [ [ 1, -4 ], [ 2, 3, 5, -1, -3, -5 ], [ 4, -2 ] ] ) ];; gap> IsMajorantlyClosed(B,T); false gap> MajorantClosure(B,T); [ <block bijection: [ 1, -2 ], [ 2, 3, 5, -1, -3, -5 ], [ 4, -4 ]>, <block bijection: [ 1, -4 ], [ 2, 3, 5, -1, -3, -5 ], [ 4, -2 ]>, <block bijection: [ 1, -2 ], [ 2, 5, -1, -5 ], [ 3, -3 ], [ 4, -4 ]> , <block bijection: [ 1, -2 ], [ 2, -1 ], [ 3, 5, -3, -5 ], [ 4, -4 ]>, <block bijection: [ 1, -4 ], [ 2, 5, -3, -5 ], [ 3, -1 ], [ 4, -2 ]> , <block bijection: [ 1, -4 ], [ 2, -3 ], [ 3, 5, -1, -5 ], [ 4, -2 ]>, <block bijection: [ 1, -4 ], [ 2, -3 ], [ 3, -1 ], [ 4, -2 ], [ 5, -5 ]> ] gap> IsMajorantlyClosed(B, last); true
‣ Minorants( S, f ) | ( operation ) |
Returns: A list of elements.
Minorants takes an element f from an inverse semigroup of partial permutations, block bijections or partial permutation bipartitions S, and returns a list of the minorants of f in S.
A minorant of f is an element of S which is strictly less than f in the natural partial order of S. See NaturalLeqPartialPerm (Reference: NaturalLeqPartialPerm).
gap> s := SymmetricInverseSemigroup(3); <symmetric inverse monoid of degree 3> gap> f := Elements(s)[13]; [1,3](2) gap> Minorants(s,f); [ <empty partial perm>, [1,3], <identity partial perm on [ 2 ]> ] gap> f := PartialPerm([3,2,4,0]); [1,3,4](2) gap> S := InverseSemigroup(f); <inverse partial perm semigroup of rank 4 with 1 generator> gap> Minorants(S,f); [ <identity partial perm on [ 2 ]>, [1,3](2), [3,4](2) ]
‣ PrimitiveIdempotents( S ) | ( attribute ) |
Returns: A list of idempotent partial permutations.
An idempotent in an inverse semigroup S is primitive if it is non-zero and minimal with respect to the NaturalPartialOrder (Reference: NaturalPartialOrder) on S. PrimitiveIdempotents returns the list of primitive idempotents in the inverse semigroup of partial permutations S.
gap> S:= InverseMonoid( > PartialPerm( [ 1 ], [ 4 ] ), > PartialPerm( [ 1, 2, 3 ], [ 2, 1, 3 ] ), > PartialPerm( [ 1, 2, 3 ], [ 3, 1, 2 ] ) );; gap> MultiplicativeZero(S); <empty partial perm> gap> PrimitiveIdempotents(S); [ <identity partial perm on [ 4 ]>, <identity partial perm on [ 1 ]>, <identity partial perm on [ 2 ]>, <identity partial perm on [ 3 ]> ] gap> S := DualSymmetricInverseMonoid(4); <inverse bipartition monoid of degree 4 with 3 generators> gap> PrimitiveIdempotents(S); [ <block bijection: [ 1, 2, 3, -1, -2, -3 ], [ 4, -4 ]>, <block bijection: [ 1, 2, 4, -1, -2, -4 ], [ 3, -3 ]>, <block bijection: [ 1, -1 ], [ 2, 3, 4, -2, -3, -4 ]>, <block bijection: [ 1, 2, -1, -2 ], [ 3, 4, -3, -4 ]>, <block bijection: [ 1, 3, 4, -1, -3, -4 ], [ 2, -2 ]>, <block bijection: [ 1, 4, -1, -4 ], [ 2, 3, -2, -3 ]>, <block bijection: [ 1, 3, -1, -3 ], [ 2, 4, -2, -4 ]> ]
‣ RightCosetsOfInverseSemigroup( S, T ) | ( operation ) |
Returns: A list of lists of elements.
RightCosetsOfInverseSemigroup takes a majorantly closed inverse subsemigroup T of an inverse semigroup of partial permutations, block bijections or partial permutation bipartitions S. See IsMajorantlyClosed (4.7-6). The result is a list of the right cosets of T in S.
For s ∈ S, the right coset overlineTs is defined if and only if ss^-1 ∈ T, in which case it is defined to be the majorant closure of the set Ts. See MajorantClosure (4.7-9). Distinct cosets are disjoint but do not necessarily partition S.
gap> S := SymmetricInverseSemigroup(3); <symmetric inverse monoid of degree 3> gap> T := InverseSemigroup(MajorantClosure(S,[PartialPerm([1])])); <inverse partial perm monoid of rank 3 with 6 generators> gap> IsMajorantlyClosed(S,T); true gap> RC := RightCosetsOfInverseSemigroup(S,T); [ [ <identity partial perm on [ 1 ]>, <identity partial perm on [ 1, 2 ]>, [2,3](1), [3,2](1), <identity partial perm on [ 1, 3 ]>, <identity partial perm on [ 1, 2, 3 ]>, (1)(2,3) ], [ [1,3], [2,1,3], [1,3](2), (1,3), [1,3,2], (1,3,2), (1,3)(2) ], [ [1,2], (1,2), [1,2,3], [3,1,2], [1,2](3), (1,2)(3), (1,2,3) ] ]
‣ SameMinorantsSubgroup( H ) | ( attribute ) |
Returns: A list of elements of the group \(\mathscr{H}\)-class H.
Given a group \(\mathscr{H}\)-class H in an inverse semigroup of partial permutations, block bijections or partial permutation bipartitions S, SameMinorantsSubgroup returns a list of the elements of H which have the same strict minorants as the identity element of H. A strict minorant of x in H is an element of S which is less than x (with respect to the natural partial order), but is not equal to x.
The returned list of elements of H describe a subgroup of H.
gap> S := SymmetricInverseSemigroup(3); <symmetric inverse monoid of degree 3> gap> H := GroupHClass(GreensDClasses(S)[1]); <Green's H-class: <identity partial perm on [ 1, 2, 3 ]>> gap> Elements(H); [ <identity partial perm on [ 1, 2, 3 ]>, (1)(2,3), (1,2)(3), (1,2,3), (1,3,2), (1,3)(2) ] gap> SameMinorantsSubgroup(H); [ <identity partial perm on [ 1, 2, 3 ]> ] gap> T := InverseSemigroup( > PartialPerm( [ 1, 2, 3, 4 ], [ 1, 2, 4, 3 ] ), > PartialPerm( [ 1 ], [ 1 ] ), PartialPerm( [ 2 ], [ 2 ] ) ); <inverse partial perm semigroup of rank 4 with 3 generators> gap> Elements(T); [ <empty partial perm>, <identity partial perm on [ 1 ]>, <identity partial perm on [ 2 ]>, <identity partial perm on [ 1, 2, 3, 4 ]>, (1)(2)(3,4) ] gap> x := GroupHClass(GreensDClasses(T)[1]); <Green's H-class: <identity partial perm on [ 1, 2, 3, 4 ]>> gap> Elements(x); [ <identity partial perm on [ 1, 2, 3, 4 ]>, (1)(2)(3,4) ] gap> SameMinorantsSubgroup(x); [ <identity partial perm on [ 1, 2, 3, 4 ]>, (1)(2)(3,4) ]
‣ SmallerDegreePartialPermRepresentation( S ) | ( attribute ) |
Returns: An isomorphism.
SmallerDegreePartialPermRepresentation attempts to find an isomorphism from the inverse semigroup S of partial permutations to another inverse semigroup of partial permutations with smaller degree. If the function cannot reduce the degree, the identity mapping is returned.
There is no guarantee that the smallest possible degree representation is returned. For more information see [Sch92].
gap> S := InverseSemigroup(PartialPerm([2, 1, 4, 3, 6, 5, 8, 7])); <commutative inverse partial perm semigroup of rank 8 with 1 generator> gap> Elements(S); [ <identity partial perm on [ 1, 2, 3, 4, 5, 6, 7, 8 ]>, (1,2)(3,4)(5,6)(7,8) ] gap> T := SmallerDegreePartialPermRepresentation(S); MappingByFunction( <partial perm group of size 2, rank 8 with 1 generator>, <commutative inverse partial perm semigroup of rank 2 with 1 generator>, function( x ) ... end, function( x ) ... end ) gap> R := Range(T); <commutative inverse partial perm semigroup of rank 2 with 1 generator> gap> Elements(R); [ <identity partial perm on [ 1, 2 ]>, (1,2) ] gap> S := DualSymmetricInverseMonoid(5);; gap> T := Range(IsomorphismPartialPermSemigroup(S)); <inverse partial perm monoid of rank 6721 with 3 generators>
‣ VagnerPrestonRepresentation( S ) | ( attribute ) |
Returns: An isomorphism to an inverse semigroup of partial permutations.
VagnerPrestonRepresentation returns an isomorphism from an inverse semigroup S where the elements of S have a unique semigroup inverse accessible via Inverse (Reference: Inverse), to the inverse semigroup of partial permutations T of degree equal to the size of S, which is obtained using the Vagner-Preston Representation Theorem.
More precisely, if f:S-> T is the isomorphism returned by VagnerPrestonRepresentation(S) and x is in S, then f(x) is the partial permutation with domain Sx^-1 and range Sx^-1x defined by f(x): sx^-1↦ sx^-1x.
In many cases, it is possible to find a smaller degree representation than that provided by VagnerPrestonRepresentation using IsomorphismPartialPermSemigroup (Reference: IsomorphismPartialPermSemigroup) or SmallerDegreePartialPermRepresentation (4.7-14).
gap> S := SymmetricInverseSemigroup(2); <symmetric inverse monoid of degree 2> gap> Size(S); 7 gap> iso := VagnerPrestonRepresentation(S); MappingByFunction( <symmetric inverse monoid of degree 2>, <inverse partial perm monoid of rank 7 with 2 generators> , function( x ) ... end, function( x ) ... end ) gap> RespectsMultiplication(iso); true gap> inv := InverseGeneralMapping(iso);; gap> ForAll(S, x-> (x^iso)^inv=x); true gap> V := InverseSemigroup([ > Bipartition( [ [ 1, -4 ], [ 2, -1 ], [ 3, -5 ], > [ 4 ], [ 5 ], [ -2 ], [ -3 ] ] ), > Bipartition( [ [ 1, -5 ], [ 2, -1 ], [ 3, -3 ], > [ 4 ], [ 5 ], [ -2 ], [ -4 ] ] ), > Bipartition( [ [ 1, -2 ], [ 2, -4 ], [ 3, -5 ], > [ 4, -1 ], [ 5, -3 ] ] ) ]); <inverse bipartition semigroup of degree 5 with 3 generators> gap> IsInverseSemigroup(V); true gap> VagnerPrestonRepresentation(V); MappingByFunction( <inverse bipartition semigroup of size 394, degree 5 with 3 generators>, <inverse partial perm semigroup of rank 394 with 5 generators> , function( x ) ... end, function( x ) ... end )
‣ CharacterTableOfInverseSemigroup( S ) | ( attribute ) |
Returns: The character table of the inverse semigroup S and a list of conjugacy class representatives of S.
Returns a list with two entries: the first entry being the character table of the inverse semigroup S as a matrix, while the second entry is a list of conjugacy class representatives of S.
The order of the columns in the character table matrix follows the order of the conjugacy class representatives list. The conjugacy representatives are grouped by \(\mathscr{D}\)-class and then sorted by rank. Also, as is typical of character tables, the rows of the matrix correspond to the irreducible characters and the columns correspond to the conjugacy classes.
This function was contributed by Jhevon Smith and Ben Steinberg.
gap> S := InverseMonoid( [ PartialPerm( [ 1, 2 ], [ 3, 1 ] ), > PartialPerm( [ 1, 2, 3 ], [ 1, 3, 4 ] ), > PartialPerm( [ 1, 2, 3 ], [ 2, 4, 1 ] ), > PartialPerm( [ 1, 3, 4 ], [ 3, 4, 1 ] ) ] );; gap> CharacterTableOfInverseSemigroup(S); [ [ [ 1, 0, 0, 0, 0, 0, 0, 0 ], [ 3, 1, 1, 1, 0, 0, 0, 0 ], [ 3, 1, E(3), E(3)^2, 0, 0, 0, 0 ], [ 3, 1, E(3)^2, E(3), 0, 0, 0, 0 ], [ 6, 3, 0, 0, 1, -1, 0, 0 ], [ 6, 3, 0, 0, 1, 1, 0, 0 ], [ 4, 3, 0, 0, 2, 0, 1, 0 ], [ 1, 1, 1, 1, 1, 1, 1, 1 ] ], [ <identity partial perm on [ 1, 2, 3, 4 ]>, <identity partial perm on [ 1, 3, 4 ]>, (1,3,4), (1,4,3), <identity partial perm on [ 1, 3 ]>, (1,3), <identity partial perm on [ 3 ]>, <empty partial perm> ] ] gap> S := SymmetricInverseMonoid(4);; gap> CharacterTableOfInverseSemigroup(S); [ [ [ 1, -1, 1, 1, -1, 0, 0, 0, 0, 0, 0, 0 ], [ 3, -1, 0, -1, 1, 0, 0, 0, 0, 0, 0, 0 ], [ 2, 0, -1, 2, 0, 0, 0, 0, 0, 0, 0, 0 ], [ 3, 1, 0, -1, -1, 0, 0, 0, 0, 0, 0, 0 ], [ 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0 ], [ 4, -2, 1, 0, 0, 1, -1, 1, 0, 0, 0, 0 ], [ 8, 0, -1, 0, 0, 2, 0, -1, 0, 0, 0, 0 ], [ 4, 2, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0 ], [ 6, 0, 0, -2, 0, 3, -1, 0, 1, -1, 0, 0 ], [ 6, 2, 0, 2, 0, 3, 1, 0, 1, 1, 0, 0 ], [ 4, 2, 1, 0, 0, 3, 1, 0, 2, 0, 1, 0 ], [ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 ] ], [ <identity partial perm on [ 1, 2, 3, 4 ]>, (1)(2)(3,4), (1)(2,3,4), (1,2)(3,4), (1,2,3,4), <identity partial perm on [ 1, 2, 3 ]>, (1)(2,3), (1,2,3), <identity partial perm on [ 1, 2 ]>, (1,2), <identity partial perm on [ 1 ]>, <empty partial perm> ] ]
In this section, we describe some functions for creating pictures of various structures related to a semigroup of transformations, partial permutations, or bipartitions; or a subsemigroup of a Rees 0-matrix semigroup.
Several of the functions described in this section return a string, which can be written to a file using the function FileString (GAPDoc: FileString) or viewed using Splash (4.8-1).
‣ Splash( str[, opts] ) | ( function ) |
Returns: Nothing.
This function attempts to convert the string str into a pdf document and open this document, i.e. to splash it all over your monitor.
The string str must correspond to a valid dot or LaTeX text file and you must have have GraphViz and pdflatex installed on your computer. For details about these file formats, see http://www.latex-project.org and http://www.graphviz.org.
This function is provided to allow convenient, immediate viewing of the pictures produced by the functions: TikzBlocks (5.8-2), TikzBipartition (5.8-1), DotSemilatticeOfIdempotents (4.8-3), and DotDClasses (4.8-2).
The optional second argument opts should be a record with components corresponding to various options, given below.
this should be a string representing the path to the directory where you want Splash to do its work. The default value of this option is "~/".
this should be a string representing the name of the directory in path where you want Splash to do its work. This function will create this directory if does not already exist.
The default value of this option is "tmp.viz" if the option path is present, and the result of DirectoryTemporary (Reference: DirectoryTemporary) is used otherwise.
this should be a string representing the name of the file where str will be written. The default value of this option is "vizpicture".
this should be a string representing the name of the program which should open the files produced by GraphViz or pdflatex.
this option can be used to specify that the string str contains a LaTeX or dot document. You can specify this option in str directly by making the first line "%latex" or "//dot". There is no default value for this option, this option must be specified in str or in opt.type.
this should be a string representing the type of file which Splash should produce. For LaTeX files, this option is ignored and the default value "pdf" is used.
This function was written by Attila Egri-Nagy and Manuel Delgado with some minor changes by J. D. Mitchell.
gap> Splash(DotDClasses(FullTransformationMonoid(4)));‣ DotDClasses( S ) | ( attribute ) |
‣ DotDClasses( S, record ) | ( operation ) |
Returns: A string.
This function produces a graphical representation of the partial order of the \(\mathscr{D}\)-classes of the semigroup S together with the eggbox diagram of each \(\mathscr{D}\)-class. The output is in dot format (also known as GraphViz) format. For details about this file format, and information about how to display or edit this format see http://www.graphviz.org.
The string returned by DotDClasses can be written to a file using the command FileString (GAPDoc: FileString).
The \(\mathscr{D}\)-classes are shown as eggbox diagrams with \(\mathscr{L}\)-classes as rows and \(\mathscr{R}\)-classes as columns; group \(\mathscr{H}\)-classes are shaded gray and contain an asterisk. The \(\mathscr{D}\)-classes are numbered according to their index in GreensDClasses(S), so that an i appears next to the eggbox diagram of GreensDClasses(S)[i]. A red line from one \(\mathscr{D}\)-class to another indicates that the higher \(\mathscr{D}\)-class is greater than the lower one in the \(\mathscr{D}\)-order on S.
If the optional second argument record is present, it can be used to specify some options for output.
if record.number is false, then the \(\mathscr{D}\)-classes in the diagram are not numbered according to their index in the list of \(\mathscr{D}\)-classes of S. The default value for this option is true.
if record.maximal is true, then the structure description of the group \(\mathscr{H}\)-classes is displayed; see StructureDescription (Reference: StructureDescription). Setting this attribute to true can adversely affect the performance of DotDClasses. The default value for this option is false.
gap> S:=FullTransformationSemigroup(3); <full transformation semigroup of degree 3> gap> DotDClasses(S); "digraph DClasses {\nnode [shape=plaintext]\nedge [color=red,arrowhe\ ad=none]\n1 [shape=box style=dotted label=<\n<TABLE BORDER=\"0\" CELL\ BORDER=\"1\" CELLPADDING=\"10\" CELLSPACING=\"0\" PORT=\"1\">\n<TR BO\ RDER=\"0\"><TD COLSPAN=\"1\" BORDER=\"0\" >1</TD></TR><TR><TD BGCOLOR\ =\"grey\">*</TD></TR>\n</TABLE>>];\n2 [shape=box style=dotted label=<\ \n<TABLE BORDER=\"0\" CELLBORDER=\"1\" CELLPADDING=\"10\" CELLSPACING\ =\"0\" PORT=\"2\">\n<TR BORDER=\"0\"><TD COLSPAN=\"3\" BORDER=\"0\" >\ 2</TD></TR><TR><TD BGCOLOR=\"grey\">*</TD><TD BGCOLOR=\"grey\">*</TD>\ <TD></TD></TR>\n<TR><TD BGCOLOR=\"grey\">*</TD><TD></TD><TD BGCOLOR=\ \"grey\">*</TD></TR>\n<TR><TD></TD><TD BGCOLOR=\"grey\">*</TD><TD BGC\ OLOR=\"grey\">*</TD></TR>\n</TABLE>>];\n3 [shape=box style=dotted lab\ el=<\n<TABLE BORDER=\"0\" CELLBORDER=\"1\" CELLPADDING=\"10\" CELLSPA\ CING=\"0\" PORT=\"3\">\n<TR BORDER=\"0\"><TD COLSPAN=\"1\" BORDER=\"0\ \" >3</TD></TR><TR><TD BGCOLOR=\"grey\">*</TD></TR>\n<TR><TD BGCOLOR=\ \"grey\">*</TD></TR>\n<TR><TD BGCOLOR=\"grey\">*</TD></TR>\n</TABLE>>\ ];\n1 -> 2\n2 -> 3\n }" gap> FileString(DotDClasses(S), "t3.dot"); fail gap> FileString("t3.dot", DotDClasses(S)); 966
‣ DotSemilatticeOfIdempotents( S ) | ( attribute ) |
Returns: A string.
This function produces a graphical representation of the semilattice of the idempotents of an inverse semigroup S where the elements of S have a unique semigroup inverse accessible via Inverse (Reference: Inverse). The idempotents are grouped by the \(\mathscr{D}\)-class they belong to.
The output is in dot format (also known as GraphViz) format. For details about this file format, and information about how to display or edit this format see http://www.graphviz.org.
gap> S:=DualSymmetricInverseMonoid(4); <inverse bipartition monoid of degree 4 with 3 generators> gap> DotSemilatticeOfIdempotents(S); "graph graphname {\n node [shape=point]\nranksep=2;\nsubgraph cluste\ r_1{\n15 \n}\nsubgraph cluster_2{\n5 11 14 8 12 13 \n}\nsubgraph clus\ ter_3{\n2 3 10 4 6 9 7 \n}\nsubgraph cluster_4{\n1 \n}\n2 -- 1\n3 -- \ 1\n4 -- 1\n5 -- 2\n5 -- 3\n5 -- 4\n6 -- 1\n7 -- 1\n8 -- 2\n8 -- 6\n8 \ -- 7\n9 -- 1\n10 -- 1\n11 -- 2\n11 -- 9\n11 -- 10\n12 -- 3\n12 -- 6\n\ 12 -- 9\n13 -- 3\n13 -- 7\n13 -- 10\n14 -- 4\n14 -- 6\n14 -- 10\n15 -\ - 5\n15 -- 8\n15 -- 11\n15 -- 12\n15 -- 13\n15 -- 14\n }"
generated by GAPDoc2HTML