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

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

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.

## Isomorphisms

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 *h*_{g} in *H* such that for all *s* in *S*, (*g* o *f*)(*s*) = (*f* o *h*_{g})(*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 *V*_{4}.

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