21.23 Homomorphisms for Permutation Groups

This section describes the various homomorphisms that are treated specially for permutation groups.

GroupHomomorphisByImages( P, H, gens, imgs )

The group homomorphism of a permutation group P into another group H is handled especially by GroupHomomorphisByImages. Below we describe how the various mapping functions are implemented for such a group homomorphism ghom. The mapping functions not mentioned below are implemented by the default functions described in GroupHomomorphismByImages.

To work with ghom, a stabilizer chain for the source of ghom is computed and stored as ghom.orbit, ghom.transversal, ghom.stabilizer. For every stabilizer stab in the stabilizer chain there is a list parallel to stab.generators, which is called stab.genimages, and contains images of the generators. The stabilizer chain is computed with a random Schreier Sims algorithm, using the size of the source to know when to stop.

IsMapping( ghom )

To test if ghom is a (single valued) mapping, all Schreier generatores are computed. Each Schreier generator is then reduced along the stabilizer chain. Because the chain is complete, each one must reduce to the identity. Parallel the images of the strong generators are multiplied. If they also reduce to the identity (in the range), ghom is a function, otherwise the remainders form a normal generating set for the subgroup of images of the identity of the source.

Image( ghom, elm )

The image of an element elm can be computed by reducing the element along the stabilizer chain, and at each step multiplying the corresponding images of the strong generators.

CompositionMapping( hom, ghom )

The composition of an arbitrary group homomorphism hom and ghom the stabilizer chain of ghom is copied. On each level the images of the generators in stab.genimages are replaced by their images under hom.

OperationHomomorphism( P, Operation( P, list ) )

The operation of a permutation group P on a list list of integers is handled especially by OperationHomomorphism. (Note that list must be a union of orbits of P for Operation to work.) We call the resulting homomorphism a transitive constituent homomorphism. Below we describe how the various mapping functions are implemented for a transitive constituent homomorphism tchom. The mapping functions not mentioned below are implemented by the default functions described in OperationHomomorphism.

Image( tchom, elm )

The image of an element is computed by restricting elm to list (see RestrictedPerm) and conjugating the restricted permutation with tchom.conperm, which maps it to a permutation that operates on [1..Length(list)] instead of list.

Image( tchom, H )

The image of a subgroup H is computed as follows. First a stabilizer chain for H is computed. This stabilizer chain is such that the base starts with points in list. Then the images of the strong generators of sub form a strong generating set of the image.

PreImages( tchom, H )

The preimage of a subgroup H is computed as follows. First a stabilizer chain for the source of tchom is computed. This stabilizer chain is such that the base starts with the point in list. Then the kernel of tchom is a stabilizer in this stabilizer chain. The preimages of the strong generators for H together with the strong generators for the kernel form a strong generating set of the preimage subgroup.

OperationHomomorphism( P, Operation( P, blocks, OnSets ) )

The operation of a permutation group P on a block system blocks (see Blocks) is handled especially by OperationHomomorphism. We call the resulting homomorphism a blocks homomorphism. Below we describe how the various mapping functions are implemented for a blocks homomorphism bhom. The mapping functions not mentioned below are implemented by the default functions described in OperationHomomorphism.

Image( bhom, elm )

To compute the image of an element elm under bhom, the record for bhom contains a list bhom.reps, which contains for each point in the union of the blocks the position of this block in blocks. Then the image of an element can simply be computed by applying the element to a representative of each block and using bhom.reps to find in which block the image lies.

Image( bhom, H )
PreImage( bhom, elm ) PreImage( bhom, H )
Kernel( bhom )

The image of a subgroup, the preimage of an element, and the preimage of a subgroup are computed by rather complicated algorithms. For a description of these algorithms see But85a.

Previous Up Top Next
Index

GAP 3.4.4
April 1997