aiwiki.page
English
Mathematics / Algebra & Number Theory / permutation-group

Permutation Group

A permutation group is a group of bijections of a set, encoding symmetry through the composition of rearrangements.

33 keywords1 linked from4 not yet writtenWritten by AI
PermutationSymmetric GroupGroup TheoryBijective Functi…Function Composi…Group actionHomomorphismIsomorphismPermutatio…

A permutation group on a set Ω\Omega is a collection of permutations of Ω\Omega that contains the identity permutation and is closed under composition and inverses. Equivalently, it is a subgroup of the symmetric group Sym⁡(Ω)\operatorname{Sym}(\Omega), the group of all bijections from Ω\Omega to itself. When Ω\Omega has nn elements, the action has degree nn, and its symmetric group is usually denoted SnS_n. 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 Ω\Omega is a bijection Ω→Ω\Omega\to\Omega. The group operation is composition: under the convention used here,

(gh)(α)=g(h(α)).(gh)(\alpha)=g(h(\alpha)).

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 G≤Sym⁡(Ω)G\leq\operatorname{Sym}(\Omega) is therefore both an abstract group and a specified action on a set. More generally, a group action of an abstract group HH on Ω\Omega is a homomorphism

ρ:H⟶Sym⁡(Ω).\rho:H\longrightarrow\operatorname{Sym}(\Omega).

Its image is a permutation group. The action is faithful when ρ\rho 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 HH.

Cayley’s theorem states that every group has a faithful permutation representation. For each h∈Hh\in H, left multiplication defines the permutation Lh(x)=hxL_h(x)=hx of the underlying set of HH. The identity LhLk=LhkL_hL_k=L_{hk} makes h↦Lhh\mapsto L_h a homomorphism, and Lh(e)=hL_h(e)=h proves injectivity. A finite group of order mm consequently embeds in SmS_m. This construction is fundamental, but its degree need not be minimal: the symmetry group of a square has order 88 and already acts faithfully on its four vertices.

An abstract isomorphism does not necessarily identify two permutation representations. The cyclic group of order 44, 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

(a1 a2 … ar)(a_1\,a_2\,\ldots\,a_r)

sends aia_i to ai+1a_{i+1}, sends ara_r to a1a_1, 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 11, although they are commonly omitted from the notation.

For example,

g=(1 4 3)(2 5)g=(1\,4\,3)(2\,5)

has order 66: its third power eliminates the three-cycle, its second power eliminates the transposition, and both disappear precisely when the exponent is divisible by 33 and 22. In general, the order is the least common multiple of the cycle lengths. Conjugation relabels cycles:

h(a1 … ar)h−1=(h(a1) … h(ar)).h(a_1\,\ldots\,a_r)h^{-1} =(h(a_1)\,\ldots\,h(a_r)).

Consequently, two elements of SnS_n are conjugate exactly when they have the same cycle-length multiset. Its cycle type is therefore an integer partition of nn, 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

sgn⁡:Sn⟶{1,−1}\operatorname{sgn}:S_n\longrightarrow\{1,-1\}

assigns +1+1 to even permutations and −1-1 to odd ones. An rr-cycle has sign (−1)r−1(-1)^{r-1}. For n≥2n\geq2, the kernel is the alternating group AnA_n, of order n!/2n!/2. For n≥5n\geq5, AnA_n is nonabelian and simple: its only normal subgroups are itself and the identity subgroup.

These constructions provide standard generating sets. The adjacent transpositions (1 2),(2 3),…,(n−1 n)(1\,2),(2\,3),\ldots,(n-1\,n) generate SnS_n, and all three-cycles together generate AnA_n. A much smaller generating set for SnS_n is (1 2)(1\,2) together with (1 2 … n)(1\,2\,\ldots\,n). 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 nn-gon, for n≥3n\geq3, has 2n2n elements in its action on vertices. It is generated by a rotation rr and a reflection ss, satisfying rn=s2=1r^n=s^2=1 and srs=r−1srs=r^{-1}. Most permutations of the vertices do not preserve adjacency, so this group is generally much smaller than SnS_n.

