12
$\begingroup$

I have a group:

group = PermutationGroup[{Cycles[{{1, 3, 6}, {2, 4}}], Cycles[{{6, 7}}]}];

And I have s subgroup

subgroup = PermutationGroup[{Cycles[{{6,7}}],Cycles[{{2,4}}],Cycles[{{1,7}}]}];

We can check it:

ResourceFunction["SubgroupQ"][subgroup, group]

True

So how to find all left cosets(or just the representative element in all left cosets) about subgroup in group?

$\endgroup$

3 Answers 3

15
$\begingroup$

Since two left cosets $g\cdot H$ and $h \cdot H$ satisfies $g\cdot H= h \cdot H$ is equavalent to $ h^{-1}\cdot g\in H$,we set it as the equivalence relationships and use Gather.

Gather[GroupElements[group],
   GroupElementQ[subgroup, PermutationProduct[InversePermutation[#1], #2]] &]

There are 4 cosets.

enter image description here

$\endgroup$
8
$\begingroup$

First edit

Since $b\in aH$, if and only if $aH=bH$:

Union[Sort[#, Less] &/@ Table[Table[
    PermutationProduct[e, i], {i, GroupElements[subgroup]}], {e, 
    GroupElements[group]}]]

enter image description here

The representative elements are respectively:

First /@ %

{Cycles[{}],Cycles[{{1,3}}],Cycles[{{3,6}}],Cycles[{{3,7}}]}

Ugly, but work.

Second edit (The efficiency version)

leftcosets[{}, r_] := r
leftcosets[remaineles_, r_ : {}] := 
 Module[{representative = First[remaineles], coset}, 
  leftcosets[Complement[remaineles, 
    coset = Table[PermutationProduct[representative, i], {i, 
       GroupElements[subgroup]}]], Append[r, coset]]]

It very quick. I'll use a larger group as an example:

group = PermutationGroup[{Cycles[{{1, 2, 7, 10, 5, 8}, {3, 4}, {6, 
       9}}], Cycles[{{1, 6}, {2, 4, 8, 7, 10, 9}, {3, 5}}]}];
subgroup = GroupStabilizer[group, {3}];

Performance comparsion

AbsoluteTiming[
 result1 = Gather[GroupElements[group], 
    GroupElementQ[subgroup, 
      PermutationProduct[InversePermutation[#], #2]] &];]

{17.0175, Null} ← cvgmt's method

AbsoluteTiming[result2 = leftcosets[GroupElements[group]];]

{0.133693, Null} ← my method

Equal to inspection

SortBy[Sort /@ result1, First] === SortBy[Sort /@ result2, First]

True


Third edit (just get the representative element of left cosets)

Union[InversePermutation[RightCosetRepresentative[subgroup,#]]&/@GroupElements[group]]

{Cycles[{}],Cycles[{{1,3}}],Cycles[{{3,6}}],Cycles[{{3,6,7}}]}

$\endgroup$
0
$\begingroup$

Share another elegant method to list all right cosets. The only regret is that it cannot be used to find left cosets. Because The inverse of the right coset canonical representative about $p$ is not in the same left coset with $p$:

GatherBy[GroupElements[group], RightCosetRepresentative[subgroup, #] &]
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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