Permutation Groups

Groups admit many different representations. In particular, all finite groups can be represented as permutation groups, that is, they are always isomorphic to a subgroup of the symmetric group of automorphisms of a set of elements (Cayley's theorem). Highly efficient techniques for manipulation of permutation groups have been developed during the last 40 years, which allow the manipulation of very large groups in a computer.
Mathematica provides a collection of commands and algorithms that can handle permutation groups of moderate degree, in the range of a few thousand, hence working with groups of permutations with more than elements.

This tutorial introduces some basic algorithms for computing with finite permutation groups, specified by a list of generating permutations given in disjoint cyclic form. A separate tutorial "Permutations" explains how to work with permutations in cyclic form.

Generating Sets

A simple and compact way of specifying a group is by giving a set of elements whose repeated product produces the whole group. These are then called generators of the group and the set of elements is referred to as a generating set. This is a powerful and general method to specify a finite group, though for large groups it might be difficult to extract information from them about the group.

PermutationGrouphead for a permutation group defined by generators
GroupElementslist of elements of a group
GroupMultiplicationTabletable with all multiplications of pairs of elements of a group
CayleyGraphgraph of generator links between elements of a group

Group representations.

Take two permutations and construct the group generated by them.
In[1]:=
Click for copyable input
This is the list of all permutations in the group.
In[4]:=
Click for copyable input
Out[4]=
In[5]:=
Click for copyable input
Out[5]=
Both generators fix point 2, thus so do all permutations in the group. This generated group is isomorphic to the symmetric group on the set , with permutations.
In[6]:=
Click for copyable input
Out[6]=
In[7]:=
Click for copyable input
Out[7]=

For small groups, it is possible to construct better representations of a group. They are the Cayley multiplication table and Cayley graph, the latter representing mixed information about both the whole group and the generating set being used.

For small groups, all products can be represented using a Cayley multiplication table.
In[8]:=
Click for copyable input
Out[8]//TableForm=
Each row and each column is itself a permutation of the numbers 1-24. The array is symmetric if and only if the group is Abelian. The group is not Abelian.
In[9]:=
Click for copyable input
Out[9]=
In[10]:=
Click for copyable input
Out[10]=
You can also use a Cayley graph. Multiplication by permutation is represented in red and by in blue.
In[11]:=
Click for copyable input
Out[11]=
It is clear in the graph that the first generator (in red) has order 3 and the second one (in blue) has order 2.
In[12]:=
Click for copyable input
Out[12]=
Any closed loop in the graph represents a relation giving the identity. For example, the loop corresponds to the following.
In[13]:=
Click for copyable input
Out[13]=
In other words, a permutation of order 4 has been found.
In[14]:=
Click for copyable input
Out[14]=

Orbits and Stabilizers

Given any generating set of a permutation group acting on a set of points, it is possible to find which other points can be related with a given point. This is called the orbit of that point.

GroupOrbitscompute orbits of points under a group

Orbit computation.

Take two new permutations and form a generating set with them.
In[15]:=
Click for copyable input
This is the orbit of point 3. Orbits are given with points sorted lexicographically.
In[18]:=
Click for copyable input
Out[18]=
Each of the points in the orbit uniquely identifies the same orbit.
In[19]:=
Click for copyable input
Out[19]=

Points cannot belong to two different orbits and hence orbits partition the set of points on which the group acts.

In this example the maximum point of the support is 30.
In[20]:=
Click for copyable input
Out[20]=
Hence, the orbits partition the range of the first 30 points.
In[21]:=
Click for copyable input
Out[21]=
Orbits can be selected by supplying more points.
In[22]:=
Click for copyable input
Out[22]=
If a larger range is partitioned, all other points are stable.
In[23]:=
Click for copyable input
Out[23]=
Orbits can be computed efficiently, and hence it is possible to work with permutations of large support.
Take a group generated by two random permutations of equal large degree.
In[24]:=
Click for copyable input
In most cases the group acts transitively, with a single orbit.
In[25]:=
Click for copyable input
Out[25]=
Now take two generators of very different support length.
In[26]:=
Click for copyable input
Then usually there is still one large orbit, but not of maximal length.
In[27]:=
Click for copyable input
Out[27]=

Using more general actions it is possible to form other types of orbits, like conjugacy classes.

This is the conjugacy class of a permutation in the symmetric group.
In[28]:=
Click for copyable input
Out[28]=

Complementary to the information given by orbits, describing how points move, it is also possible to compute stabilizers, namely the subgroups of elements fixing one or several points.

GroupStabilizersubgroup of elements fixing one or several points

Computation of stabilizers.

Take this group again.
In[29]:=
Click for copyable input
Out[29]=
This is the subgroup of permutations fixing point 3. The cyclic notation shows that none of its generators moves point 3.
In[30]:=
Click for copyable input
Out[30]=
Recall the orbit of point 3 under this group has length 18.
In[31]:=
Click for copyable input
Out[31]=
In[32]:=
Click for copyable input
Out[32]=
By the orbit stabilizer theorem, that must be also the quotient between the group orders.
In[33]:=
Click for copyable input
Out[33]=

Strong Generating Set Representation

For larger permutation groups it becomes increasingly infeasible to list or draw all their elements. In such cases it is necessary to resort to alternative methods that can infer information about a group from a generating set of the group without actually computing all its permutations. The key ideas were developed in the late 1960s, and are based on the construction of a new equivalent generating set for the same group, but from which it is easy to form a hierarchy of subgroups that allow fast manipulation of the full group. This special type of generating set is called a strong generating set.

GroupOrdernumber of elements of a group
GroupElementQtest whether a permutation belongs to a given group

Basic functionality with strong generating set representations.

Take this group generated by two permutations with support .
In[34]:=
Click for copyable input
Orbit computations can be done directly from standard generators. However, in order to compute the group order, Mathematica internally computes strong generators for the group.
In[37]:=
Click for copyable input
Out[37]=
That representation is stored, to avoid recomputing it for the same original set of generators.
In[38]:=
Click for copyable input
Out[38]=
Now it is possible to do things like testing for membership.
In[39]:=
Click for copyable input
Out[39]=
In[40]:=
Click for copyable input
Out[40]=
Any product of generators must belong to the group.
In[41]:=
Click for copyable input
Out[41]=
In[42]:=
Click for copyable input
Out[42]=

Now return to the properties of a strong generating set. Strong generators are defined with respect to a base: this is an ordered subset of points of the domain of action of the group, such that the identity is the only element that fixes them all. That implies that knowing the images of the points in a base under a permutation uniquely identifies that permutation. Groups for which a short base is known can be manipulated highly efficiently. The base defines a very useful hierarchy of stabilizer subgroups, known as the stabilizer chain, which plays a central role in the manipulation of permutation groups, very much like the Gauss-elimination hierarchy of vector spaces in linear algebra. Finally, the condition that characterizes a set of generators as being strong with respect to a base is that it contains generating subsets for all subgroups in the corresponding stabilizer chain.

GroupStabilizerChainchain of stabilizer subgroups of a permutation group
GroupActionBaseoption specifying a base of a group

Stabilizer chain, base, and strong generators.

This is a stabilizer chain of the previous group, with respect to a base automatically chosen by Mathematica.
In[43]:=
Click for copyable input
Out[43]=
These are the orders of the subgroups in the stabilizer chain.
In[44]:=
Click for copyable input
Out[44]=
The base and strong generators of the chain can be extracted as follows.
In[45]:=
Click for copyable input
Out[45]=
In[46]:=
Click for copyable input
Out[46]=
Those are still generators for the original group.
In[47]:=
Click for copyable input
Out[47]=
The second group in the chain is the stabilizer of 1, a subgroup of order 253.
In[48]:=
Click for copyable input
Out[48]=
In[49]:=
Click for copyable input
Out[49]=
The stabilizer subgroup has two permutations less, precisely those moving point 1.
In[50]:=
Click for copyable input
Out[50]=
The other permutations in the strong generating set do not move point 1.
In[51]:=
Click for copyable input
Out[51]=
You can repeat the stabilization for the first two points in the base.
In[52]:=
Click for copyable input
Out[52]=
In[53]:=
Click for copyable input
Out[53]=
Finally, the third stabilizer is the trivial group, because it is the stabilizer of the full base.
In[54]:=
Click for copyable input
Out[54]=
Check Lagrange's theorem by showing that the size of a subgroup always divides that of the group.
In[55]:=
Click for copyable input
Out[55]=
In[56]:=
Click for copyable input
Out[56]=
The product of those numbers is the size of the full original group.
In[57]:=
Click for copyable input
Out[57]=
In[58]:=
Click for copyable input
Out[58]=
The option GroupActionBase allows specifying an alternative base. If it is not a true base, Mathematica will complete it with additional points.
In[59]:=
Click for copyable input
Out[59]=

Example: The Rubik Group

One of the most famous permutation groups is that associated with the rotations of a Rubik cube. In the following diagram moving facelets are numbered from 1 to 48. The central facelets do not move, and define six respective basic rotations.

These are the six basic rotations.
In[60]:=
Click for copyable input
This is the number of elements in that group.
In[67]:=
Click for copyable input
Out[67]=
Internally the following chain of stabilizers has been constructed. The number of permutations that fix the corresponding list of points is indicated. The last line gives a base of the group, because only one permutation (the identity) fixes the given 18 points.
In[68]:=
Click for copyable input
In[69]:=
Click for copyable input
Out[69]=
A set of strong generators is given by the group in the first line of the chain.
In[70]:=
Click for copyable input
Out[70]=
Now you can test membership of some moves. For example, swapping two neighbor edge facelets is not allowed.
In[71]:=
Click for copyable input
Out[71]=
But the simultaneous switching of two of those is allowed.
In[72]:=
Click for copyable input
Out[72]=
This is the superflip move, which switches all those pairs simultaneously.
In[73]:=
Click for copyable input
Out[73]=
In[74]:=
Click for copyable input
Out[74]=

Other Examples

These are two examples of groups of larger support, but with very short bases.

The largest symplectic group given in the ATLAS of Finite Groups is , represented as permutations on 496 points.
In[75]:=
Click for copyable input
In[78]:=
Click for copyable input
Out[78]=
In[79]:=
Click for copyable input
Out[79]=
These are the orders of the subgroups in its stabilizer chain.
In[80]:=
Click for copyable input
Out[80]=
This is the exceptional twisted group , represented with permutations on 819 points.
In[81]:=
Click for copyable input
In[84]:=
Click for copyable input
Out[84]=
It also admits a very short base.
In[85]:=
Click for copyable input
Out[85]=
New to Mathematica? Find your learning path »
Have a question? Ask support »