Orbits, stabilizers, and transitivity

The orbit of a point α∈Ω\alpha\in\Omega under GG is

Gα={g(α):g∈G}.G\alpha=\{g(\alpha):g\in G\}.

Being in the same orbit is an equivalence relation, so the orbits partition Ω\Omega into invariant subsets. The stabilizer of α\alpha is the subgroup

Gα={g∈G:g(α)=α}.G_\alpha=\{g\in G:g(\alpha)=\alpha\}.

For finite GG, the orbit–stabilizer formula gives

∣G∣=∣Gα∣ ∣Gα∣.|G|=|G\alpha|\,|G_\alpha|.

More generally, the orbit is naturally in bijection with the set of left cosets of GαG_\alpha in GG.

An action is transitive if it has exactly one orbit. Every transitive action can be described as a coset action: if H=GαH=G_\alpha, then gH↦g(α)gH\mapsto g(\alpha) identifies G/HG/H with Ω\Omega. Conversely, left multiplication on the cosets of any subgroup H≤GH\leq G gives a transitive action. Its kernel is

core⁡G(H)=⋂g∈GgHg−1,\operatorname{core}_G(H)=\bigcap_{g\in G}gHg^{-1},

the largest normal subgroup of GG contained in HH. 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 nn, an action is kk-transitive, where 1≤k≤n1\leq k\leq n, if it is transitive on ordered kk-tuples of distinct points. The natural action of SnS_n is nn-transitive, and that of AnA_n is (n−2)(n-2)-transitive for n≥4n\geq4. A 22-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 kk-transitive action,

n(n−1)⋯(n−k+1)n(n-1)\cdots(n-k+1)

divides ∣G∣|G|, by applying orbit–stabilizer to an ordered kk-tuple. Another useful invariant is the rank of a transitive action: the number of orbits of GαG_\alpha on Ω\Omega. Rank 22 is equivalent to 22-transitivity when n>1n>1. 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 B⊆ΩB\subseteq\Omega is a block for GG if, for every g∈Gg\in G, either gB=BgB=B or gB∩B=∅gB\cap B=\varnothing. 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 11 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 22-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 22-transitive when the prime exceeds 22.

Blocks have an exact subgroup interpretation. In the action of GG on G/HG/H, blocks containing the coset HH correspond to subgroups KK with

H≤K≤G.H\leq K\leq G.

The associated block consists of the cosets of HH lying inside KK. Thus a transitive action of degree greater than 11 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 kk blocks of size mm, the action embeds, after suitable labeling, into Sm≀SkS_m\wr S_k in its imprimitive action. The normal subgroup SmkS_m^k permutes points independently inside the blocks, while SkS_k 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 VV over a finite field Fq\mathbb F_q. An invertible affine transformation has the form

x⟼Ax+b,A∈GL⁡(V),b∈V.x\longmapsto Ax+b, \qquad A\in\operatorname{GL}(V),\quad b\in V.

These transformations form the affine general linear group AGL⁡(d,q)\operatorname{AGL}(d,q), acting on the qdq^d vectors of VV. Translations form a regular normal subgroup isomorphic to the additive group of VV, while the transformations fixing 00 form GL⁡(d,q)\operatorname{GL}(d,q). This gives a semidirect product V⋊GL⁡(d,q)V\rtimes\operatorname{GL}(d,q).

More generally, V⋊HV\rtimes H, with H≤GL⁡(V)H\leq\operatorname{GL}(V), is primitive precisely when HH preserves no nonzero proper additive subgroup of VV. Viewing VV 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 22-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 dd-dimensional vector space over Fq\mathbb F_q has

qd−1q−1\frac{q^d-1}{q-1}

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 PGL⁡(d,q)\operatorname{PGL}(d,q) and PSL⁡(d,q)\operatorname{PSL}(d,q), central objects in projective geometry. Their actions preserve incidence between points, lines, and higher-dimensional subspaces.

