Goto Chapter: Top 1 2 3 4 5 6 7 8 Bib Ind

### 5 Homomorphisms of Groupoids

A homomorphism m from a groupoid G to a groupoid H consists of a map from the objects of G to those of H together with a map from the elements of G to those of H which is compatible with tail and head and which preserves multiplication:

m(g1 : o1 \to o2)*m(g2 : o2 \to o3) ~=~ m(g1*g2 : o1 \to o3).

Note that when a homomorphism is not injective on objects, the image of the source need not be a subgroupoid of the range. A simple example of this is given by a homomorphism from the two-object, four-element groupoid with trivial group to the free group ⟨ a ⟩ on one generator, when the image is [1,a^n,a^-n] for some n>0.

Attempts to trace the cause of a longstanding error when using InverseGeneralMapping, as described in 5.4, have revealed errors when using other functions, such as ImageElm. As a result, a redesign of groupoid homomorphisms is planned for the next release.

#### 5.1 Homomorphisms from a connected groupoid

##### 5.1-1 GroupoidHomomorphismFromSinglePiece
 ‣ GroupoidHomomorphismFromSinglePiece( src, rng, hom, imobs, imrays ) ( operation )
 ‣ GroupoidHomomorphism( args ) ( function )
 ‣ InclusionMappingGroupoids( gpd, sgpd ) ( operation )
 ‣ IsomorphismNewObjects( src, objlist ) ( operation )
 ‣ IsomorphismStandardGroupoid( gpd, obs ) ( operation )

As usual, there are various homomorphism operations. The basic construction is a homomorphism ϕ : G -> H with G the direct product of a group and a complete graph. The homomorphism has attributes Source, Range, ImagesOfObjects and RootGroupHomomorphism. The input data consists of the source; the range; and

• a homomorphism hom from the root group of G to that of H;

• a list imobs of the images of the objects of G;

• a list imrays of the elements in the images of the rays of G, so that the image ϕ(r_i : o_1 -> o_i) of the i-th ray is (imrays[i]:imobs[1]->imobs[i]).

The operation IsomorphismNewObjects returns the isomorphism from a groupoid to a groupoid with the same object group and rays but with a different set of objects.

The operation IsomorphismStandardGroupoid(gpd,obs) returns the isomorphism from a groupoid with rays to the groupoid of type IsDirectProductWithCompleteGraph on the given objects.


