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.

RightCosetRepresentativecompute smallest group element in a coset

Computation of a canonical coset representative.

Take two permutations and the group generated by them.
In[1]:=
Click for copyable input
Out[2]=
This group partitions into 210 disjoint cosets.
In[3]:=
Click for copyable input
Out[3]=
Given any other permutation, it is possible to list the elements of its associated right coset.
In[4]:=
Click for copyable input
In[5]:=
Click for copyable input
Out[5]=
The canonical representative of the right coset is taken to be the least permutation in the order defined by images.
In[6]:=
Click for copyable input
Out[6]=
Construct the canonical representative directly, without listing the permutations in the coset.
In[7]:=
Click for copyable input
Out[7]=
Check that this also agrees with the minimum-rank permutation (in the group ) in the coset.
In[8]:=
Click for copyable input
In[9]:=
Click for copyable input
Out[9]=
In[10]:=
Click for copyable input
Out[10]=
In[11]:=
Click for copyable input
Out[11]=
For bigger groups, it is not possible to list or rank all permutations, but you can still use RightCosetRepresentative.
Take two permutations and construct the group generated by them.
In[12]:=
Click for copyable input
This is the number of cosets induced by this group on .
In[13]:=
Click for copyable input
Out[13]=
For any permutation belonging to the group itself, the canonical representative is always the identity permutation.
In[14]:=
Click for copyable input
Out[14]=
In[15]:=
Click for copyable input
Out[15]=
Now take some random permutation in .
In[16]:=
Click for copyable input
Out[16]=
This is its coset representative.
In[17]:=
Click for copyable input
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 permPermutationProduct[h,rep].
In[18]:=
Click for copyable input
Out[18]=
In[19]:=
Click for copyable input
Out[19]=

Centralizer

The centralizer of an element in a group is the subgroup of elements of that commute with .

GroupCentralizercompute the centralizer subgroup of some group element

Computation of centralizers.

Take the group.
In[20]:=
Click for copyable input
Out[21]=
Choose a permutation.
In[22]:=
Click for copyable input
This is its centralizer in the group.
In[23]:=
Click for copyable input
Out[23]=
In[24]:=
Click for copyable input
Out[24]=
Check the result by direct computation of all commutators in the group.
In[25]:=
Click for copyable input
In[26]:=
Click for copyable input
In[27]:=
Click for copyable input
Out[27]=
In[28]:=
Click for copyable input
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.

GroupSetwiseStabilizercompute the setwise stabilizer subgroup of a list of points

Computation of setwise stabilizers.

Take the group again.
In[29]:=
Click for copyable input
Out[30]=
This is the list of points to be stabilized.
In[31]:=
Click for copyable input
In[32]:=
Click for copyable input
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.
In[33]:=
Click for copyable input
Out[33]=
Compare with the (pointwise) stabilizer of the same list of elements. It only contains permutations stabilizing all elements of the list.
In[34]:=
Click for copyable input
Out[34]=
In[35]:=
Click for copyable input
Out[35]=