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. The group of all permutations of a set M is the symmetric group of M, often written as Sym. The term permutation group thus means a subgroup of the symmetric group. If then Sym is usually denoted by S_n, and may be called the symmetric group on n letters.
By Cayley's theorem, every group is isomorphic to some permutation group.
The way in which the elements of a permutation group permute the elements of the set is called its group action. Group actions have applications in the study of symmetries, combinatorics and many other branches of mathematics, physics and chemistry.
Image:Rubik's cube.svg|thumb|The popular puzzle Rubik's Cube invented in 1974 by Ernő Rubik has been used as an illustration of permutation groups. Each rotation of a layer of the cube results in a permutation of the surface colors and is a member of the group. The permutation group of the cube is called the Rubik's Cube group.

Basic properties and terminology

A permutation group is a subgroup of a symmetric group; that is, its elements are permutations of a given set. It is thus a subset of a symmetric group that is closed under composition of permutations, contains the identity permutation, and contains the inverse permutation of each of its elements. A general property of finite groups implies that a finite nonempty subset of a symmetric group is a permutation group if and only if it is closed under permutation composition.
The degree of a group of permutations of a finite set is the number of elements in the set. The order of a group is the number of elements in the group. By Lagrange's theorem, the order of any finite permutation group of degree n must divide n! since n-factorial is the order of the symmetric group S_n.

Notation

Since permutations are bijections of a set, they can be represented by Cauchy's two-line notation. This notation lists each of the elements of M in the first row, and for each element, its image under the permutation below it in the second row. If is a permutation of the set then,
For instance, a particular permutation of the set can be written as
this means that σ satisfies σ = 2, σ = 5, σ = 4, σ = 3, and σ = 1. The elements of M need not appear in any special order in the first row, so the same permutation could also be written as
Permutations are also often written in cycle notation so that given the set M =, a permutation g of M with g = 2, g = 4, g = 1 and g = 3 will be written as, or more commonly, since 3 is left unchanged; if the objects are denoted by single letters or digits, commas and spaces can also be dispensed with, and we have a notation such as. The permutation written [|above] in 2-line notation would be written in cycle notation as

Composition of permutations–the group product

The product of two permutations is defined as their composition as functions, so is the function that maps any element x of the set to. Note that the rightmost permutation is applied to the argument first, because of the way function composition is written. Some authors prefer the leftmost factor acting first, but to that end permutations must be written to the right of their argument, often as a superscript, so the permutation acting on the element results in the image. With this convention, the product is given by.
However, this gives a different rule for multiplying permutations. This convention is commonly used in the permutation group literature, but this article uses the convention where the rightmost permutation is applied first.
Since the composition of two bijections always gives another bijection, the product of two permutations is again a permutation. In two-line notation, the product of two permutations is obtained by rearranging the columns of the second permutation so that its first row is identical with the second row of the first permutation. The product can then be written as the first row of the first permutation over the second row of the modified second permutation. For example, given the permutations,
the product QP is:
The composition of permutations, when they are written in cycle notation, is obtained by juxtaposing the two permutations and then simplifying to a disjoint cycle form if desired. Thus, the above product would be given by:
Since function composition is associative, so is the product operation on permutations:. Therefore, products of two or more permutations are usually written without adding parentheses to express grouping; they are also usually written without a dot or other sign to indicate multiplication.

Neutral element and inverses

The identity permutation, which maps every element of the set to itself, is the neutral element for this product. In two-line notation, the identity is
In cycle notation, e =... which by convention is also denoted by just or even.
Since bijections have inverses, so do permutations, and the inverse σ⁻¹ of σ is again a permutation. Explicitly, whenever σ=''y one also has σ''⁻¹=x. In two-line notation the inverse can be obtained by interchanging the two lines. For instance
To obtain the inverse of a single cycle, we reverse the order of its elements. Thus,
To obtain the inverse of a product of cycles, we first reverse the order of the cycles, and then we take the inverse of each as above. Thus,
Having an associative product, an identity element, and inverses for all its elements, makes the set of all permutations of M into a group, Sym; a permutation group.

Examples

Consider the following set G₁ of permutations of the set M = :

e = =
*This is the identity, the trivial permutation which fixes each element.
a = =
*This permutation interchanges 1 and 2, and fixes 3 and 4.
b = =
*Like the previous one, but exchanging 3 and 4, and fixing the others.
ab =
*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 abab = e. This permutation group is, as an abstract group, the Klein group V₄.
As another example consider the group of symmetries of a square. Let the vertices of a square be labeled 1, 2, 3 and 4. The symmetries are determined by the images of the vertices, that can, in turn, be described by permutations. The rotation by 90° about the center of the square is described by the permutation. The 180° and 270° rotations are given by and, respectively. The reflection about the horizontal line through the center is given by and the corresponding vertical line reflection is. The reflection about the 1,3−diagonal line is and reflection about the 2,4−diagonal is. The only remaining symmetry is the identity. This permutation group is known, as an abstract group, as the dihedral group of order 8.

Group actions

In the above example of the symmetry group of a square, the permutations "describe" the movement of the vertices of the square induced by the group of symmetries. It is common to say that these group elements are "acting" on the set of vertices of the square. This idea can be made precise by formally defining a group action.
Let G be a group and M a nonempty set. An action of G on M is a function f: G × M → M such that

f = x, for all x in M, and
f = f, for all g,''h in G'' and all x in M.

This pair of conditions can also be expressed as saying that the action induces a group homomorphism from G into Sym. Any such homomorphism is called a representation of G on M.
For any permutation group, the action that sends → g is called the natural action of G on M. This is the action that is assumed unless otherwise indicated. In the example of the symmetry group of the square, the group's action on the set of vertices is the natural action. However, this group also induces an action on the set of four triangles in the square, which are: t₁ = 234, t₂ = 134, t₃ = 124 and t₄ = 123. It also acts on the two diagonals: d₁ = 13 and d₂ = 24.

Group element	Action on triangles	Action on diagonals

Transitive actions

The action of a group G on a set M is said to be transitive if, for every two elements s, t of M, there is some group element g such that g = t. Equivalently, the set M forms a single orbit under the action of G. Of the examples above, the group of permutations of is not transitive but the group of symmetries of a square is transitive on the vertices.

Primitive actions

A permutation group G acting transitively on a non-empty finite set M is imprimitive if there is some nontrivial set partition of M that is preserved by the action of G, where "nontrivial" means that the partition isn't the partition into singleton sets nor the partition with only one part. Otherwise, if G is transitive but does not preserve any nontrivial partition of M, the group G is primitive.
For example, the group of symmetries of a square is imprimitive on the vertices: if they are numbered 1, 2, 3, 4 in cyclic order, then the partition into opposite pairs is preserved by every group element. On the other hand, the full symmetric group on a set M is always primitive.