Permutation group

In mathematics, a permutation group is a group G whose elements are permutations of a given set M, and whose group operation is the composition of permutations in G (which are thought of as bijective functions from the set M to itself); the relationship is often written as (G,M). Note that the group of all permutations of a set is the symmetric group; the term permutation group is usually restricted to mean a subgroup of the symmetric group. The symmetric group of n elements is denoted by Sn; if M is any finite or infinite set, then the group of all permutations of M is often written as Sym(M).

Examples

Permutations are often written in cyclic form, so that given the set M = {1,2,3,4}, a permutation g of M with g(1) = 2, g(2) = 4, g(4) = 1 and g(3) = 3 will be written as (1,2,4)(3), or more commonly, (1,2,4) since 3 is left unchanged.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Consider the following set of permutations G of the set M = {1,2,3,4}:

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

• e = (1)(2)(3)(4)
• This is the identity, the trivial permutation which fixes each element.
• a = (12)(3)(4) = (12)
• This permutation interchanges 1 and 2, and fixes 3 and 4.
• b = (1)(2)(34) = (34)
• Like the previous one, but exchanging 3 and 4, and fixing the others.
• ab = (12)(34)
• This permutation, which is the composition of the previous two, exchanges simultaneously 1 with 2, and 3 with 4.

G forms a group, since aa = bb = e, ba = ab, and baba = e. So (G,M) forms a permutation group.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

The Rubik's Cube puzzle is another example of a permutation group. The underlying set being permuted is the colored subcubes of the whole cube. Each of the rotations of the faces of the cube is a permutation of the positions and orientations of the subcubes. Taken together, the rotations form a generating set, which in turn generates a group by composition of these rotations. The axioms of a group are easily seen to be satisfied; to invert any sequence of rotations, simply perform their opposites, in reverse order.

Related Topics:
Rubik's Cube - Generating set - Axioms of a group

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

The group of permutations on the Rubik's Cube does not form a complete symmetric group of the 20 corner and face cubelets; there are some final cube positions which cannot be achieved through the legal manipulations of the cube.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Other examples of permutation groups: the kaleidoscope puzzle and the eightfold cube.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

More generally, every group G is isomorphic to a permutation group by virtue of its action on G as a set; this is the content of Cayley's Theorem.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~