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

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.

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

equals `S`), p);`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(`

, then this operation returns a multiplication table of a semigroup isomorphic to that defined by `table`)]`table` where the elements `[1 .. Length(`

are relabelled according to `table`)]`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-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);; 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