In this chapter we describe the various ways to define a homomorphism from a semigroup to another semigroup.
‣ SemigroupHomomorphismByImages( S, T, gens, imgs ) | ( operation ) |
‣ SemigroupHomomorphismByImages( S, T, imgs ) | ( operation ) |
‣ SemigroupHomomorphismByImages( S, T ) | ( operation ) |
‣ SemigroupHomomorphismByImages( S, gens, imgs ) | ( operation ) |
Returns: A semigroup homomorphism, or fail.
SemigroupHomomorphismByImages attempts to construct a homomorphism from the semigroup S to the semigroup T by mapping the i-th element of gens to the i-th element of imgs. If this mapping corresponds to a homomorphism, the homomorphism is returned, and if not, then fail is returned. Similarly, if gens does not generate S, fail is returned.
If omitted, the arguments gens and imgs default to the generators of S and T respectively. See GeneratorsOfSemigroup (Reference: GeneratorsOfSemigroup).
If T is not given, then it defaults to the semigroup generated by imgs, resulting in the mapping being surjective.
gap> S := FullTransformationMonoid(3);; gap> gens := GeneratorsOfSemigroup(S);; gap> J := FullTransformationMonoid(4);; gap> imgs := ListWithIdenticalEntries(4, > ConstantTransformation(3, 1));; gap> hom := SemigroupHomomorphismByImages(S, J, gens, imgs); <full transformation monoid of degree 3> -> <full transformation monoid of degree 4>
‣ SemigroupHomomorphismByFunctionNC( S, T, fun ) | ( operation ) |
‣ SemigroupHomomorphismByFunction( S, T, fun ) | ( operation ) |
Returns: A semigroup homomorphism or fail.
SemigroupHomomorphismByFunctionNC returns a semigroup homomorphism with source S and range T, such that each element s in S is mapped to the element fun(s), where fun is a GAP function.
The function SemigroupHomomorphismByFunctionNC performs no checks on whether the function actually gives a homomorphism, and so it is possible for this operation to return a mapping from S to T that is not a homomorphism.
The function SemigroupHomomorphismByFunction checks that the mapping from S to T defined by fun satisfies RespectsMultiplication (Reference: RespectsMultiplication), which can be expensive. If RespectsMultiplication (Reference: RespectsMultiplication) does not hold, then fail is returned.
gap> g := Semigroup([(1, 2, 3, 4), (1, 2)]);; gap> h := Semigroup([(1, 2, 3), (1, 2)]);; gap> hom := SemigroupHomomorphismByFunction(g, h, > function(x) > if SignPerm(x) = -1 then return (1, 2); > else return (); > fi; end); <semigroup of size 24, with 2 generators> -> <semigroup of size 6, with 2 generators>
The following methods relate to semigroup homomorphisms by images or by function:
Range (Reference: range),
Image (Reference: Image),
Images (Reference: Images),
ImageElm (Reference: ImageElm),
PreImage (Reference: PreImage),
PreImages (Reference: PreImages),
PreImagesRepresentative (Reference: PreImagesRepresentative),
PreImagesRange (Reference: PreImagesRange),
PreImagesElm (Reference: PreImagesElm),
PreImagesSet (Reference: PreImagesSet),
IsSurjective (Reference: IsSurjective),
IsInjective (Reference: IsInjective),
IsBijective (Reference: IsBijective),
Source (Reference: Source),
Range (Reference: range),
ImagesSource (Reference: ImagesSource),
KernelOfSemigroupHomomorphism (14.1-7).
‣ IsSemigroupHomomorphismByImages( hom ) | ( filter ) |
Returns: true or false.
IsSemigroupHomomorphismByImages returns true if hom is a semigroup homomorphism by images and false if it is not. A semigroup homomorphism is a mapping from a semigroup S to a semigroup T that respects multiplication. This representation describes semigroup homomorphisms internally by the generators of S and their images in T. See SemigroupHomomorphismByImages (14.1-1).
gap> S := FullTransformationMonoid(3);; gap> gens := GeneratorsOfSemigroup(S);; gap> T := FullTransformationMonoid(4);; gap> imgs := ListWithIdenticalEntries(4, ConstantTransformation(3, 1));; gap> hom := SemigroupHomomorphismByImages(S, T, gens, imgs); <full transformation monoid of degree 3> -> <full transformation monoid of degree 4> gap> IsSemigroupHomomorphismByImages(hom); true
‣ IsSemigroupHomomorphismByFunction( hom ) | ( filter ) |
Returns: true or false.
IsSemigroupHomomorphismByFunction returns true if hom was created using SemigroupHomomorphismByFunction (14.1-2) and false if it was not. Note that this filter may return true even if the underlying GAP function does not define a homomorphism. A semigroup homomorphism is a mapping from a semigroup S to a semigroup T that respects multiplication. This representation describes semigroup homomorphisms internally using a GAP function mapping elements of S to their images in T.
gap> S := Semigroup([(1, 2, 3, 4), (1, 2)]);; gap> T := Semigroup([(1, 2, 3), (1, 2)]);; gap> hom := SemigroupHomomorphismByFunction(S, T, > function(x) if SignPerm(x) = -1 then return (1, 2); > else return ();fi; end); <semigroup of size 24, with 2 generators> -> <semigroup of size 6, with 2 generators> gap> IsSemigroupHomomorphismByFunction(hom); true
‣ AsSemigroupHomomorphismByImages( hom ) | ( operation ) |
Returns: A semigroup homomorphism, or fail.
AsSemigroupHomomorphismByImages takes hom, a semigroup homomorphism, and returns the same mapping but represented internally using the generators of Source(hom) and their images in Range(hom). If hom not a semigroup homomorphism, then fail is returned. For example, this could happen if hom was created using SemigroupIsomorphismByFunction (14.2-9) and a function which does not give a homomorphism.
gap> S := Semigroup([(1, 2, 3, 4), (1, 2)]);; gap> T := Semigroup([(1, 2, 3), (1, 2)]);; gap> hom := SemigroupHomomorphismByFunction(S, T, > function(x) if SignPerm(x) = -1 then return (1, 2); > else return (); fi; end); <semigroup of size 24, with 2 generators> -> <semigroup of size 6, with 2 generators>
‣ AsSemigroupHomomorphismByFunction( hom ) | ( operation ) |
Returns: A semigroup homomorphism.
AsSemigroupHomomorphismByFunction takes hom, a semigroup homomorphism, and returns the same mapping but described by a GAP function mapping elements of Source(hom) to their images in Range(hom).
gap> T := TrivialSemigroup();; gap> S := GLM(2, 2);; gap> gens := GeneratorsOfSemigroup(S);; gap> imgs := ListX(gens, x -> IdentityTransformation);; gap> hom := SemigroupHomomorphismByImages(S, T, gens, imgs);; gap> hom := AsSemigroupHomomorphismByFunction(hom); <general linear monoid 2x2 over GF(2)> -> <trivial transformation group of degree 0 with 1 generator>
‣ KernelOfSemigroupHomomorphism( hom ) | ( attribute ) |
Returns: A semigroup congruence.
KernelOfSemigroupHomomorphism returns the kernel of the semigroup homomorphism hom. The kernel of a semigroup homomorphism hom is a semigroup congruence relating pairs of elements in Source(hom) mapping to the same element under hom.
gap> S := Semigroup([Transformation([2, 1, 5, 1, 5]), > Transformation([1, 1, 1, 5, 3]), > Transformation([2, 5, 3, 5, 3])]);; gap> congs := CongruencesOfSemigroup(S);; gap> cong := congs[3];; gap> T := S / cong;; gap> gens := GeneratorsOfSemigroup(S);; gap> images := List(gens, gen -> EquivalenceClassOfElement(cong, gen));; gap> hom1 := SemigroupHomomorphismByImages(S, T, gens, images);; gap> cong = KernelOfSemigroupHomomorphism(hom1); true
‣ 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 (14.2-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 isomorphic 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 (14.2-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 (14.2-4) and OnMultiplicationTable (14.2-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 (14.2-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"
‣ SemigroupIsomorphismByImages( S, T, gens, imgs ) | ( operation ) |
‣ SemigroupIsomorphismByImages( S, T, imgs ) | ( operation ) |
‣ SemigroupIsomorphismByImages( S, T ) | ( operation ) |
‣ SemigroupIsomorphismByImages( S, gens, imgs ) | ( operation ) |
Returns: A semigroup isomorphism, or fail.
SemigroupIsomorphismByImages attempts to construct a isomorphism from the semigroup S to the semigroup T, by mapping the i-th element of gens to the i-th element of imgs. If this mapping corresponds to an isomorphism, the isomorphism is returned, and if not, then fail is returned. An isomorphism is a bijective homomorphism. See also SemigroupHomomorphismByImages (14.1-1).
gap> S := Semigroup([ > Matrix(IsNTPMatrix, [[0, 1, 2], [4, 3, 0], [0, 2, 0]], 9, 4), > Matrix(IsNTPMatrix, [[1, 1, 0], [4, 1, 1], [0, 0, 0]], 9, 4)]);; gap> T := AsSemigroup(IsTransformationSemigroup, S);; gap> iso := SemigroupIsomorphismByImages(S, T); <semigroup of size 46, 3x3 ntp matrices with 2 generators> -> <transformation semigroup of size 46, degree 47 with 2 generators>
‣ SemigroupIsomorphismByFunctionNC( S, T, fun, invFun ) | ( operation ) |
‣ SemigroupIsomorphismByFunction( S, T, fun, invFun ) | ( operation ) |
Returns: A semigroup isomorphism or fail.
SemigroupIsomorphismByFunctionNC returns a semigroup isomorphism with source S and range T, such that each element s in S is mapped to the element fun(s), where fun is a GAP function, and invFun its inverse, mapping fun(s) back to s.
The function SemigroupIsomorphismByFunctionNC performs no checks on whether the function actually gives an isomorphism, and so it is possible for this operation to return a mapping from S to T that is not a homomorphism, or not a bijection, or where the return value of InverseGeneralMapping (Reference: InverseGeneralMapping) is not the inverse of the returned function.
The function SemigroupIsomorphismByFunction checks that: the mapping from S to T defined by fun satisfies RespectsMultiplication (Reference: RespectsMultiplication); that the function from T to S defined by invFun satisfies RespectsMultiplication (Reference: RespectsMultiplication); and that these functions are mutual inverses. This can be expensive. If any of these checks fails, then fail is returned.
gap> S := MonogenicSemigroup(IsTransformationSemigroup, 3, 2);; gap> T := MonogenicSemigroup(IsBipartitionSemigroup, 3, 2);; gap> map := x -> T.1 ^ Length(Factorization(S, x));; gap> inv := x -> S.1 ^ Length(Factorization(T, x));; gap> iso := SemigroupIsomorphismByFunction(S, T, map, inv); <commutative non-regular transformation semigroup of size 4, degree 5 with 1 generator> -> <commutative non-regular block bijection semigroup of size 4, degree 6 with 1 generator>
‣ IsSemigroupIsomorphismByFunction( iso ) | ( filter ) |
Returns: true or false.
IsSemigroupIsomorphismByFunction returns true if hom satisfies IsSemigroupHomomorphismByFunction (14.1-4) and IsBijective (Reference: IsBijective), and false if does not. Note that this filter may return true even if the underlying GAP function does not define a homomorphism. A semigroup isomorphism is a mapping from a semigroup S to a semigroup T that respects multiplication. This representation describes semigroup isomorphisms internally by using a GAP function mapping elements of S to their images in T. See SemigroupIsomorphismByFunction (14.2-9).
gap> S := MonogenicSemigroup(IsTransformationSemigroup, 3, 2);; gap> T := MonogenicSemigroup(IsBipartitionSemigroup, 3, 2);; gap> map := x -> T.1 ^ Length(Factorization(S, x));; gap> inv := x -> S.1 ^ Length(Factorization(T, x));; gap> iso := SemigroupIsomorphismByFunction(S, T, map, inv); <commutative non-regular transformation semigroup of size 4, degree 5 with 1 generator> -> <commutative non-regular block bijection semigroup of size 4, degree 6 with 1 generator> gap> IsSemigroupIsomorphismByFunction(iso); true
‣ AsSemigroupIsomorphismByFunction( hom ) | ( operation ) |
Returns: A semigroup isomorphism, or fail.
AsSemigroupIsomorphismByFunction takes a semigroup homomorphism hom and returns a semigroup isomorphism represented using GAP functions for the isomorphism and its inverse. If hom is not bijective, then fail is returned.
gap> S := FullTransformationMonoid(3);; gap> gens := GeneratorsOfSemigroup(S);; gap> imgs := ListWithIdenticalEntries(4, ConstantTransformation(3, 1));; gap> hom := SemigroupHomomorphismByImages(S, S, gens, gens);; gap> AsSemigroupIsomorphismByFunction(hom); <full transformation monoid of degree 3> -> <full transformation monoid of degree 3>
‣ SmallerDegreeTransformationRepresentation( S ) | ( attribute ) |
Returns: An isomorphism to a transformation semigroup.
This function attempts to find a small degree transformation representation of the semigroup S. The implementation attempts to find a right congruence of S that S acts on (the equivalence classes of) faithfully.
If S is not a finitely presented semigroup, then the returned isomorphism is the composition of an isomorphism to a finitely presented semigroup and an isomorphism from that finitely presented semigroup to a transformation semigroup.
The runtime of this function depends on the presentation for S that is either given explicitly or computed by the Semigroups package, but it is difficult to predict what properties of the presentation lead to a shorter runtime. This is unlikely to terminate in a reasonable amount of time for semigroups with more than approx. 10000 elements, but might also not terminate quickly for smaller semigroups depending on the presentation used.
gap> S := BrauerMonoid(3); <regular bipartition *-monoid of degree 3 with 3 generators> gap> IsomorphismTransformationSemigroup(S); <regular bipartition *-monoid of size 15, degree 3 with 3 generators> -> <transformation monoid of size 15, degree 15 with 3 generators> gap> SmallerDegreeTransformationRepresentation(S); CompositionMapping( <fp semigroup with 4 generators and 20 relations of length 81> -> <transformation monoid of degree 7 with 3 generators>, <regular bipartition *-monoid of size 15, degree 3 with 3 generators> -> <fp semigroup with 4 generators and 20 relations of length 81> ) gap> S := JonesMonoid(5); <regular bipartition *-monoid of degree 5 with 4 generators> gap> Size(S); 42 gap> SmallerDegreeTransformationRepresentation(S); CompositionMapping( <fp semigroup with 5 generators and 28 relations of length 120> -> <transformation monoid of degree 10 with 4 generators>, <regular bipartition *-monoid of size 42, degree 5 with 4 generators> -> <fp semigroup with 5 generators and 28 relations of length 120> )
‣ MinimalFaithfulTransformationDegree( S ) | ( attribute ) |
Returns: A positive integer.
This function returns the minimal degree of a faithful transformation representation of the semigroup S. This is currently only implemented for a very small number of types of semigroups.
gap> S := RightZeroSemigroup(10); <transformation semigroup of degree 7 with 10 generators> gap> MinimalFaithfulTransformationDegree(S); 7
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 (14.3-2) or RZMSIsoByTriple (14.3-2), and will satisfy the filter IsRMSIsoByTriple (14.3-1) or IsRZMSIsoByTriple (14.3-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 14.3-7, and basic operations are: Range (Reference: range), Source (Reference: Source), ELM_LIST (14.3-3), CompositionMapping (Reference: CompositionMapping), ImagesElm (14.3-5), ImagesRepresentative (14.3-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_\lambda\) 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 (14.3-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)( 3, 5)( 8,10)( 9,11), GroupHomomorphismByImages( Group( [ (1,2,3,4) ] ), Group( [ (1,2,3,4) ] ), [ (1,2,3,4) ], [ (1,2,3,4) ] ), [ (), (1,3)(2,4), (1,3)(2,4), (1,3)(2,4), (1,3)(2,4), (1,3)(2,4), (), (1,3)(2,4), (1,3)(2,4), (1,3)(2,4), (1,3)(2,4), (1,3)(2,4) ]) gap> CompositionMapping2(G.2, G.3); (( 2, 4)( 3, 5)( 8,10)( 9,11), GroupHomomorphismByImages( Group( [ (1,2,3,4) ] ), Group( [ (1,2,3,4) ] ), [ (1,2,3,4) ], [ (1,2,3,4) ] ), [ (), (1,3)(2,4), (1,3)(2,4), (1,3)(2,4), (1,3)(2,4), (1,3)(2,4), (), (1,3)(2,4), (1,3)(2,4), (1,3)(2,4), (1,3)(2,4), (1,3)(2,4) ])
‣ 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 UnderlyingSemigroup (Reference: UnderlyingSemigroup for a Rees 0-matrix semigroup) as S but the Matrix (Reference: 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 (14.3-3).
map1 * map2returns the composition of map2 and map1; see CompositionMapping2 (14.3-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 (14.3-5).
generated by GAPDoc2HTML