Permutation group

From Wikipedia, the free encyclopedia

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

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 and physics.

Contents

[edit] 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 subset of a finite symmetric group is again a group if and only if it is closed under the group operation.

[edit] Examples

Permutations are often written in cyclic form, e.g. during cycle index computations, 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 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 = (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.

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 permutation group by virtue of its regular action on G as a set; this is the content of Cayley's theorem.

[edit] 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 \mapsto f −1 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 hg in H such that for all x in X, (g o f)(x) = (f o hg)(x). This is equivalent to G and H being conjugate as subgroups of SX. 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 V4.

If (G,M) and (H,M) such that both G and H are isomorphic as groups to Sym(M), then (G,M) and (H,M) are isomorphic as permutation groups; thus it is appropriate to talk about the symmetric group Sym(M) (up to isomorphism).

[edit] Transpositions, simple transpositions, inversions and sorting

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

An inversion of a permutation p in Sn is a pair (i  i + 1) such that p(i) > p(i + 1). Viewing permutations as lists, an inversion expresses that the items at position i and i + 1 are out of order.

It can be shown that every permutation can be written as a product of simple transpositions; furthermore, the number of simple transpositions one can write a permutation p in Sn 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, and that it is possible to find such a product—in fact, this is what insertion sort does implicitly (instead of giving the simple transpositions as output, it applies them to the input list).

[edit] See also

[edit] 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.
  • 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.