Group Theory Algorithms
This tutorial introduces some basic algorithms for computing with finite permutation groups, other than those introduced in
"Permutation Groups".
Coset Representatives
A subgroup
of a group
partitions the list of elements of
into disjoint subsets, called cosets of
in
, such that
is one of them and the rest are of the form
for some element
of
, with
denoting the product law. A way of identifying the coset is by selecting a representative from each coset, for example the smallest element in the coset.
Computation of a canonical coset representative.
Take two permutations and the group generated by them.
| Out[2]= |  |
This group partitions
into 210 disjoint cosets.
| Out[3]= |  |
Given any other permutation, it is possible to list the elements of its associated right coset.
| Out[5]= |  |
The canonical representative of the right coset is taken to be the least permutation in the order defined by images.
| Out[6]= |  |
Construct the canonical representative directly, without listing the permutations in the coset.
| Out[7]= |  |
Check that this also agrees with the minimum-rank permutation (in the group
) in the coset.
| Out[9]= |  |
| Out[10]= |  |
| Out[11]= |  |
Take two permutations and construct the group generated by them.
This is the number of cosets induced by this group on
.
| Out[13]= |  |
For any permutation belonging to the group itself, the canonical representative is always the identity permutation.
| Out[14]= |  |
| Out[15]= |  |
Now take some random permutation in
.
| Out[16]= |  |
This is its coset representative.
| Out[17]= |  |
Check that the representative indeed belongs to the same coset. This will be the case if there exists a permutation
h in the original group such that
perm=PermutationProduct[h, rep].
| Out[18]= |  |
| Out[19]= |  |
Centralizer
The centralizer
of an element
in a group
is the subgroup of elements of
that commute with
.
Computation of centralizers.
| Out[21]= |  |
This is its centralizer in the group.
| Out[23]= |  |
| Out[24]= |  |
Check the result by direct computation of all commutators in the group.
| Out[27]= |  |
| Out[28]= |  |
Setwise Stabilizer
The (pointwise) stabilizer of a group
is the subgroup of elements of
fixing a set of one or several points of the domain of action. This concept can be extended to the setwise stabilizer, which is the subgroup of elements either fixing those points or moving them among themselves.
Computation of setwise stabilizers.
| Out[30]= |  |
This is the list of points to be stabilized.
| Out[32]= |  |
The action of the permutations of the setwise stabilizer changes the individual elements of the list, but always to other elements of the list.
| Out[33]= |  |
Compare with the (pointwise) stabilizer of the same list of elements. It only contains permutations stabilizing all elements of the list.
| Out[34]= |  |
| Out[35]= |  |
