8. Canonical representative of a right coset

Given a permutation g and a group S of permutations we can construct the right coset S.g, which is not a group in general. Here we want to choose a canonical representant of S.g. `Canonical´ means the first according to a given ordering of the points of the Ω set.  That ordering is defined through the base of the SGS.

Suppose a group generated by two permutations. We construct a SGS. Note that we can give the first points of the base of the SGS or not:

In[267]:=

Out[267]=

In[268]:=

Out[268]=

The group generated by those SGSs has order 8 and therefore there are 90 cosets of that group in S6:

In[269]:=

Out[269]=

In[270]:=

Out[270]=

In[271]:=

Out[271]=

Now we take one permutation which does not belong to the group and construct the corresponding right coset, sorting the permutations:

In[272]:=

In[273]:=

Out[273]=

In[274]:=

Out[274]=

In[275]:=

Out[275]=

The sorting is only evident in Images notation. The first permutation is our canonical representative:

In[276]:=

Out[276]=

It can also be computed using Portugal's algorithms.

In[277]:=

Out[277]=

There is an additional argument which assigns special priority to some points ("free slots" below). The default is Range[deg], assigning that special priority to all points ("all slots are free"):

In[278]:=

Out[278]=

Together with the canonical representative, the algorithm returns a SGS for the stabilizer of the special points, and the new positions of the special points under the change of coset element (performed by the permutation h in G taking the old permutation to the new permutation):

In[279]:=

Out[279]=

In[280]:=

Out[280]=

In[281]:=

Out[281]=

In[282]:=

It is important to stress that PermSort uses by default the trivial ordering of points {1, 2, 3,...}, which in this case coincide with the base of SGS1. However, if we want to use other bases, then we need a second argument:

In[283]:=

Out[283]=

In[284]:=

Out[284]=

PermSort with a base uses the ordering given by PermOrderedQ. In any case the identity must always be the least permutation. Here we check that all permutations of degree four with all bases come after the identity:

In[285]:=

Out[285]=

It is possible to follow the internals of CosetRepresentative using the option xPermVerbose. Note that we use the terminology of tensor computations (tensor, slots, indices, etc.):

In[286]:=

Out[286]=

RightCosetRepresentative            Compute a canonical representative of a coset

Canonicalization of free indices.

Created by Mathematica  (May 16, 2008)