gap> gend12 := [ (15,16,17,18,19,20), (15,20)(16,19)(17,18) ];;
gap> d12 := Group( gend12 );;
gap> Gd12 := Groupoid( d12, [-37,-36,-35,-34] );;
gap> SetName( d12, "d12" );
gap> SetName( Gd12, "Gd12" );
gap> s3 := Subgroup( d12, [ (15,17,19)(16,18,20), (15,20)(16,19)(17,18) ] );;
gap> Gs3 := SubgroupoidByPieces( Gd12, [ [ s3, [-36,-35,-34] ] ] );;
gap> SetName( s3, "s3" );
gap> SetName( Gs3, "Gs3" );
gap> gend8 := GeneratorsOfGroup( d8 );;
gap> imhd8 := [ ( ), (15,20)(16,19)(17,18) ];;
gap> hd8 := GroupHomomorphismByImages( d8, s3, gend8, imhd8 );;
gap> homd8 := GroupoidHomomorphism( Gd8, Gs3, hd8 );
groupoid homomorphism : Gd8 -> Gs3
[ [ GroupHomomorphismByImages( d8, s3, [ (1,2,3,4), (1,3) ],
[ (), (15,20)(16,19)(17,18) ] ), [ -36, -35, -34 ], [ (), (), () ] ] ]
gap> e2; ImageElm( homd8, e2 );
[(1,3) : -8 -> -7]
[(15,20)(16,19)(17,18) : -35 -> -34]
gap> incGs3 := InclusionMappingGroupoids( Gd12, Gs3 );;
gap> ihomd8 := homd8 * incGs3;;
gap> IsBijectiveOnObjects( ihomd8 );
false
gap> Display( ihomd8 );
groupoid mapping: [ Gd8 ] -> [ Gd12 ]
root homomorphism: [ [ (1,2,3,4), (1,3) ], [ (), (15,20)(16,19)(17,18) ] ]
images of objects: [ -36, -35, -34 ]
images of rays: [ [() : -36 -> -36], [() : -36 -> -35], [() : -36 -> -34] ]
gap> e2; ImageElm( homd8, e2 );
[(1,3) : -8 -> -7]
[(15,20)(16,19)(17,18) : -35 -> -36]
gap> c6d := Subgroup( d12, [ (15,16,17,18,19,20) ] );;
gap> rays := [ (), (16,20)(17,19), (15,17)(18,20), (15,19)(16,18) ];;
gap> Gc6d := SubgroupoidWithRays( Gd12, c6d, rays );
single piece groupoid with rays: < Group( [ (15,16,17,18,19,20) ] ),
[ -37, -36, -35, -34 ], [ (), (16,20)(17,19), (15,17)(18,20), (15,19)(16,18)
] >
gap> iso1 := IsomorphismNewObjects( Gd12, [-7,-6,-5,-4] );
groupoid homomorphism :
[ [ IdentityMapping( d12 ), [ -7, -6, -5, -4 ], [ (), (), (), () ] ] ]
gap> iso2 := IsomorphismStandardGroupoid( Gc6d, [-7,-6,-5,-4] );
groupoid homomorphism :
[ [ IdentityMapping( Group( [ (15,16,17,18,19,20) ] ) ), [ -7, -6, -5, -4 ],
[ (), (), (), () ] ] ]



#### 5.2 Homomorphisms to a connected groupoid

##### 5.2-1 HomomorphismToSinglePiece
 ‣ HomomorphismToSinglePiece( src, rng, pieces ) ( operation )

When G is made up of two or more pieces, all of which get mapped to a connected groupoid, we have a homomorphism to a single piece. The third input parameter in this case is a list of the PieceImages of the individual homomorphisms from the single pieces. See section 3.1 for the corresponding operation on homomorphisms of magmas with objects.

In the following example the source V3 of homV3 has three pieces, and one of the component homomorphisms is an IdentityMapping .


gap> hc6 := GroupHomomorphismByImages( c6, s3,
>            [(5,6,7)(8,9)], [(15,16)(17,20)(18,19)] );;
gap> Fs3 := FullSubgroupoid( Gs3, [ -35 ] );;
gap> SetName( Fs3, "Fs3" );
gap> homc6 := GroupoidHomomorphism( Gc6, Fs3, hc6 );;
gap> incFs3 := InclusionMappingGroupoids( Gs3, Fs3 );;
gap> ihomc6 := homc6 * incFs3;
groupoid homomorphism : Gc6 -> Gs3
[ [ GroupHomomorphismByImages( c6, s3, [ (5,6,7)(8,9) ],
[ (15,16)(17,20)(18,19) ] ), [ -35 ], [ () ] ] ]
gap> idGs3 := IdentityMapping( Gs3 );;
gap> V3 := ReplaceOnePieceInUnion( U3, 1, Gs3 );
groupoid with 3 pieces:
[ Gs3, Gd8, Gc6 ]
gap> images3 := [ PieceImages( idGs3 )[1],
>                 PieceImages( homd8 )[1],
>                 PieceImages( ihomc6 )[1] ];;
gap> homV3 := HomomorphismToSinglePiece( V3, Gs3, images3 );;
gap> Display( homV3 );
homomorphism to single piece magma with pieces:
(1): [ Gs3 ] -> [ Gs3 ]
magma mapping: [ [ (15,17,19)(16,18,20), (15,20)(16,19)(17,18) ],
[ (15,17,19)(16,18,20), (15,20)(16,19)(17,18) ] ]
object map: [ -36, -35, -34 ] -> [ -36, -35, -34 ]
(2): [ Gd8 ] -> [ Gs3 ]
magma mapping: [ [ (1,2,3,4), (1,3) ], [ (), (15,20)(16,19)(17,18) ] ]
object map: [ -9, -8, -7 ] -> [ -36, -35, -34 ]
(3): [ Gc6 ] -> [ Gs3 ]
magma mapping: [ [ (5,6,7)(8,9) ], [ (15,16)(17,20)(18,19) ] ]
object map: [ -6 ] -> [ -35 ]



