Goto Chapter: Top 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 Bib Ind

### 18 Semigroup homomorphisms

In this chapter we describe the various ways to define a homomorphism from a semigroup to another semigroup.

#### 18.1 Isomorphisms of arbitrary semigroups

##### 18.1-1 IsIsomorphicSemigroup
 ‣ 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(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.

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

##### 18.1-2 SmallestMultiplicationTable
 ‣ 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 ] ]

##### 18.1-3 IsomorphismSemigroups
 ‣ 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 S = T. See 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([, [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

#### 18.2 Isomorphisms of Rees (0-)matrix semigroups

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).

##### 18.2-1 IsRMSIsoByTriple
 ‣ 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:

1. an isomorphism of the underlying graph of S to the underlying graph of of T

2. an isomorphism from G to H

3. 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).

##### 18.2-2 RMSIsoByTriple
 ‣ 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 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) = RZMSDigraph(R2).

• triple 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 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 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 ] ) ),
[ (), (), (), (), (), () ])


##### 18.2-3 ELM_LIST
 ‣ 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:

1. An isomorphism of the underlying graphs of the source and range of map, respectively.

2. An isomorphism of the underlying groups of the source and range of map, respectively.

3. An function from the union of the rows and columns of the source of map to the underlying group of the range of map.

##### 18.2-4 CompositionMapping2
 ‣ 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:

1. map1 * map2

2. map1 * map2

3. the componentwise product of map1 * map2 and map1 * map2.

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

##### 18.2-5 ImagesElm
 ‣ 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:

1. pt ^ map

2. (pt ^ map) * (pt ^ map) * (pt ^ map) ^ -1

3. pt ^ map.

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

##### 18.2-6 Operators for isomorphisms of Rees (0-)matrix semigroup by triples
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 * 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).

Goto Chapter: Top 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 Bib Ind

generated by GAPDoc2HTML