In mathematics, a permutation group is a group G whose elements are permutations of a given set M, and whose 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).
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.
| Table of contents |
|
2 Isomorphisms 3 See Also |
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}:
The group of all permutations of a set of n elements is the symmetric group written Sn; if M is any finite or infinite set, then the group of all permutations of M is often written as Sym(M).
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.
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 action on G as a set; this is the content of Cayley's Theorem.
If G and H are two permutation groups on the same set S, then we say that G and H are isomorphic as permutation groups if there exists a bijective map f : S → S such that r |-> 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 s in S, (g o f)(s) = (f o hg)(s). 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).Examples
G forms a group, since aa = bb = e, ba = ab, and baba = e. So (G,M) forms a permutation group.Isomorphisms