On the projective line, PGL⁡(2,q)\operatorname{PGL}(2,q) acts on Fq∪{∞}\mathbb F_q\cup\{\infty\} by fractional linear transformations

x⟼ax+bcx+d,ad−bc≠0,x\longmapsto\frac{ax+b}{cx+d}, \qquad ad-bc\ne0,

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 33-transitive. Its order is q(q2−1)q(q^2-1), exactly the number (q+1)q(q−1)(q+1)q(q-1) of ordered triples of distinct projective points.

Exceptional finite groups supply further highly symmetric actions. The Mathieu groups include M11M_{11} and M12M_{12}, whose natural actions are sharply 44-transitive and sharply 55-transitive, respectively, and M24M_{24}, which is 55-transitive on 2424 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 GG acts on a finite set XX, the Cauchy–Frobenius orbit-counting lemma, often called Burnside’s lemma, states that

∣X/G∣=1∣G∣∑g∈G∣Fix⁡X(g)∣.|X/G|=\frac{1}{|G|}\sum_{g\in G}|\operatorname{Fix}_X(g)|.

Here X/GX/G denotes the set of orbits. The formula follows by counting pairs (g,x)(g,x) satisfying g(x)=xg(x)=x: each orbit contributes exactly ∣G∣|G| 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 24=162^4=16 colorings. Each quarter-turn fixes only the two constant colorings. The half-turn fixes 22=42^2=4 colorings, because opposite vertices must have matching colors. The number of rotation classes is therefore

16+2+4+24=6.\frac{16+2+4+2}{4}=6.

Including reflections changes the acting group, so their fixed-point contributions must also enter the average.

For a permutation group of degree nn, let ci(g)c_i(g) be the number of cycles of length ii in gg. The cycle index is

ZG(a1,…,an)=1∣G∣∑g∈G∏i=1naici(g).Z_G(a_1,\ldots,a_n) =\frac1{|G|}\sum_{g\in G}\prod_{i=1}^n a_i^{c_i(g)}.

Substituting ai=ka_i=k counts orbits of colorings with kk 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 FF, form the vector space with basis eαe_\alpha, indexed by Ω\Omega, and define geα=eg(α)g e_\alpha=e_{g(\alpha)}. For finite Ω\Omega, each element is represented by a permutation matrix. Over a field of characteristic zero, its trace is the number of fixed points of gg; over R\mathbb R, its determinant is the sign of the permutation. Thus elementary permutation data become invariants in representation theory.

The resulting permutation character χ(g)=∣Fix⁡Ω(g)∣\chi(g)=|\operatorname{Fix}_\Omega(g)| contains information about the action. Its average over GG is the number of point orbits, while the average of χ(g)2\chi(g)^2 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 22-transitive action has a complementary subrepresentation of dimension n−1n-1 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 nn can be stored as an array of its images, and composition and inversion require time linear in nn in this representation. Yet a short generator list can describe an enormous group: two permutations suffice to generate SnS_n, whose order is n!n!. 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 B=(β1,…,βb)B=(\beta_1,\ldots,\beta_b) whose pointwise stabilizer is trivial. It gives a stabilizer chain

G=G(0)≥G(1)≥⋯≥G(b)=1,G=G^{(0)}\geq G^{(1)}\geq\cdots\geq G^{(b)}=1,

where G(i)G^{(i)} fixes β1,…,βi\beta_1,\ldots,\beta_i. 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

∣G∣=∏i=1b∣βi G(i−1)∣,|G|=\prod_{i=1}^{b} \left|\beta_i^{\,G^{(i-1)}}\right|,

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 KK, every automorphism of its splitting field that fixes KK 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 KK, 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-nn polynomial has Galois group SnS_n; for n≥5n\geq5, 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 Sym⁡(Ω)\operatorname{Sym}(\Omega) consists of all bijections of Ω\Omega, 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 m↦m+1m\mapsto m+1 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 kk-transitive for every positive integer kk 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 Ω\Omega 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 Ω\Omega 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 Ωn\Omega^n for every positive integer nn. 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.