2
$\begingroup$

Background

I want to get a permutation list, so I use the SymmetricGroup(or use Permutations) to produce it when the GroupOrder is 4.

Permute[Range@4, SymmetricGroup[4]]

{{1,2,3,4},{1,2,4,3},{1,3,2,4},{1,3,4,2},{1,4,2,3},{1,4,3,2},{2,1,3,4},{2,1,4,3},{2,3,1,4},{2,3,4,1},{2,4,1,3},{2,4,3,1},{3,1,2,4},{3,1,4,2},{3,2,1,4},{3,2,4,1},{3,4,1,2},{3,4,2,1},{4,1,2,3},{4,1,3,2},{4,2,1,3},{4,2,3,1},{4,3,1,2},{4,3,2,1}}

You can use Permutations[Range@4] to get the same list. But when the GroupOrder surpass 11, my PC cannot generate such permutation list because of the insufficient RAM. So I want to split it into more part then process it respectively and combine those parts in the last work.

Question

How to split a SymmetricGroup into some PermutationGroup with smaller GroupOrder. These new PermutationGroup had better have no overlapping GroupElements and all of the PermutationGroup's GroupElements is equal to that of SymmetricGroup's.

$\endgroup$
  • $\begingroup$ What do you mean by "process it?" $\endgroup$ – Jens Jun 16 '16 at 15:56
4
$\begingroup$

A permutation group cannot be partitioned into a list of disjoint permutation groups. Note for example that every permutation group must necessarily contain the identity permutation.

But we can partition a group G into a subgroup S and cosets of S in G. For symmetric groups this is easy, because we know that if m < n the SymmetricGroup[m] is a subgroup of SymmetricGroup[n]. This allows breaking the list of n! permutations of SymmetricGroup[n] into n disjoint lists of (n-1)! permutations each.

To do this, we need to construct the list of "coset representatives":

representatives[n_Integer] := Table[Cycles[{Range[i, n]}], {i, n, 1, -1}]

and the following function to construct cosets by permutation product:

rightcoset[groupelems_List, perm_Cycles] := Thread[PermutationProduct[groupelems, perm]]

Now imagine that you already have the list of group elements of SymmetricGroup[6]:

S6 = GroupElements[SymmetricGroup[6]]

Create the seven cosets of S6 in S7 (in your application you would construct and work with one coset at a time):

S7cosets = rightcoset[S6, #] & /@ representatives[7]

The full list of elements of the group is just the joining of those lists:

S7 = Join@@ S7cosets

Check that we indeed have them all:

In[]:= Sort[S7] === Sort[GroupElements[SymmetricGroup[7]]]
Out[]= True
$\endgroup$
  • $\begingroup$ This answer help me a lot.I cost plenty of time to digest your answer,and I have consulted some books for understanding it.Thanks very very much. $\endgroup$ – yode Jun 18 '16 at 20:19
  • $\begingroup$ Would you mind to update an universal method to partition any group G into a subgroup S and cosets of S in G?such as this group,SeedRandom[1]; group=PermutationGroup[{RandomPermutation[4],RandomPermutation[5],RandomPermutation[7]}].Of course,maybe I should be post a new question for this. $\endgroup$ – yode Jun 19 '16 at 6:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.