In this chapter we describe the various ways to define a homomorphism from a semigroup to another semigroup.
‣ IsIsomorphicSemigroup( S, T ) | ( operation ) |
Returns: true or false.
If S and T are semigroups, then this operation attempts to determine whether S and T are isomorphic semigroups by using the operation IsomorphismSemigroups (18.1-6). If IsomorphismSemigroups(S, T) returns an isomorphism, then IsIsomorphicSemigroup(S, T) returns true, while if IsomorphismSemigroups(S, T) returns fail, then IsIsomorphicSemigroup(S, T) returns false.
Note that in some cases, at present, there is no method for determining whether S is isomorphic to T, even if it is obvious to the user whether or not S and T are isomorphic. There are plans to improve this in the future.
gap> S := Semigroup(PartialPerm([1, 2, 4], [1, 3, 5]), > PartialPerm([1, 3, 5], [1, 2, 4]));; gap> T := AsSemigroup(IsTransformationSemigroup, S);; gap> IsIsomorphicSemigroup(S, T); true gap> IsIsomorphicSemigroup(FullTransformationMonoid(4), > PartitionMonoid(4)); false
‣ SmallestMultiplicationTable( S ) | ( attribute ) |
Returns: The lex-least multiplication table of a semigroup.
This function returns the lex-least multiplication table of a semigroup isomorphic to the semigroup S. SmallestMultiplicationTable returns the lex-least multiplication of any semigroup isomoprhic to S. Due to the high complexity of computing the smallest multiplication table of a semigroup, this function only performs well for semigroups with at most approximately 50 elements.
SmallestMultiplicationTable is based on the function IdSmallSemigroup (Smallsemi: IdSmallSemigroup) by Andreas Distler.
From Version 3.3.0 of Semigroups this attribute is computed using MinimalImage (images: MinimalImage) from the the images package. See also: CanonicalMultiplicationTable (18.1-3).
gap> S := Semigroup( > Bipartition([[1, 2, 3, -1, -3], [-2]]), > Bipartition([[1, 2, 3, -1], [-2], [-3]]), > Bipartition([[1, 2, 3], [-1], [-2, -3]]), > Bipartition([[1, 2, -1], [3, -2], [-3]]));; gap> Size(S); 8 gap> SmallestMultiplicationTable(S); [ [ 1, 1, 3, 4, 5, 6, 7, 8 ], [ 1, 1, 3, 4, 5, 6, 7, 8 ], [ 1, 1, 3, 4, 5, 6, 7, 8 ], [ 1, 3, 3, 4, 5, 6, 7, 8 ], [ 5, 5, 6, 7, 5, 6, 7, 8 ], [ 5, 5, 6, 7, 5, 6, 7, 8 ], [ 5, 6, 6, 7, 5, 6, 7, 8 ], [ 5, 6, 6, 7, 5, 6, 7, 8 ] ]
‣ CanonicalMultiplicationTable( S ) | ( attribute ) |
Returns: A canonical multiplication table (up to isomorphism) of a semigroup.
This function returns a multiplication table of a semigroup isomorphic to the semigroup S. CanonicalMultiplicationTable returns a multiplication that is canonical, in the sense that if two semigroups S and T are isomorphic, then the return values of CanonicalMultiplicationTable are equal.
CanonicalMultiplicationTable uses the machinery for canonical labelling of vertex coloured digraphs in bliss via BlissCanonicalLabelling (Digraphs: BlissCanonicalLabelling for a digraph and a list).
The multiplication table returned by this function is the result of OnMultiplicationTable(MultiplicationTable(S), CanonicalMultiplicationTablePerm(S));
Note that the performance of CanonicalMultiplicationTable is vastly superior to that of SmallestMultiplicationTable.
See also: CanonicalMultiplicationTablePerm (18.1-4) and OnMultiplicationTable (18.1-5).
gap> S := Semigroup( > Bipartition([[1, 2, 3, -1, -3], [-2]]), > Bipartition([[1, 2, 3, -1], [-2], [-3]]), > Bipartition([[1, 2, 3], [-1], [-2, -3]]), > Bipartition([[1, 2, -1], [3, -2], [-3]]));; gap> Size(S); 8 gap> CanonicalMultiplicationTable(S); [ [ 1, 2, 2, 8, 1, 2, 7, 8 ], [ 1, 2, 2, 8, 1, 2, 7, 8 ], [ 1, 2, 6, 4, 5, 6, 7, 8 ], [ 1, 2, 5, 4, 5, 6, 7, 8 ], [ 1, 2, 6, 4, 5, 6, 7, 8 ], [ 1, 2, 6, 4, 5, 6, 7, 8 ], [ 1, 2, 1, 8, 1, 2, 7, 8 ], [ 1, 2, 1, 8, 1, 2, 7, 8 ] ]
‣ CanonicalMultiplicationTablePerm( S ) | ( attribute ) |
Returns: A permutation.
This function returns a permutation p such that OnMultiplicationTable(MultiplicationTable(S), p); equals CanonicalMultiplicationTable(S).
See CanonicalMultiplicationTable (18.1-3) for more details.
CanonicalMultiplicationTablePerm uses the machinery for canonical labelling of vertex coloured digraphs in bliss via BlissCanonicalLabelling (Digraphs: BlissCanonicalLabelling for a digraph and a list).
gap> S := Semigroup( > Bipartition([[1, 2, 3, -1, -3], [-2]]), > Bipartition([[1, 2, 3, -1], [-2], [-3]]), > Bipartition([[1, 2, 3], [-1], [-2, -3]]), > Bipartition([[1, 2, -1], [3, -2], [-3]]));; gap> Size(S); 8 gap> CanonicalMultiplicationTablePerm(S); (1,5,8,3,6,7,2,4)
‣ OnMultiplicationTable( table, p ) | ( operation ) |
Returns: A multiplication table.
If table is a multiplication table of a semigroup and the second argument p is a permutation of [1 .. Length(table)], then this operation returns a multiplication table of a semigroup isomorphic to that defined by table where the elements [1 .. Length(table)] are relabelled according to p.
gap> table := [[1, 1, 3, 4, 5, 6, 7, 8], > [1, 1, 3, 4, 5, 6, 7, 8], > [1, 1, 3, 4, 5, 6, 7, 8], > [1, 3, 3, 4, 5, 6, 7, 8], > [5, 5, 6, 7, 5, 6, 7, 8], > [5, 5, 6, 7, 5, 6, 7, 8], > [5, 6, 6, 7, 5, 6, 7, 8], > [5, 6, 6, 7, 5, 6, 7, 8]];; gap> p := (1, 2, 3, 4)(10, 11, 12);; gap> OnMultiplicationTable(table, p); [ [ 1, 2, 4, 4, 5, 6, 7, 8 ], [ 1, 2, 2, 4, 5, 6, 7, 8 ], [ 1, 2, 2, 4, 5, 6, 7, 8 ], [ 1, 2, 2, 4, 5, 6, 7, 8 ], [ 7, 5, 5, 6, 5, 6, 7, 8 ], [ 7, 5, 5, 6, 5, 6, 7, 8 ], [ 7, 5, 6, 6, 5, 6, 7, 8 ], [ 7, 5, 6, 6, 5, 6, 7, 8 ] ]
‣ IsomorphismSemigroups( S, T ) | ( operation ) |
Returns: An isomorphism, or fail.
This operation attempts to find an isomorphism from the semigroup S to the semigroup T. If it finds one, then it is returned, and if not, then fail is returned.
IsomorphismSemigroups uses the machinery for finding isomorphisms between vertex coloured digraphs in bliss via IsomorphismDigraphs (Digraphs: IsomorphismDigraphs for digraphs and homogeneous lists) using digraphs constructed from the multiplication tables of S and T.
Note that finding an isomorphism between two semigroups is difficult, and may not be possible for semigroups whose size exceeds a few hundred elements. On the other hand, IsomorphismSemigroups may be able deduce that S and T are not isomorphic by finding that some of their semigroup-theoretic properties differ.
gap> S := RectangularBand(IsTransformationSemigroup, 4, 5); <regular transformation semigroup of size 20, degree 9 with 5 generators> gap> T := RectangularBand(IsBipartitionSemigroup, 4, 5); <regular bipartition semigroup of size 20, degree 3 with 5 generators> gap> IsomorphismSemigroups(S, T) <> fail; true gap> D := DClass(FullTransformationMonoid(5), > Transformation([1, 2, 3, 4, 1]));; gap> S := PrincipalFactor(D);; gap> StructureDescription(UnderlyingSemigroup(S)); "S4" gap> S; <Rees 0-matrix semigroup 10x5 over S4> gap> D := DClass(PartitionMonoid(5), > Bipartition([[1], [2, -2], [3, -3], [4, -4], [5, -5], [-1]]));; gap> T := PrincipalFactor(D);; gap> StructureDescription(UnderlyingSemigroup(T)); "S4" gap> T; <Rees 0-matrix semigroup 15x15 over S4> gap> IsomorphismSemigroups(S, T); fail gap> I := SemigroupIdeal(FullTransformationMonoid(5), > Transformation([1, 1, 2, 3, 4]));; gap> T := PrincipalFactor(DClass(I, I.1));; gap> StructureDescription(UnderlyingSemigroup(T)); "S4" gap> T; <Rees 0-matrix semigroup 10x5 over S4> gap> IsomorphismSemigroups(S, T) <> fail; true
‣ AutomorphismGroup( S ) | ( operation ) |
Returns: A group.
This operation returns the group of automorphisms of the semigroup S. AutomorphismGroup uses bliss via AutomorphismGroup (Digraphs: AutomorphismGroup for a digraph and a homogeneous list) using a vertex coloured digraph constructed from the multiplication table of S. Consequently, this method is only really feasible for semigroups whose size does not exceed a few hundred elements.
gap> S := RectangularBand(IsTransformationSemigroup, 4, 5); <regular transformation semigroup of size 20, degree 9 with 5 generators> gap> StructureDescription(AutomorphismGroup(S)); "S4 x S5"
An isomorphism between two regular finite Rees (0-)matrix semigroups whose underlying semigroups are groups can be described by a triple defined in terms of the matrices and underlying groups of the semigroups. For a full description of the theory involved, see Section 3.4 of [How95].
An isomorphism described in this way can be constructed using RMSIsoByTriple (18.2-2) or RZMSIsoByTriple (18.2-2), and will satisfy the filter IsRMSIsoByTriple (18.2-1) or IsRZMSIsoByTriple (18.2-1).
‣ IsRMSIsoByTriple | ( category ) |
‣ IsRZMSIsoByTriple | ( category ) |
The isomorphisms between finite Rees matrix or 0-matrix semigroups S and T over groups G and H, respectively, specified by a triple consisting of:
an isomorphism of the underlying graph of S to the underlying graph of of T
an isomorphism from G to H
a function from Rows(S) union Columns(S) to H
belong to the categories IsRMSIsoByTriple and IsRZMSIsoByTriple. Basic operators for such isomorphism are given in 18.2-7, and basic operations are: Range (Reference: range), Source (Reference: Source), ELM_LIST (18.2-3), CompositionMapping (Reference: CompositionMapping), ImagesElm (18.2-5), ImagesRepresentative (18.2-5), InverseGeneralMapping (Reference: InverseGeneralMapping), PreImagesRepresentative (Reference: PreImagesRepresentative), IsOne (Reference: IsOne).
‣ RMSIsoByTriple( R1, R2, triple ) | ( operation ) |
‣ RZMSIsoByTriple( R1, R2, triple ) | ( operation ) |
Returns: An isomorphism.
If R1 and R2 are isomorphic regular Rees 0-matrix semigroups whose underlying semigroups are groups then RZMSIsoByTriple returns the isomorphism between R1 and R2 defined by triple, which should be a list consisting of the following:
triple[1] should be a permutation describing an isomorphism from the graph of R1 to the graph of R2, i.e. it should satisfy OnDigraphs(RZMSDigraph(R1), triple[1]) = RZMSDigraph(R2).
triple[2] should be an isomorphism from the underlying group of R1 to the underlying group of R2 (see UnderlyingSemigroup (Reference: UnderlyingSemigroup for a rees 0-matrix semigroup)).
triple[3] should be a list of elements from the underlying group of R2. If the Matrix (Reference: Matrix) of R1 has m columns and n rows, then the list should have length m + n, where the first m entries should correspond to the columns of R1's matrix, and the last n entries should correspond to the rows. These column and row entries should correspond to the u_i and v_λ elements in Theorem 3.4.1 of [How95].
If triple describes a valid isomorphism from R1 to R2 then this will return an object in the category IsRZMSIsoByTriple (18.2-1); otherwise an error will be returned.
If R1 and R2 are instead Rees matrix semigroups (without zero) then RMSIsoByTriple should be used instead. This operation is used in the same way, but it should be noted that since an RMS's graph is a complete bipartite graph, triple[1] can be any permutation on [1 .. m + n], so long as no point in [1 .. m] is mapped to a point in [m + 1 .. m + n].
gap> g := SymmetricGroup(3);; gap> mat := [[0, 0, (1, 3)], [(1, 2, 3), (), (2, 3)], [0, 0, ()]];; gap> R := ReesZeroMatrixSemigroup(g, mat);; gap> id := IdentityMapping(g);; gap> g_elms_list := [(), (), (), (), (), ()];; gap> RZMSIsoByTriple(R, R, [(), id, g_elms_list]); ((), IdentityMapping( SymmetricGroup( [ 1 .. 3 ] ) ), [ (), (), (), (), (), () ])
‣ ELM_LIST( map, pos ) | ( operation ) |
Returns: A component of an isomorphism of Rees (0-)matrix semigroups by triple.
ELM_LIST(map, i) returns the ith component of the Rees (0-)matrix semigroup isomorphism by triple map when i = 1, 2, 3.
The components of an isomorphism of Rees (0-)matrix semigroups by triple are:
An isomorphism of the underlying graphs of the source and range of map, respectively.
An isomorphism of the underlying groups of the source and range of map, respectively.
An function from the union of the rows and columns of the source of map to the underlying group of the range of map.
‣ CompositionMapping2( map1, map2 ) | ( operation ) |
‣ CompositionMapping2( map1, map2 ) | ( operation ) |
Returns: A Rees (0-)matrix semigroup by triple.
If map1 and map2 are isomorphisms of Rees matrix or 0-matrix semigroups specified by triples and the range of map2 is contained in the source of map1, then CompositionMapping2(map1, map2) returns the isomorphism from Source(map2) to Range(map1) specified by the triple with components:
map1[1] * map2[1]
map1[2] * map2[2]
the componentwise product of map1[1] * map2[3] and map1[3] * map2[2].
gap> R := ReesZeroMatrixSemigroup(Group([(1, 2, 3, 4)]), > [[(1, 3)(2, 4), (1, 4, 3, 2), (), (1, 2, 3, 4), (1, 3)(2, 4), 0], > [(1, 4, 3, 2), 0, (), (1, 4, 3, 2), (1, 2, 3, 4), (1, 2, 3, 4)], > [(), (), (1, 4, 3, 2), (1, 2, 3, 4), 0, (1, 2, 3, 4)], > [(1, 2, 3, 4), (1, 4, 3, 2), (1, 2, 3, 4), 0, (), (1, 2, 3, 4)], > [(1, 3)(2, 4), (1, 2, 3, 4), 0, (), (1, 4, 3, 2), (1, 2, 3, 4)], > [0, (1, 2, 3, 4), (1, 2, 3, 4), (1, 2, 3, 4), (1, 2, 3, 4), ()]]); <Rees 0-matrix semigroup 6x6 over Group([ (1,2,3,4) ])> gap> G := AutomorphismGroup(R);; gap> G.2; ((), IdentityMapping( Group( [ (1,2,3,4) ] ) ), [ (), (), (), (), (), (), (), (), (), (), (), () ]) gap> G.3; (( 2, 4, 6, 3)( 7,11, 8,10), GroupHomomorphismByImages( Group( [ (1,2,3,4) ] ), Group( [ (1,2,3,4) ] ), [ (1,2,3,4) ], [ (1,2,3,4) ] ), [ (), (1,4,3,2), (1,4,3,2), (), (1,4,3,2), (1,3)(2,4), (), (1,3)(2,4), (), (1,2,3,4), (1,2,3,4), (1,4,3,2) ]) gap> CompositionMapping2(G.2, G.3); (( 2, 4, 6, 3)( 7,11, 8,10), GroupHomomorphismByImages( Group( [ (1,2,3,4) ] ), Group( [ (1,2,3,4) ] ), [ (1,2,3,4) ], [ (1,2,3,4) ] ), [ (), (1,4,3,2), (1,4,3,2), (), (1,4,3,2), (1,3)(2,4), (), (1,3)(2,4), (), (1,2,3,4), (1,2,3,4), (1,4,3,2) ])
‣ ImagesElm( map, pt ) | ( operation ) |
‣ ImagesRepresentative( map, pt ) | ( operation ) |
Returns: An element of a Rees (0-)matrix semigroup or a list containing such an element.
If map is an isomorphism of Rees matrix or 0-matrix semigroups specified by a triple and pt is an element of the source of map, then ImagesRepresentative(map, pt) = pt ^ map returns the image of pt under map.
The image of pt under map of Range(map) is the element with components:
pt[1] ^ map[1]
(pt[1] ^ map[3]) * (pt[2] ^ map[2]) * (pt[3] ^ map[3]) ^ -1
pt[3] ^ map[1].
ImagesElm(map, pt) simply returns [ImagesRepresentative(map, pt)].
gap> R := ReesZeroMatrixSemigroup(Group([(2, 8), (2, 8, 6)]), > [[0, (2, 8), 0, 0, 0, (2, 8, 6)], > [(), 0, (2, 8, 6), (2, 6), (2, 6, 8), 0], > [(2, 8, 6), 0, (2, 6, 8), (2, 8), (), 0], > [(2, 8, 6), 0, (2, 6, 8), (2, 8), (), 0], > [0, (2, 8, 6), 0, 0, 0, (2, 8)], > [(2, 8, 6), 0, (2, 6, 8), (2, 8), (), 0]]); <Rees 0-matrix semigroup 6x6 over Group([ (2,8), (2,8,6) ])> gap> map := RZMSIsoByTriple(R, R, > [(), IdentityMapping(Group([(2, 8), (2, 8, 6)])), > [(), (2, 6, 8), (), (), (), (2, 8, 6), > (2, 8, 6), (), (), (), (2, 6, 8), ()]]);; gap> ImagesElm(map, RMSElement(R, 1, (2, 8), 2)); [ (1,(2,8),2) ]
‣ CanonicalReesZeroMatrixSemigroup( S ) | ( attribute ) |
‣ CanonicalReesMatrixSemigroup( S ) | ( attribute ) |
Returns: A Rees zero matrix semigroup.
If S is a Rees 0-matrix semigroup then CanonicalReesZeroMatrixSemigroup returns an isomorphic Rees 0-matrix semigroup T with the same IsUnderlyingSemigroup (???) as S but the Matrix (???) of T has been canonicalized. The output T is canonical in the sense that for any two inputs which are isomorphic Rees zero matrix semigroups the output of this function is the same.
CanonicalReesMatrixSemigroup works the same but for Rees matrix semigroups.
gap> S := ReesZeroMatrixSemigroup(SymmetricGroup(3), > [[(), (1, 3, 2)], [(), ()]]);; gap> T := CanonicalReesZeroMatrixSemigroup(S); <Rees 0-matrix semigroup 2x2 over Sym( [ 1 .. 3 ] )> gap> Matrix(S); [ [ (), (1,3,2) ], [ (), () ] ] gap> Matrix(T); [ [ (), () ], [ (), (1,2,3) ] ]
map[i]map[i] returns the ith component of the Rees (0-)matrix semigroup isomorphism by triple map when i = 1, 2, 3; see ELM_LIST (18.2-3).
map1 * map2returns the composition of map2 and map1; see CompositionMapping2 (18.2-4).
map1 < map2returns true if map1 is lexicographically less than map2.
map1 = map2returns true if the Rees (0-)matrix semigroup isomorphisms by triple map1 and map2 have equal source and range, and are equal as functions, and false otherwise.
It is possible for map1 and map2 to be equal but to have distinct components.
pt ^ mapreturns the image of the element pt of the source of map under the isomorphism map; see ImagesElm (18.2-5).
generated by GAPDoc2HTML