#### 5.3 Homomorphisms to more than one piece

##### 5.3-1 HomomorphismByUnion
 ‣ HomomorphismByUnion( src, rng, homs ) ( operation )

As in section 3.3, when the range H has more than one connected component, a homomorphism is a union of homomorphisms, one for each piece.


gap> isoq8 := IsomorphismNewObjects( Gq8, [-38,-37] );
groupoid homomorphism :
[
[ IdentityMapping( q8 ), [ -38, -37 ],
[ <identity> of ..., <identity> of ... ] ] ]
gap> Gq8b := Range( isoq8 );;
gap> SetName( Gq8b, "Gq8b" );
gap> V4 := UnionOfPieces( [ V3, Gq8 ] );
groupoid with 4 pieces:
[ Gs3, Gq8, Gd8, Gc6 ]
gap> SetName( V4, "V4" );
gap> Vs3q8b := UnionOfPieces( [ Gs3, Gq8b ] );
gap> SetName( Vs3q8b, "Vs3q8b" );
gap> hom4 := HomomorphismByUnion( V4, Vs3q8b, [ homV3, isoq8 ] );;
gap> PiecesOfMapping( hom4 );
[ groupoid homomorphism : Gq8 -> Gq8b
[ [ IdentityMapping( q8 ), [ -38, -37 ],
[ <identity> of ..., <identity> of ... ] ] ],
groupoid homomorphism :
[ [ IdentityMapping( s3 ), [ -36, -35, -34 ], [ (), (), () ] ],
[ GroupHomomorphismByImages( d8, s3, [ (1,2,3,4), (1,3) ],
[ (), (15,20)(16,19)(17,18) ] ), [ -36, -35, -34 ],
[ (), (), () ] ],
[ GroupHomomorphismByImages( c6, s3, [ (5,6,7)(8,9) ],
[ (15,16)(17,20)(18,19) ] ), [ -35 ], [ () ] ] ] ]



#### 5.4 Groupoid automorphisms

##### 5.4-1 GroupoidAutomorphismByObjectPerm
 ‣ GroupoidAutomorphismByObjectPerm( gpd, imobs ) ( operation )
 ‣ GroupoidAutomorphismByGroupAuto( gpd, gpauto ) ( operation )
 ‣ GroupoidAutomorphismByRayShifts( gpd, imrays ) ( operation )

We first describe automorphisms of a groupoid G where G is the direct product of a group g and a complete graph. The automorphism group is generated by three types of automorphism:

• given a permutation π of the n objects, we define π : G -> G,~ (o_i,g,o_j) ↦ (o_π i,g,o_π j);

• given an automorphism α of the root group g, we define α : G -> G,~ (o_i,g,o_j) ↦ (o_i,α g,o_j);

• given L = [1,g_2,g_3,...,g_n] ∈ g^n we define θ_L : G -> G,~ (o_i,g,o_j) ↦ (o_i,g_i^-1gg_j,o_j) so that, in particular, for all i the rays (r_i : o_1 -> o_i) are shifted by g_i: they map to (g_ir_i : o_1 -> o_i).

Notice, at the end of the following example, that the calculated inverse inv123a of aut123 is not in fact the correct morphism. Attempts to trace the source of this bug have revealed discrepancies in other functions. As a result, a redesign of groupoid homomorphisms is planned for the next release!


