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-3). If `IsomorphismSemigroups(`

returns an isomorphism, then `S`, `T`)`IsIsomorphicSemigroup(`

returns `S`, `T`)`true`

, while if `IsomorphismSemigroups(`

returns `S`, `T`)`fail`

, then `IsIsomorphicSemigroup(`

returns `S`, `T`)`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.

If the size of `S` and `T` is rather small — with approximately 50 or fewer elements — then it is possible to calculate whether `S` and `T` are isomorphic by using `SmallestMultiplicationTable`

(18.1-2), but this is not currently done by `IsIsomorphicSemigroup`

. In particular, `S` and `T` are isomorphic if and only if `SmallestMultiplicationTable(`

.`S`) = SmallestMultiplicationTable(`T`)

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`

is an isomorphism invariant of semigroups, and so it can, for example, be used to check if two semigroups are isomorphic.

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.

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

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

For many types of semigroup, `IsomorphismSemigroups`

is not able to determine whether or not `S` and `T` are isomorphic, and so this operation may result in an "Error, no method found". `IsomorphismSemigroups`

may be able deduce that `S` and `T` are not isomorphic by finding that some of their semigroup-theoretic properties differ; however it is harder to construct an isomorphism for semigroups that are isomorphic.

At present, `IsomorphismSemigroups`

is only able to return an isomorphism when `S` and `T` are finite simple, 0-simple, or monogenic semigroups, or when

. See `S` = `T``IsSimpleSemigroup`

(15.1-22), `IsZeroSimpleSemigroup`

(15.1-28), and `IsMonogenicSemigroup`

(15.1-11) for more information about these types of semigroups.

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

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-6, 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:

should be a permutation describing an isomorphism from the graph of`triple`[1]`R1`to the graph of`R2`, i.e. it should satisfy`OnDigraphs(RZMSDigraph(`

.`R1`),`triple`[1]) = RZMSDigraph(`R2`)

should be an isomorphism from the underlying group of`triple`[2]`R1`to the underlying group of`R2`(see`UnderlyingSemigroup`

(Reference: UnderlyingSemigroup for a rees 0-matrix semigroup)).

should be a list of elements from the underlying group of`triple`[3]`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,

can be any permutation on `triple`[1]`[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(`

returns the `map`, `i`)`i`

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

returns the isomorphism from `map1`, `map2`)`Source(`

to `map2`)`Range(`

specified by the triple with components:`map1`)

`map1`[1] *`map2`[1]`map1`[2] *`map2`[2]the componentwise product of

and`map1`[1] *`map2`[3]

.`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); <automorphism group of <Rees 0-matrix semigroup 6x6 over Group([ (1,2, 3,4) ])> with 4 generators> 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(`

returns the image of `map`, `pt`) = `pt` ^ `map``pt` under `map`.

The image of `pt` under `map` of `Range(`

is the element with components:`map`)

`pt`[1] ^`map`[1]`(`

`pt`[1] ^`map`[3]) * (`pt`[2] ^`map`[2]) * (`pt`[3] ^`map`[3]) ^ -1

.`pt`[3] ^`map`[1]

`ImagesElm(`

simply returns `map`, `pt`)`[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) ]

`map`[`i`]

returns the`map`[i]`i`th component of the Rees (0-)matrix semigroup isomorphism by triple`map`when

; see`i`= 1, 2, 3`ELM_LIST`

(18.2-3).`map1`*`map2`returns the composition of

`map2`and`map1`; see`CompositionMapping2`

(18.2-4).`map1`<`map2`returns

`true`

if`map1`is lexicographically less than`map2`.`map1`=`map2`returns

`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`^`map`returns the image of the element

`pt`of the source of`map`under the isomorphism`map`; see`ImagesElm`

(18.2-5).

generated by GAPDoc2HTML