A permutation group on a set is a collection of permutations of that contains the identity permutation and is closed under composition and inverses. Equivalently, it is a subgroup of the symmetric group , the group of all bijections from to itself. When has elements, the action has degree , and its symmetric group is usually denoted . Permutation groups give a precise language for describing transformations that rearrange objects while preserving specified relationships.
Their importance extends beyond the study of rearrangements. Every abstract group can be represented faithfully as a permutation group, while a particular permutation representation exposes geometric, combinatorial, or algebraic features that the abstract multiplication law alone does not display. Permutation groups connect group theory with polynomial equations, finite geometries, graph symmetries, counting problems, and computational algorithms. Their study ranges from concrete cycle calculations to the structure of primitive finite groups and the topology of infinite transformation groups.
Definition, actions, and permutation representations
A permutation of is a bijection . The group operation is composition: under the convention used here,
Thus the rightmost permutation acts first. The identity fixes every point, and the inverse of a permutation reverses its rearrangement. Some literature, particularly in computational group theory, instead writes points on the left of exponents and uses right actions; formulas must then be interpreted consistently with that convention.
A permutation group is therefore both an abstract group and a specified action on a set. More generally, a group action of an abstract group on is a homomorphism
Its image is a permutation group. The action is faithful when is injective, meaning that no nonidentity element acts trivially on every point. Otherwise, the action represents the quotient by its kernel rather than distinguishing all elements of .
Cayley’s theorem states that every group has a faithful permutation representation. For each , left multiplication defines the permutation of the underlying set of . The identity makes a homomorphism, and proves injectivity. A finite group of order consequently embeds in . This construction is fundamental, but its degree need not be minimal: the symmetry group of a square has order and already acts faithfully on its four vertices.
An abstract isomorphism does not necessarily identify two permutation representations. The cyclic group of order , for example, can act regularly on four points or act on five points by the same four-cycle with one additional fixed point. The abstract groups are identical, but the actions have different degrees and orbit structures. Actions on sets of the same size are permutation equivalent when a bijection between the sets conjugates one acting group to the other.
This distinction makes the underlying set essential data. Questions about group order or commutativity concern the abstract group; questions about fixed points, transitivity, or blocks concern the chosen representation. The same group may admit many inequivalent actions, each adapted to a different problem. A faithful action of small degree can make computation efficient, whereas an action on geometric objects may reveal incidence relations or invariant configurations.
Cycle structure, parity, and basic examples
For a finite set, every permutation decomposes into disjoint cycles. A cycle
sends to , sends to , and fixes points not displayed. Disjoint cycles commute because they move disjoint subsets. The decomposition is unique up to rearranging the cycles and cyclically rotating their entries. Fixed points are cycles of length , although they are commonly omitted from the notation.
For example,
has order : its third power eliminates the three-cycle, its second power eliminates the transposition, and both disappear precisely when the exponent is divisible by and . In general, the order is the least common multiple of the cycle lengths. Conjugation relabels cycles:
Consequently, two elements of are conjugate exactly when they have the same cycle-length multiset. Its cycle type is therefore an integer partition of , understood here as a partition of the integer rather than a partition of the underlying point set.
Every finite permutation is a product of transpositions, which interchange two points. Although this expression is not unique, the parity of the number of transpositions is invariant. The sign homomorphism
assigns to even permutations and to odd ones. An -cycle has sign . For , the kernel is the alternating group , of order . For , is nonabelian and simple: its only normal subgroups are itself and the identity subgroup.
These constructions provide standard generating sets. The adjacent transpositions generate , and all three-cycles together generate . A much smaller generating set for is together with . Conjugating the transposition by powers of the long cycle produces transpositions between consecutive points around the cycle, which suffice to generate the full symmetric group.
Geometric examples impose stronger restrictions than arbitrary rearrangement. The dihedral group of a regular -gon, for , has elements in its action on vertices. It is generated by a rotation and a reflection , satisfying and . Most permutations of the vertices do not preserve adjacency, so this group is generally much smaller than .
Orbits, stabilizers, and transitivity
The orbit of a point under is
Being in the same orbit is an equivalence relation, so the orbits partition into invariant subsets. The stabilizer of is the subgroup
For finite , the orbit–stabilizer formula gives
More generally, the orbit is naturally in bijection with the set of left cosets of in .
An action is transitive if it has exactly one orbit. Every transitive action can be described as a coset action: if , then identifies with . Conversely, left multiplication on the cosets of any subgroup gives a transitive action. Its kernel is
the largest normal subgroup of contained in . Thus a coset action is faithful precisely when this core is trivial.
An action is semiregular if no nonidentity element fixes a point, and regular if it is both semiregular and transitive. In a regular action, exactly one group element sends any chosen point to any other, and a finite regular group has order equal to its degree. Cayley’s left multiplication action is regular. By contrast, the full symmetry group of a square is transitive on its vertices but not regular: a reflection through two opposite vertices fixes those vertices.
For a finite set of size , an action is -transitive, where , if it is transitive on ordered -tuples of distinct points. The natural action of is -transitive, and that of is -transitive for . A -transitive group can send any ordered pair of distinct points to any other such pair. Equivalently, it is transitive and a point stabilizer is transitive on all remaining points.
Higher transitivity forces substantial group order. In a -transitive action,
divides , by applying orbit–stabilizer to an ordered -tuple. Another useful invariant is the rank of a transitive action: the number of orbits of on . Rank is equivalent to -transitivity when . Higher ranks record the different relative positions that two points can occupy, making rank useful in the study of finite geometries and symmetric graphs.
Blocks, primitivity, and structural classification
A nonempty subset is a block for if, for every , either or . In a transitive action, the translates of a block form a partition into equally sized parts. Singleton sets and the whole set are always blocks. A transitive action of degree greater than is primitive if these are its only blocks; otherwise it is imprimitive. Primitivity concerns the action, not just the abstract group.
For example, the dihedral group acting on the four vertices of a square is imprimitive: the two pairs of opposite vertices form an invariant partition. Its action remains transitive because any vertex can be carried to any other. Every -transitive action is primitive, but the converse fails. A cyclic group of prime order acting regularly is primitive, since a nontrivial block size would have to divide the prime degree, yet it is not -transitive when the prime exceeds .
Blocks have an exact subgroup interpretation. In the action of on , blocks containing the coset correspond to subgroups with
The associated block consists of the cosets of lying inside . Thus a transitive action of degree greater than is primitive exactly when its point stabilizer is a maximal proper subgroup. This correspondence translates a combinatorial property of a partition into a structural property of a subgroup.
Imprimitive groups can be organized using wreath products. If there are blocks of size , the action embeds, after suitable labeling, into in its imprimitive action. The normal subgroup permutes points independently inside the blocks, while permutes the blocks themselves. This does not mean that every imprimitive group is the full wreath product; rather, the wreath product supplies an ambient structure separating internal and external motion.
Primitive groups are central to finite permutation-group classification. The orbits of a normal subgroup form an invariant partition, so every nontrivial normal subgroup of a faithful primitive group is transitive. The O’Nan–Scott theory develops this restriction through the socle, the subgroup generated by minimal nontrivial normal subgroups. Important families include affine groups with a regular elementary abelian normal subgroup, almost simple groups lying between a nonabelian simple group and its automorphism group, and diagonal or product-action constructions. The classification of finite simple groups supplies much of the information needed to analyze these families, although identifying all primitive actions remains distinct from merely listing the underlying simple groups.
Affine, projective, and other important families
Affine permutation groups arise from a vector space over a finite field . An invertible affine transformation has the form
These transformations form the affine general linear group , acting on the vectors of . Translations form a regular normal subgroup isomorphic to the additive group of , while the transformations fixing form . This gives a semidirect product .
More generally, , with , is primitive precisely when preserves no nonzero proper additive subgroup of . Viewing as a vector space over its prime field makes this an irreducibility condition. A preserved subspace yields a block system consisting of its additive cosets. The full affine general linear group is -transitive: a translation moves the first member of an ordered pair to the origin, and an invertible linear map sends its nonzero difference vector to any other nonzero vector.
Projective groups act on one-dimensional subspaces rather than individual vectors. A -dimensional vector space over has
such subspaces. Scalar matrices act trivially on them, so the induced faithful projective action factors through an appropriate quotient. This leads to groups such as and , central objects in projective geometry. Their actions preserve incidence between points, lines, and higher-dimensional subspaces.
On the projective line, acts on by fractional linear transformations
with the usual interpretation at poles and at infinity. A unique projective transformation sends any ordered triple of distinct points to any other, so the action is sharply -transitive. Its order is , exactly the number of ordered triples of distinct projective points.
Exceptional finite groups supply further highly symmetric actions. The Mathieu groups include and , whose natural actions are sharply -transitive and sharply -transitive, respectively, and , which is -transitive on points. Their actions are linked to special combinatorial designs and error-correcting codes. These examples show that the natural symmetric and alternating groups are not the only sources of multiple transitivity, while also illustrating how restrictive high transitivity becomes outside those two families.
Counting orbits and constructing linear representations
Permutation groups provide systematic methods for counting objects up to symmetry. If a finite group acts on a finite set , the Cauchy–Frobenius orbit-counting lemma, often called Burnside’s lemma, states that
Here denotes the set of orbits. The formula follows by counting pairs satisfying : each orbit contributes exactly such pairs. It replaces the difficult task of choosing one representative from each symmetry class with a sum of fixed-point counts.
For instance, consider two-colorings of the four vertices of a square, identifying colorings under rotations but not reflections. The identity rotation fixes all colorings. Each quarter-turn fixes only the two constant colorings. The half-turn fixes colorings, because opposite vertices must have matching colors. The number of rotation classes is therefore
Including reflections changes the acting group, so their fixed-point contributions must also enter the average.
For a permutation group of degree , let be the number of cycles of length in . The cycle index is
Substituting counts orbits of colorings with available colors, since a fixed coloring is constant along each cycle. More elaborate substitutions track how often each color is used. This is the basis of Pólya enumeration, an important method in combinatorics and the counting of chemical configurations.
An action also produces a linear representation. Given a field , form the vector space with basis , indexed by , and define . For finite , each element is represented by a permutation matrix. Over a field of characteristic zero, its trace is the number of fixed points of ; over , its determinant is the sign of the permutation. Thus elementary permutation data become invariants in representation theory.
The resulting permutation character contains information about the action. Its average over is the number of point orbits, while the average of is the number of orbits on ordered pairs. For a transitive finite action, the latter equals its rank. The all-ones vector always spans a trivial subrepresentation. Over characteristic zero, a -transitive action has a complementary subrepresentation of dimension that is irreducible, connecting pairwise symmetry with linear decomposition.
Computational methods and symmetry algorithms
A finite permutation group is usually specified by generators rather than by listing every element. A permutation of degree can be stored as an array of its images, and composition and inversion require time linear in in this representation. Yet a short generator list can describe an enormous group: two permutations suffice to generate , whose order is . Effective computation must therefore extract structure without enumerating every group element.
The central data structure is a base and strong generating set. A base is a sequence of points whose pointwise stabilizer is trivial. It gives a stabilizer chain
where fixes . A generating set is strong relative to this base if its elements lying in each chain subgroup generate that subgroup. Repeated use of orbit–stabilizer then yields
where the exponent denotes the orbit under the indicated subgroup.
The Schreier–Sims algorithm, developed from work of Charles Sims in the late 1960s and early 1970s, constructs and uses this structure. Its foundation is Schreier’s method for generating stabilizers from generators and orbit representatives. A candidate permutation is tested for membership by successively composing it with suitable representatives so that it fixes each base point. This process, called sifting, reduces membership to a sequence of orbit and stabilizer calculations.
With a strong generating set, group order, membership, point orbits, and many stabilizer calculations become practical even when the group is far too large to enumerate. Randomized variants often construct useful chains faster, while verification procedures establish correctness. Complexity depends on the degree, generator count, and precise algorithm; the number of group elements alone is a poor guide to practical difficulty.
Permutation-group methods also appear in graph theory. A graph automorphism is a permutation of vertices preserving adjacency, and all such automorphisms form a permutation group. Graph-isomorphism programs combine combinatorial refinement with group-theoretic techniques to recognize equivalent vertices and avoid repeatedly exploring symmetric branches. In optimization, a symmetry group may permute variables while preserving constraints and the objective, permitting equivalent search cases to be identified. Particular tasks such as finding subgroup intersections or centralizers can still demand substantial computation: an efficient representation of a group does not make every question about it equally easy.
Historical development and the theory of equations
Permutation groups emerged from attempts to understand formulas for polynomial roots. Eighteenth-century algebraists studied how expressions in the roots changed when those roots were permuted. Joseph-Louis Lagrange’s investigations, published in 1770–1771, connected the number of distinct values of such expressions with the behavior of solution methods. These studies did not yet use the fully abstract modern definition of a group, but they made substitutions of roots into mathematical objects worthy of study in their own right.
Paolo Ruffini and Niels Henrik Abel investigated the impossibility of solving the general quintic by radicals. Abel’s 1824 publication established the general impossibility result. Évariste Galois subsequently identified the decisive role of groups of root permutations, connecting their subgroup structure with intermediate fields and solvability. His work was published by Joseph Liouville in 1846, after Galois’s death in 1832. In modern terminology, Galois theory studies automorphism groups of suitable field extensions and their relation to the extensions’ internal structure.
For a separable polynomial over a field , every automorphism of its splitting field that fixes permutes the roots. Because the splitting field is generated by those roots, the action is faithful. The resulting permutation group preserves all algebraic relations over , not merely the displayed polynomial equation. If the polynomial is irreducible, this action on its roots is transitive. Thus factorization properties have direct interpretations in terms of root orbits.
For a separable polynomial over a field of characteristic zero, solvability by radicals is equivalent to solvability of its Galois group. Here a solvable group is one admitting a series with abelian factors, or equivalently one whose derived series terminates at the identity. The general degree- polynomial has Galois group ; for , this group is not solvable. The obstruction is therefore structural, not simply the failure to discover a sufficiently complicated formula.
During the nineteenth century, permutation groups developed beyond the theory of equations. Augustin-Louis Cauchy investigated substitution groups, Arthur Cayley formulated the regular permutation representation in 1854, and Camille Jordan’s 1870 Traité des substitutions et des équations algébriques systematized a large body of results. Abstract group theory later separated the group concept from any particular action, but permutation representations remained central. Twentieth-century work on finite simple groups, highly transitive groups, and computation transformed the subject from a theory of substitutions into a general framework for finite symmetry.
Infinite permutation groups and topological structure
The definition of a permutation group applies equally to an infinite set. The full symmetric group consists of all bijections of , while the finitary symmetric group consists of those moving only finitely many points. These groups are very different. A permutation of an infinite set may contain infinite orbits, as the translation does on the integers. Such an orbit has the form of a doubly infinite chain rather than a finite cycle.
On an infinite set, finite support permits a well-defined sign, giving a finitary alternating subgroup. There is no sign homomorphism on the full infinite symmetric group extending the ordinary sign of every finite-support permutation. Infinite groups also show that familiar finite implications require care. An action may be -transitive for every positive integer without being the full symmetric group: the finitary symmetric group on an infinite set has this property, since any prescribed bijection between finite tuples can be extended using only finitely many moved points.
Infinite permutation groups carry a natural topology of pointwise convergence when is discrete. A basic neighborhood of the identity is the pointwise stabilizer of a finite subset. Agreement on a sufficiently large finite set therefore means closeness. When is countably infinite, this topology makes the full symmetric group a separable, completely metrizable topological group. The finitary symmetric group is dense: every finite restriction of a permutation can be matched by a finite-support permutation, even though the finitary group is a proper subgroup.
Closed permutation groups connect directly with model theory. The automorphism group of a relational structure is closed in the pointwise-convergence topology, because failure to preserve a relation is witnessed on a finite tuple. Conversely, a closed permutation group can be recovered as the automorphism group of a relational structure obtained by recording its orbits on finite tuples. This correspondence translates questions about transformations into questions about definable relationships.
A group is oligomorphic if it has only finitely many orbits on for every positive integer . The automorphism group of the ordered rationals is an example: finite tuples are classified by their equality and order patterns. For a countably infinite structure in a countable language, the Engeler–Ryll-Nardzewski–Svenonius theorem relates oligomorphic automorphism groups to countable categoricity of its complete first-order theory. Thus orbit counts in infinite permutation groups measure a precise form of logical uniformity, rather than merely the number of ways individual points can be rearranged.