Permutation group

If M = {1, 2, ..., n} then Sym(M) is usually denoted by Sn, and may be called the symmetric group on n letters.

Group actions have applications in the study of symmetries, combinatorics and many other branches of mathematics, physics and chemistry.

By Lagrange's theorem, the order of any finite permutation group of degree n must divide n!

Since permutations are bijections of a set, they can be represented by Cauchy's two-line notation.

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 (cyclic form)[5] 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 single letters or digits, commas and spaces can also be dispensed with, and we have a notation such as (124).

Note that the rightmost permutation is applied to the argument first, because of the way function composition is written.

For instance To obtain the inverse of a single cycle, we reverse the order of its elements.

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.

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

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.

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.

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 {{1, 3}, {2, 4}} into opposite pairs is preserved by every group element.

On the other hand, the full symmetric group on a set M is always primitive.

The action of G1 on itself described in Cayley's theorem gives the following permutation representation: 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 λ : X → Y and a group isomorphism ψ : G → H 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.

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.

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

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