Given a normal subgroup H of a (large, finite permutation) group G, knowing a set of generators for each of H and G, how to find a subgroup K of G that is isomorphic to G/H? (Using Mathematica.)
3 Answers
$\begingroup$
$\endgroup$
10
The following is a hacky way of doing it for finite groups only:
quotientGroup[g_, h_] :=
RightCosetRepresentative[h, #] & /@ GroupElements[g] //
DeleteDuplicates
answered Aug 31, 2015 at 12:35
-
$\begingroup$ It's been along time since my group theory days. This generates the factor group; is it necessarily isomorphic to a subgroup of the original group? $\endgroup$– marchCommented Aug 31, 2015 at 15:16
-
$\begingroup$ @march If it's not, then the OP is asking for something which doesn't exist. It is indeed not always possible: consider the quaternion group $Q_8$ with generators $\langle i, j, k \rangle$ quotiented by the normal subgroup $\{1, -1\}$. This is isomorphic to $V_4$, which is not a subgroup of the quaternion group because any single non-$\pm 1$ element generates a cyclic 4-group. $\endgroup$ Commented Aug 31, 2015 at 15:21
-
$\begingroup$ Good, thanks. That's vaguely what I remembered. I suppose one could directly check whether or not the output of your code is a subset (and therefore necessarily a subgroup) of the original group (by using
SubsetQ), which would completely answer OP's question. $\endgroup$– marchCommented Aug 31, 2015 at 15:25 -
$\begingroup$ In the Q8 example, my code results in a group of order 384 as the "factor group". I'm decidedly confused. $\endgroup$ Commented Aug 31, 2015 at 15:28
-
2$\begingroup$ Upshot: Mathematica makes it hard to do group theory. $\endgroup$ Commented Aug 31, 2015 at 15:52
$\begingroup$
$\endgroup$
Extending Patrick Stevens answer and modifying it somewhat. As an example, I'll use the Quaternions {1, -1, i, -i, j, -j, k, -k} (per our discussion in the comments to his answer) and factor by the normal subgroup {-1, 1}.
Warning: if the groups are too big, the following calculations will probably take too much time.
To extract a permutation-group representation of the group, we do
q = PermutationCycles /@ FiniteGroupData["Quaternion", "PermutationRepresentation"] // Sort
(* {Cycles[{}], Cycles[{{1, 2, 5, 6}, {3, 4, 7, 8}}]
, Cycles[{{1, 3, 5, 7}, {2, 8, 6, 4}}]
, Cycles[{{1, 4, 5, 8}, {2, 3, 6, 7}}]
, Cycles[{{1, 6, 5, 2}, {3, 8, 7, 4}}]
, Cycles[{{1, 7, 5, 3}, {2, 4, 6, 8}}]
, Cycles[{{1, 8, 5, 4}, {2, 7, 6, 3}}]
, Cycles[{{1, 5}, {2, 6}, {3, 7}, {4, 8}}]} *)
We can verify that this set is closed under group multiplication by doing
q === Sort@Union@Flatten@Outer[PermutationProduct, q, q]
(* True *)
The subgroup {-1, 1} can be picked out using
h = {First@q, Last@q}
(* {Cycles[{}], Cycles[{{1, 5}, {2, 6}, {3, 7}, {4, 8}}]} *)
We construct the right-cosets of h using
cosets = Sort /@ Outer[PermutationProduct, q, h] // DeleteDuplicates;
cosets // TableForm
(* Cycles[{}] Cycles[{{1,5},{2,6},{3,7},{4,8}}]
Cycles[{{1,2,5,6},{3,4,7,8}}] Cycles[{{1,6,5,2},{3,8,7,4}}]
Cycles[{{1,3,5,7},{2,8,6,4}}] Cycles[{{1,7,5,3},{2,4,6,8}}]
Cycles[{{1,4,5,8},{2,3,6,7}}] Cycles[{{1,8,5,4},{2,7,6,3}}] *)
and we will use
cosetReps = cosets[[All, 1]]
(the first column above) as our set of right-coset representatives.
Finally, we construct a (clunky) multiplication for cosets via
factorGroupMultiply[elements__List, cosetReps_] /; SubsetQ[cosetsReps, elements] :=
First@@Select[cosets, MemberQ[#, PermutationProduct @@ elements] &]
(Pre-MMA-v.10, you can use a (again clunky) homebrew subsetQ,
subsetQ[list1_, list2_] := Sort@Intersection[list1, list2] === Sort@Union@list2
which is not well, tested, but should work.) This multiplication function will accept members of cosetReps, multiply them using PermutationProduct, find in which coset the result lives, then return the corresponding coset representative.
To visualize the resulting group, let's form the Cayley table:
factorGroupCayley = Outer[factorGroupMultiply[{##}, cosetReps] &, cosetReps, cosetReps];
factorGroupCayley /. Thread[cosetReps -> {1, 2, 3, 4}] // TableForm
(* 1 2 3 4
2 1 4 3
3 4 1 2
4 3 2 1 *)
Finally, we can decide whether or not this group is isomorphic to a subgroup of the original group by extracting the subgroup data for the group:
subgroups = FiniteGroupData["Quaternion", "Subgroups"]
(* {"Trivial", {"CyclicGroup", 2}, {"CyclicGroup", 4}, "Quaternion"} *)
The only subgroup of order 4 is cyclic, and the Cayley table above is clearly not the Cayley table of a cyclic group. In general, we might go through the process of finding the Cayley tables for each of the subgroups using
subGroupCayleyTables = FiniteGroupData[#, "MultiplicationTable"] & /@ subgroups;
$\begingroup$
$\endgroup$
Thanks Patrick and march for your ideas about looking at the quaternion group.
FiniteGroupData["Quaternion", "Subgroups"]
{"Trivial", {"CyclicGroup", 2}, {"CyclicGroup", 4}, "Quaternion"}.
The quotient group march mentions is clearly not cyclic but does have order 4, and there are only 2 of those, and the other is not a subgroup of the quaternion group.
FiniteGroupData[4]
{{"CyclicGroup", 4}, {"AbelianGroup", {2, 2}}}.
This quotient group goes by several names.
FiniteGroupData[{"AbelianGroup", {2, 2}}, "IsomorphicGroups"]
{"Vierergruppe", {4, 2}, {"CrystallographicPointGroup", 5}, {"CrystallographicPointGroup", 6}, {"CrystallographicPointGroup", 7}, {"CyclicGroupUnits", 8}, {"CyclicGroupUnits", 12}, {"DihedralGroup", 2}}.
So the answer to my question is that, generally speaking, there isn't necessarily a subgroup isomorphic to a quotient group. I have learned a lot talking with you.
GroupElements[group]returns the list of all elements ofgroup." I agree that it's a horrible way to do it. $\endgroup$