3.1. Groups by generators

Every finite group is isomorphic to some subgroup of a symmetric group of permutations (Cayley theorem). Hence, provided we can find a permutation representation, working with groups of permutations is generic.

Groups of permutations can be extremely large. The order (number of elements) of the group of permutations of n points is n!. In general we will be interested in (still very large) subgroups of a given . For example, the number of permutations of the 48 moving squares of a Rubik's cube is

In[67]:=

Out[67]=

On the other hand, the number of allowed permutations of a "clean" cube (forming a subgroup) turns out to be, as we will see below,

In[68]:=

Out[68]=

However we can describe the whole subgroup with just six permutations, corresponding to each rotation of the six faces of the cube. The subgroup can be constructed by repeated multiplication of the six "generators". We shall describe groups using generating sets, expressions with head GenSet where the elements are the generators. By convention, the identity permutation never belongs to a generating set. For example the group can be generated with just 2 permutations using Diminos's algorithm:

In[69]:=

Out[69]=

And actually any can be generated with just 2 permutations. For example :

In[70]:=

Out[70]=

A group generated by a single permutation is called a cyclic group:

In[71]:=

Out[71]=

We can form left and right cosets:

In[72]:=

Out[72]=

In[73]:=

Out[73]=

If the permutation already belongs to the group, the coset is actually the original group:

In[74]:=

Out[74]=

GenSet                Head for a generating set
Group                Head for a group of permutations
Coset                Head for a coset
Dimino                Algorithm to construct a group of permutations from one of its generating sets

Generating Sets.

Created by Mathematica  (May 16, 2008)