# Permutation Groups

Generating Sets | Example: The Rubik Group |

Orbits and Stabilizers | Other Examples |

Strong Generating Set Representation |

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.

PermutationGroup | head for a permutation group defined by generators |

GroupElements | list of elements of a group |

GroupMultiplicationTable | table with all multiplications of pairs of elements of a group |

CayleyGraph | graph of generator links between elements of a group |

In[1]:= |

In[4]:= |

Out[4]= |

In[5]:= |

Out[5]= |

In[6]:= |

Out[6]= |

In[7]:= |

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.

In[8]:= |

Out[8]//TableForm= | |

In[9]:= |

Out[9]= |

In[10]:= |

Out[10]= |

In[11]:= |

Out[11]= |

In[12]:= |

Out[12]= |

In[13]:= |

Out[13]= |

In[14]:= |

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.

GroupOrbits | compute orbits of points under a group |

In[15]:= |

In[18]:= |

Out[18]= |

In[19]:= |

Out[19]= |

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

In[20]:= |

Out[20]= |

In[21]:= |

Out[21]= |

In[22]:= |

Out[22]= |

In[23]:= |

Out[23]= |

In[24]:= |

In[25]:= |

Out[25]= |

In[26]:= |

In[27]:= |

Out[27]= |

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

In[28]:= |

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.

GroupStabilizer | subgroup of elements fixing one or several points |

In[29]:= |

Out[29]= |

In[30]:= |

Out[30]= |

In[31]:= |

Out[31]= |

In[32]:= |

Out[32]= |

In[33]:= |

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*.

GroupOrder | number of elements of a group |

GroupElementQ | test whether a permutation belongs to a given group |

Basic functionality with strong generating set representations.

In[34]:= |

*Mathematica*internally computes strong generators for the group.

In[37]:= |

Out[37]= |

In[38]:= |

Out[38]= |

In[39]:= |

Out[39]= |

In[40]:= |

Out[40]= |

In[41]:= |

Out[41]= |

In[42]:= |

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.

GroupStabilizerChain | chain of stabilizer subgroups of a permutation group |

GroupActionBase | option specifying a base of a group |

Stabilizer chain, base, and strong generators.

*Mathematica*.

In[43]:= |

Out[43]= |

In[44]:= |

Out[44]= |

In[45]:= |

Out[45]= |

In[46]:= |

Out[46]= |

In[47]:= |

Out[47]= |

In[48]:= |

Out[48]= |

In[49]:= |

Out[49]= |

In[50]:= |

Out[50]= |

In[51]:= |

Out[51]= |

In[52]:= |

Out[52]= |

In[53]:= |

Out[53]= |

In[54]:= |

Out[54]= |

In[55]:= |

Out[55]= |

In[56]:= |

Out[56]= |

In[57]:= |

Out[57]= |

In[58]:= |

Out[58]= |

*Mathematica*will complete it with additional points.

In[59]:= |

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.

In[60]:= |

In[67]:= |

Out[67]= |

In[68]:= |

In[69]:= |

Out[69]= |

In[70]:= |

Out[70]= |

In[71]:= |

Out[71]= |

In[72]:= |

Out[72]= |

In[73]:= |

Out[73]= |

In[74]:= |

Out[74]= |

## Other Examples

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

*ATLAS of Finite Groups*is , represented as permutations on 496 points.

In[75]:= |

In[78]:= |

Out[78]= |

In[79]:= |

Out[79]= |

In[80]:= |

Out[80]= |

In[81]:= |

In[84]:= |

Out[84]= |

In[85]:= |

Out[85]= |