11
$\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$

2 Answers 2

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$

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.