Permutation group

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.

Being a subgroup of a symmetric group, all that is necessary for a set of permutations to satisfy the group axioms and be a permutation group is that it contain the identity permutation, the inverse permutation of each permutation it contains, and be closed under composition of its permutations.[2] 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.[3]

The degree of a group of permutations of a finite set is the number of elements in the set. The order of a group (of any type) is the number of elements (cardinality) 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 Sn.

this means that σ satisfies σ(1) = 2, σ(2) = 5, σ(3) = 4, σ(4) = 3, and σ(5) = 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

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 (leftmost) permutation so that its first row is identical with the second row of the first (rightmost) 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 composition of permutations, when they are written in cyclic form, is obtained by juxtaposing the two permutations (with the second one written on the left) and then simplifying to a disjoint cycle form if desired. Thus, in cyclic notation the above product would be given by:

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 cyclic notation, e = (1)(2)(3)...(n) which by convention is also denoted by just (1) or even ().[11]

Since bijections have inverses, so do permutations, and the inverse σ−1 of σ is again a permutation. Explicitly, whenever σ(x)=y one also has σ−1(y)=x. In two-line notation the inverse can be obtained by interchanging the two lines (and sorting the columns if one wishes the first line to be in a given order). 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(M); a permutation group.

G1 forms a group, since aa = bb = e, ba = ab, and abab = e. This permutation group is isomorphic, as an abstract group, to the Klein group V4.

As another example consider the group of symmetries of a square. Let the vertices of a square be labeled 1, 2, 3 and 4 (counterclockwise around the square starting with 1 in the top left corner). The symmetries are determined by the images of the vertices, that can, in turn, be described by permutations. The rotation by 90° (counterclockwise) about the center of the square is described by the permutation (1234). The 180° and 270° rotations are given by (13)(24) and (1432), respectively. The reflection about the horizontal line through the center is given by (12)(34) and the corresponding vertical line reflection is (14)(23). The reflection about the 1,3−diagonal line is (24) and reflection about the 2,4−diagonal is (13). The only remaining symmetry is the identity (1)(2)(3)(4). This permutation group is abstractly known as the dihedral group of order 8.

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.[12]

Let G be a group and M a nonempty set. An action of G on M is a function f: G × MM such that

This last condition can also be expressed as saying that the action induces a group homomorphism from G into Sym(M).[12] Any such homomorphism is called a (permutation) representation of G on M.

For any permutation group, the action that sends (g, x) → g(x) is called the natural action of G on M. This is the action that is assumed unless otherwise indicated.[12] 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: t1 = 234, t2 = 134, t3 = 124 and t4 = 123. It also acts on the two diagonals: d1 = 13 and d2 = 24.

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.

Any group G can act on itself (the elements of the group being thought of as the set M) in many ways. In particular, there is a regular action given by (left) multiplication in the group. That is, f(g, x) = gx for all g and x in G. For each fixed g, the function fg(x) = gx is a bijection on G and therefore a permutation of the set of elements of G. Each element of G can be thought of as a permutation in this way and so G is isomorphic to a permutation group; this is the content of Cayley's theorem.

If G and H are two permutation groups on sets X and Y with actions f1 and f2 respectively, then we say that G and H are permutation isomorphic (or isomorphic as permutation groups) if there exists a bijective map λ : XY and a group isomorphism ψ : GH such that

If X = Y this is equivalent to G and H being conjugate as subgroups of Sym(X).[15] The special case where G = H and ψ is the identity map gives rise to the concept of equivalent actions of a group.[16]

When a group G acts on a set S, the action may be extended naturally to the Cartesian product Sn of S, consisting of n-tuples of elements of S: the action of an element g on the n-tuple (s1, ..., sn) is given by

The group G is said to be oligomorphic if the action on Sn has only finitely many orbits for every positive integer n.[17][18] (This is automatic if S is finite, so the term is typically of interest when S is infinite.)

The interest in oligomorphic groups is partly based on their application to model theory, for example when considering automorphisms in countably categorical theories.[19]

The study of groups originally grew out of an understanding of permutation groups.[20] Permutations had themselves been intensively studied by Lagrange in 1770 in his work on the algebraic solutions of polynomial equations. This subject flourished and by the mid 19th century a well-developed theory of permutation groups existed, codified by Camille Jordan in his book Traité des Substitutions et des Équations Algébriques of 1870. Jordan's book was, in turn, based on the papers that were left by Évariste Galois in 1832.

When Cayley introduced the concept of an abstract group, it was not immediately clear whether or not this was a larger collection of objects than the known permutation groups (which had a definition different from the modern one). Cayley went on to prove that the two concepts were equivalent in Cayley's theorem.[21]

Another classical text containing several chapters on permutation groups is Burnside's Theory of Groups of Finite Order of 1911.[22] The first half of the twentieth century was a fallow period in the study of group theory in general, but interest in permutation groups was revived in the 1950s by H. Wielandt whose German lecture notes were reprinted as Finite Permutation Groups in 1964.[23]