gap> a4 := Subgroup( s4, [(1,2,3),(2,3,4)] );;
gap> SetName( a4, "a4" );
gap> gensa4 := GeneratorsOfGroup( a4 );;
gap> Ga4 := SubgroupoidByPieces( Gs4, [ [a4, [-15,-13,-11]] ] );
single piece groupoid: < a4, [ -15, -13, -11 ] >
gap> SetName( Ga4, "Ga4" );
gap> aut1 := GroupoidAutomorphismByObjectPerm( Ga4, [-13,-11,-15] );;
gap> Display( aut1 );
groupoid mapping: [ Ga4 ] -> [ Ga4 ]
root homomorphism: [ [ (1,2,3), (2,3,4) ], [ (1,2,3), (2,3,4) ] ]
images of objects: [ -13, -11, -15 ]
images of rays: [ [() : -13 -> -13], [() : -13 -> -11], [() : -13 -> -15] ]
gap> h2 := GroupHomomorphismByImages( a4, a4, gensa4, [(2,3,4), (1,3,4)] );;
gap> aut2 := GroupoidAutomorphismByGroupAuto( Ga4, h2 );;
gap> Display( aut2 );
groupoid mapping: [ Ga4 ] -> [ Ga4 ]
root homomorphism: [ [ (1,2,3), (2,3,4) ], [ (2,3,4), (1,3,4) ] ]
images of objects: [ -15, -13, -11 ]
images of rays: [ [() : -15 -> -15], [() : -15 -> -13], [() : -15 -> -11] ]
gap> im3 := [(), (1,3,2), (2,4,3)];;
gap> aut3 := GroupoidAutomorphismByRayShifts( Ga4, im3 );;
gap> Display( aut3 );
groupoid mapping: [ Ga4 ] -> [ Ga4 ]
root homomorphism: [ [ (1,2,3), (2,3,4) ], [ (1,2,3), (2,3,4) ] ]
images of objects: [ -15, -13, -11 ]
images of rays: [ [() : -15 -> -15], [(1,3,2) : -15 -> -13],
[(2,4,3) : -15 -> -11] ]
gap> aut123 := aut1*aut2*aut3;;
gap> Display( aut123 );
groupoid mapping: [ Ga4 ] -> [ Ga4 ]
root homomorphism: [ [ (1,2,3), (2,3,4) ], [ (2,3,4), (1,3,4) ] ]
images of objects: [ -13, -11, -15 ]
images of rays: [ [() : -13 -> -13], [(1,4,3) : -13 -> -11],
[(1,2,3) : -13 -> -15] ]
gap> inv123a := InverseGeneralMapping( aut123 );;
gap> Display( inv123a );
groupoid mapping: [ Ga4 ] -> [ Ga4 ]
root homomorphism: [ [ (1,2,3), (2,3,4) ], [ (1,2,4), (1,3,4) ] ]
images of objects: [ -11, -15, -13 ]
images of rays: [ [() : -11 -> -11], [(1,2,4) : -11 -> -15],
[(1,3,4) : -11 -> -13] ]
gap> inv1 := InverseGeneralMapping( aut1 );;
gap> inv2 := InverseGeneralMapping( aut2 );;
gap> inv3 := InverseGeneralMapping( aut3 );;
gap> inv123b := inv3*inv2*inv1;;
gap> Display( inv123b );
groupoid mapping: [ Ga4 ] -> [ Ga4 ]
root homomorphism: [ [ (1,2,3), (2,3,4) ], [ (1,2,4), (1,2,3) ] ]
images of objects: [ -11, -15, -13 ]
images of rays: [ [() : -11 -> -11], [(1,2,4) : -11 -> -15],
[(1,2,3) : -11 -> -13] ]
gap> ok := inv123a = inv123b;
false



##### 5.4-2 Automorphisms of a groupoid with rays

If S is a wide subgroupoid with rays of a standard groupoid G then an automorphism α of G may map S to a different subgroupoid. When α is a GroupoidAutomorphismByObjectPerm, then it restricts to an automorphism of S provided the objects in each orbit have the same ray elements.

This subsection needs to be expanded and examples added.

