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 S_n; if M is any finite or infinite set, then the group of all permutations of M is often written as Sym(M).

The application of a permutation group to the elements being permuted is called its group action; it has applications in both the study of symmetries, combinatorics and many other branches of mathematics, physics and chemistry.

The degree of a group of permutations of a finite set is the number of elements in the set.

Closure properties

As a subgroup of a symmetric group, all that is necessary for a permutation group to satisfy the group axioms is that it contain the identity permutation, the inverse permutation of each permutation it contains, and be closed under composition of its permutations. A general property of finite groups implies that a finite nonempty subset of a symmetric group is again a group if and only if it is closed under the group operation.

Examples

Permutations are often written in cyclic form^[1] 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; if the objects are denoted by a single letter or digit, commas are also dispensed with, and we have a notation such as (1 2 4).

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

• e = (1)(2)(3)(4)= (1)^[2][3]
  • This is the identity, the trivial permutation which fixes each element.
• a = (1 2)(3)(4) = (1 2)
  • This permutation interchanges 1 and 2, and fixes 3 and 4.
• b = (1)(2)(3 4) = (3 4)
  • Like the previous one, but exchanging 3 and 4, and fixing the others.
• ab = (1 2)(3 4)
  • 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 coloured 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.^[3]

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.

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

Isomorphisms

If G and H are two permutation groups on the same set X, then we say that G and H are isomorphic as permutation groups if there exists a bijective map f : X → X such that r ↦ f ⁻¹ o r o f defines a bijective map between G and H; in other words, if for each element g in G, there is a unique h_g in H such that for all x in X, (g o f)(x) = (f o h_g)(x). This is equivalent to G and H being conjugate as subgroups of Sym(X). In this case, G and H are also isomorphic as groups.

Notice that different permutation groups may well be isomorphic as abstract groups, but not as permutation groups. For instance, the permutation group on {1,2,3,4} described above is isomorphic as a group (but not as a permutation group) to {(1)(2)(3)(4), (12)(34), (13)(24), (14)(23)}. Both are isomorphic as groups to the Klein group V₄.

Transpositions, simple transpositions, inversions and sorting

A 2-cycle is known as a transposition. A simple transposition in S_n is a 2-cycle of the form (i  i + 1).

For a permutation p in S_n, a pair (i , j)∈I_n is a permutation inversion, if when i<j, we have p(i) > p(j).^[4]

Every permutation can be written as a product of simple transpositions; furthermore, the number of simple transpositions one can write a permutation p in S_n can be the number of inversions of p and if the number of inversions in p is odd or even the number of transpositions in p will also be odd or even corresponding to the oddness of p.

Notes

1. ↑ e.g. during cycle index computations
2. ↑ This is just a notation that is often used
3. ↑ 3.0 3.1 Math Circle- Berkeley: Application of Groups to Solve Rubik's Cube
4. ↑ Weisstein, Eric W. "Permutation Inversion." From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/PermutationInversion.html

See also

• Rank 3 permutation group
• Primitive group
• Oligomorphic group

References

• John D. Dixon and Brian Mortimer. Permutation Groups. Number 163 in Graduate Texts in Mathematics. Springer-Verlag, 1996.
• Akos Seress. Permutation group algorithms. Cambridge Tracts in Mathematics, 152. Cambridge University Press, Cambridge, 2003.
• Meenaxi Bhattacharjee, Dugald Macpherson, Rögnvaldur G. Möller and Peter M. Neumann. Notes on Infinite Permutation Groups. Number 1698 in Lecture Notes in Mathematics. Springer-Verlag, 1998.
• Hazewinkel, Michiel, ed. (2001), "Permutation group", Encyclopedia of Mathematics, Springer, ISBN 978-1-55608-010-4 
• Alexander Hulpke. GAP Data Library "Transitive Permutation Groups".
• Peter J. Cameron. Permutation Groups. LMS Student Text 45. Cambridge University Press, Cambridge, 1999.
• Peter J. Cameron. Oligomorphic Permutation Groups. Cambridge University Press, Cambridge, 1990.