##### 5.4-3 AutomorphismGroupOfGroupoid
 ‣ AutomorphismGroupOfGroupoid( gpd ) ( operation )
 ‣ NiceObjectAutoGroupGroupoid( gpd, aut ) ( operation )

The AutomorphismGroup of G is isomorphic to the quotient of S_n × A × g^n by a subgroup isomorphic to g, where A is the automorphism group of g and S_n is the symmetric group on the n objects. This is one of the main topics in [AW10].

The function NiceObjectAutoGroupGroupoid takes a groupoid and a subgroup of its automorphism group and retuns a nice monomorphism from this automorphism group to a pc-group, if one is available. The current implementation is experimental. Note that ImageElm at present only works on generating elements.


gap> AGa4 := AutomorphismGroupOfGroupoid( Ga4 );
<group with 8 generators>
gap> Print( GeneratorsOfGroup( AGa4 ), "\n" );
[ groupoid homomorphism : Ga4 -> Ga4
[ [ ConjugatorAutomorphism( a4, (2,3,4) ), [ -15, -13, -11 ],
[ (), (), () ] ] ], groupoid homomorphism : Ga4 -> Ga4
[ [ ConjugatorAutomorphism( a4, (1,4,2,3) ), [ -15, -13, -11 ],
[ (), (), () ] ] ], groupoid homomorphism : Ga4 -> Ga4
[ [ GroupHomomorphismByImages( a4, a4, [ (1,2,3), (2,3,4) ],
[ (1,2,3), (2,3,4) ] ), [ -13, -11, -15 ], [ (), (), () ] ] ],
groupoid homomorphism : Ga4 -> Ga4
[ [ GroupHomomorphismByImages( a4, a4, [ (1,2,3), (2,3,4) ],
[ (1,2,3), (2,3,4) ] ), [ -13, -15, -11 ], [ (), (), () ] ] ],
groupoid homomorphism : Ga4 -> Ga4
[ [ IdentityMapping( a4 ), [ -15, -13, -11 ], [ (), (1,2,3), () ] ] ],
groupoid homomorphism : Ga4 -> Ga4
[ [ IdentityMapping( a4 ), [ -15, -13, -11 ], [ (), (2,3,4), () ] ] ],
groupoid homomorphism : Ga4 -> Ga4
[ [ IdentityMapping( a4 ), [ -15, -13, -11 ], [ (), (), (1,2,3) ] ] ],
groupoid homomorphism : Ga4 -> Ga4
[ [ IdentityMapping( a4 ), [ -15, -13, -11 ], [ (), (), (2,3,4) ] ] ] ]
gap> NGa4 := NiceObject( AGa4 );
Group([ f6, f3, f11*f12, f12, f2, f1, f4*f9, f4^2, f5*f9*f10*f11*f12, f5^2 ])
gap> MGa4 := NiceMonomorphism( AGa4 );;
gap> Size( AGa4 );
20736
gap> SetName( AGa4, "AGa4" );
gap> SetName( NGa4, "NGa4" );
gap> Print( Image( MGa4 ), "\n" );
Group( [ f4*f5*f6, f3*f9*f10*f11, f2, f1*f2, f5*f11, f5^2, f4*f9, f4^2 ] )
gap> ##  Now do some tests!
gap> mgi := MappingGeneratorsImages( MGa4 );;
gap> autgen := mgi[1];;
gap> pcgen := mgi[2];;
gap> ngen := Length( autgen );;
gap> ForAll( [1..ngen], i -> Order(autgen[i]) = Order(pcgen[i]) );
true



##### 5.4-4 GroupoidAutomorphismByGroupAutos
 ‣ GroupoidAutomorphismByGroupAutos( gpd, auts ) ( operation )

Homogeneous, discrete groupoids are the second type of groupoid for which a method is provided for AutomorphismGroupOfGroupoid. This is used in the XMod package for constructing crossed modules of groupoids. The two types of generating automorphism are GroupoidAutomorphismByGroupAutos, which requires a list of group automorphisms, one for each object group, and GroupoidAutomorphismByObjectPerm, which permutes the objects.


gap> Hs3 := HomogeneousDiscreteGroupoid( s3, [ -13..-10] );
homogeneous, discrete groupoid: < s3, [ -13 .. -10 ] >
gap> aut4 := GroupoidAutomorphismByObjectPerm( Hs3, [-12,-10,-11,-13] );
groupoid homomorphism : morphism from a homogeneous discrete groupoid:
[ -13, -12, -11, -10 ] -> [ -12, -10, -11, -13 ]
object homomorphisms:
IdentityMapping( s3 )
IdentityMapping( s3 )
IdentityMapping( s3 )
IdentityMapping( s3 )
gap> gens3 := GeneratorsOfGroup( s3 );;
gap> g1 := gens3[1];;
gap> g2 := gens3[2];;
gap> b1 := GroupHomomorphismByImages( s3, s3, gens3, [ g1, g2^g1 ] );;
gap> b2 := GroupHomomorphismByImages( s3, s3, gens3, [ g1^g2, g2 ] );;
gap> b3 := GroupHomomorphismByImages( s3, s3, gens3, [ g1^g2, g2^(g1*g2) ] );;
gap> b4 := GroupHomomorphismByImages( s3, s3, gens3, [ g1^(g2*g1), g2^g1 ] );;
gap> aut5 := GroupoidAutomorphismByGroupAutos( Hs3, [b1,b2,b3,b4] );
groupoid homomorphism : morphism from a homogeneous discrete groupoid:
[ -13, -12, -11, -10 ] -> [ -13, -12, -11, -10 ]
object homomorphisms:
GroupHomomorphismByImages( s3, s3,
[ (15,17,19)(16,18,20), (15,20)(16,19)(17,18) ],
[ (15,17,19)(16,18,20), (15,18)(16,17)(19,20) ] )
GroupHomomorphismByImages( s3, s3,
[ (15,17,19)(16,18,20), (15,20)(16,19)(17,18) ],
[ (15,19,17)(16,20,18), (15,20)(16,19)(17,18) ] )
GroupHomomorphismByImages( s3, s3,
[ (15,17,19)(16,18,20), (15,20)(16,19)(17,18) ],
[ (15,19,17)(16,20,18), (15,16)(17,20)(18,19) ] )
GroupHomomorphismByImages( s3, s3,
[ (15,17,19)(16,18,20), (15,20)(16,19)(17,18) ],
[ (15,19,17)(16,20,18), (15,18)(16,17)(19,20) ] )
gap> AHs3 := AutomorphismGroupOfGroupoid( Hs3 );
<group of size 31104 with 4 generators>
gap> GeneratorsOfGroup( AHs3 )[2];
groupoid homomorphism : morphism from a homogeneous discrete groupoid:
[ -13, -12, -11, -10 ] -> [ -13, -12, -11, -10 ]
object homomorphisms:
ConjugatorAutomorphism( s3, (15,19,17)(16,20,18) )
IdentityMapping( s3 )
IdentityMapping( s3 )
IdentityMapping( s3 )



##### 5.4-5 RootGroupHomomorphism
 ‣ RootGroupHomomorphism( gpdhom ) ( attribute )
 ‣ ObjectGroupHomomorphism( gpdhom, obj ) ( operation )

A homomorphism from a single piece groupoid has one further attribute, namely RootGroupHomomorphism. This is the group homomorphism from the root group of the source to the object group at the image object in the range. Similarly, the group homomorphism from an object group of the source to the object group at the image object in the range is given by ObjectGroupHomomorphism.


gap> RootGroupHomomorphism( aut123 );
[ (1,2,3), (2,3,4) ] -> [ (2,3,4), (1,3,4) ]
gap> ObjectGroupHomomorphism( aut123, -13 );
[ (1,2,3), (2,3,4) ] -> [ (1,3,2), (1,3,4) ]


Goto Chapter: Top 1 2 3 4 5 6 7 8 Bib Ind

generated by GAPDoc2HTML