1 Definition and basic examples

Permutation groups are groups whose elements are permutations of a set and whose operation is composition. They offer a concrete model for abstract group theory because the group law can be described by the familiar process of applying one rearrangement after another. Permutation groups may act on finite or infinite sets, although finite examples are most commonly studied.

1.1 Permutations of a set

A permutation of a set is a bijection from the set to itself. Because it has both an inverse and an unambiguous composition rule, the collection of all permutations of a given set naturally forms a group. In practice, one often studies permutations of a finite set such as {1, 2, ..., n}, but the definition applies equally well to any set.

1.2 Group structure under composition

The group operation is function composition. If two permutations are applied in succession, the result is again a permutation of the same set. Composition is associative, the identity map acts as a neutral element, and every permutation has an inverse permutation that reverses its effect.

1.3 Symmetric groups

The symmetric group on a set is the full group of all its permutations. When the set has n elements, this group is usually written S_n. Symmetric groups are central in algebra because every finite permutation group can be viewed as a subgroup of some S_n.

1.3.1 Identity permutation

The identity permutation leaves every element unchanged. It serves as the identity element of the permutation group and is often denoted by e or id. In cycle notation, it may be written as the empty product of cycles or simply omitted.

1.3.2 Inverses and closure

The inverse of a permutation is obtained by reversing each correspondence. Closure under composition means that combining any two permutations produces another permutation of the same set. These properties ensure that permutations form a group rather than merely a collection of rearrangements.

1.4 Elementary examples of permutation groups

Simple examples include the trivial group acting on a single object, the group generated by a swap of two elements, and the full symmetric group on three letters. The cyclic group of order three can be realized as the rotations of an equilateral triangle, while the dihedral group appears as the symmetries of a polygon. Such examples illustrate how permutation groups encode symmetry in a tangible form.

2 Notation and representations

Permutation groups are written in several standard ways, each emphasizing a different feature of the action. Some notations highlight the rearrangement of individual elements, while others encode the same information in algebraic or linear forms.

2.1 Cycle notation

Cycle notation records the movement of elements around a loop. For example, the cycle (1 3 2) means that 1 moves to 3, 3 moves to 2, and 2 moves back to 1. Elements not mentioned in a cycle are understood to be fixed.

2.1.1 Disjoint cycle decomposition

Every permutation can be expressed as a product of disjoint cycles. Disjoint cycles commute because they move different elements, so the decomposition is especially convenient for computation and classification. This representation makes it easy to determine the order of a permutation and to study its structure.

2.1.2 Transpositions

A transposition is a cycle of length two, which swaps two elements and fixes the rest. Any permutation of a finite set can be written as a product of transpositions. This fact is fundamental in the study of parity and the alternating group.

2.2 One-line notation

One-line notation lists the images of the elements in order. For a permutation of {1, 2, ..., n}, the sequence (a1, a2, ..., an) indicates that i maps to ai. This notation is compact and is often useful in combinatorial settings and computer calculations.

2.3 Matrix representations

Permutations can also be represented by matrices. In a suitable basis, each permutation corresponds to a matrix with exactly one entry equal to 1 in each row and each column, and all other entries equal to 0. Such matrices translate rearrangements into linear algebra.

2.3.1 Permutation matrices

A permutation matrix is obtained from the identity matrix by permuting its rows or columns. Multiplying by a permutation matrix reorders coordinates. The set of permutation matrices forms a group under matrix multiplication, mirroring the structure of the corresponding permutation group.

2.3.2 Action on vector spaces

Permutation groups may act on vector spaces by permuting basis vectors. This produces a linear representation that is widely used in algebra and combinatorics. The resulting module or representation can reveal structural properties that are not immediately visible from the set-theoretic action alone.

3 Group actions and permutation groups

Permutation groups are closely tied to the general theory of group actions. Every permutation group can be seen as a group acting on a set, and many abstract groups can be studied by examining how they act faithfully on suitable sets.

3.1 Group actions on sets

A group action assigns to each group element a bijection of a set in a way that respects the group operation. This framework unifies many symmetry phenomena. When a group acts on a set, each element of the group can be interpreted as a specific permutation of that set.

3.2 Faithful actions

An action is faithful if distinct group elements induce distinct permutations. Faithfulness ensures that the action captures the full group structure rather than collapsing different elements into the same transformation. Faithful permutation actions are especially important because they realize the group concretely as a subgroup of a symmetric group.

3.3 Permutation representation

A permutation representation is a homomorphism from a group into a symmetric group arising from an action on a set. It packages the action into algebraic form and allows the use of permutation-group methods in broader group-theoretic problems. Such representations are among the simplest and most direct linear or combinatorial realizations of a group.

3.3.1 Kernel of the action

The kernel of an action consists of the group elements that act trivially on every point. If the kernel is trivial, the action is faithful. The kernel measures how much information is lost when a group is represented by permutations of a set.

3.3.2 Embedding into a symmetric group

Every faithful action yields an embedding of the group into a symmetric group on the underlying set. This is a key reason permutation groups are so fundamental: they show that abstract groups can often be studied as concrete rearrangement groups. The symmetric group therefore serves as a universal ambient object for finite permutation theory.

3.4 Conjugation action

A group can act on itself by conjugation, sending an element x to g x g^-1. This action is important because it reflects the internal symmetry of the group. In the case of permutation groups, conjugation often helps describe how cycles and stabilizers transform under relabeling.

4 Orbits and stabilizers

Orbits and stabilizers are the basic tools for analyzing how a permutation group acts on a set. They divide the set into regions of connected movement and identify the elements that remain fixed under a chosen point.

4.1 Orbits

The orbit of a point is the set of all images of that point under the group action. Orbits partition the set into equivalence classes of points that can be moved into one another. They provide a first measure of how transitive or fragmented an action is.

4.2 Stabilizers

The stabilizer of a point is the subgroup consisting of all group elements that fix that point. Stabilizers capture local symmetry around a point and are often easier to study than the whole group. Their size and structure are closely linked to orbit sizes.

4.3 Orbit-stabilizer theorem

The orbit-stabilizer theorem states that the size of an orbit is equal to the index of the stabilizer in the group, for finite groups. This result is one of the most useful counting tools in permutation group theory. It connects global group size with local fixing behavior.

4.4 Block systems

A block system is a partition of the underlying set into subsets that are permuted among themselves by the group. Block systems reveal intermediate levels of symmetry between complete transitivity and total separation. They are especially useful in distinguishing primitive from imprimitive actions.

4.4.1 Blocks of imprimitivity

A block of imprimitivity is a subset that is either moved entirely onto itself or disjointly onto another block under every group element. Such blocks behave like indivisible units from the point of view of the action. Their existence shows that the action has a nontrivial internal partition preserved by symmetry.

4.4.2 Imprimitive actions

An action is imprimitive if it preserves a nontrivial block system. Imprimitive actions arise frequently in permutation groups built from smaller actions or wreath products. They sit between transitive and primitive actions in the hierarchy of symmetry types.

5 Types of permutation groups

Permutation groups are classified according to how strongly they act on the underlying set. The main distinctions are between transitive, primitive, and doubly transitive actions, together with the opposite cases of intransitivity and imiprimitivity.

5.1 Transitive groups

A group action is transitive if there is only one orbit. In such a case, any point of the set can be moved to any other point by some group element. Transitive permutation groups are a basic model of homogeneous symmetry.

5.1.1 Regular actions

A regular action is transitive and has trivial point stabilizers. Each group element is determined uniquely by where it sends a chosen point. Regular actions provide a particularly clean link between abstract groups and permutation groups.

5.1.2 Sharply transitive actions

A sharply transitive action is one in which there is exactly one group element sending any given point to any other given point. This is another way to describe regularity in finite settings. Such actions are highly rigid and are often used in combinatorial constructions.

5.2 Primitive groups

A transitive action is primitive if it preserves no nontrivial block system. Primitive groups represent an irreducible form of permutation symmetry. They are a central focus of finite group theory because they often serve as building blocks for more complicated actions.

5.2.1 Criteria for primitivity

Primitivity can be tested by examining stabilizers and possible blocks containing a chosen point. If every block is either a single point or the whole set, the action is primitive. Group-theoretic criteria often involve maximality of point stabilizers or the absence of certain normal subgroups.

5.2.2 Examples of primitive actions

The natural action of the symmetric group on n letters is primitive for n greater than 1. The alternating group in its natural action is also primitive for sufficiently large n. Actions arising from affine or projective geometries often furnish additional classical examples.

5.3 Doubly transitive groups

A group is doubly transitive if it can send any ordered pair of distinct points to any other such pair. This is a stronger condition than transitivity and implies a high degree of symmetry. Doubly transitive groups occur in geometry, design theory, and finite group classification.

5.4 Intransitive and imprimitive groups

An action is intransitive if it has more than one orbit. Intransitive groups decompose the set into separate symmetry components, while imprimitive transitive groups preserve nontrivial blocks. These two forms of reduced symmetry are important for understanding how permutation groups build up from simpler pieces.

6 Structure and properties

Several numerical and structural invariants help describe permutation groups. These include the size of the underlying set, the elements moved by a permutation, and parity distinctions that separate even and odd rearrangements.

6.1 Degree of a permutation group

The degree is the number of points in the set on which the group acts. For a subgroup of S_n, the degree is n in the natural action. Degree is one of the first quantities used to compare different permutation groups.

6.2 Support of a permutation

The support of a permutation is the set of points that are moved by it. A small support indicates that the permutation is localized, while a large support suggests a more extensive rearrangement. Support is useful in studying commutation, generation, and cycle structure.

6.3 Sign of a permutation

The sign, or parity, of a permutation distinguishes even permutations from odd ones. It is determined by whether the permutation can be written as an even or odd number of transpositions. The sign is a homomorphism from the symmetric group to a two-element group.

6.4 Alternating groups

The alternating group is the subgroup of the symmetric group consisting of all even permutations. It is denoted A_n and plays a fundamental role in finite group theory. Alternating groups are simple for n greater than or equal to 5, making them especially important.

6.4.1 Even and odd permutations

An even permutation is one that can be decomposed into an even number of transpositions, while an odd permutation requires an odd number. Although the decomposition into transpositions is not unique, the parity is well defined. This distinction partitions S_n into two equal-sized classes.

6.4.2 Parity homomorphism

The parity homomorphism sends each permutation to its sign. Its kernel is the alternating group. As a group homomorphism, it provides a concise algebraic expression of the even-odd dichotomy among permutations.

7 Subgroups and generated groups

Many permutation groups are studied through the subgroups they contain and the generators that produce them. This perspective is essential for both theoretical analysis and explicit computation.

7.1 Generated permutation groups

A generated permutation group is determined by a set of permutations from which every other element can be obtained by composition and inversion. Generators often give the most compact description of a group. Different generating sets may produce the same group but highlight different structural features.

7.2 Cyclic subgroups

A cyclic subgroup is generated by a single permutation. Its structure is governed by the cycle decomposition of that permutation and the least common multiple of its cycle lengths. Cyclic subgroups are among the simplest examples of permutation groups.

7.3 Normalizers and centralizers

The normalizer of a subgroup consists of elements that conjugate the subgroup to itself, while the centralizer consists of elements that commute with every element of the subgroup. These subgroups measure symmetry of symmetry. In permutation groups, they are often used to study cycle structure and subgroup embeddings.

7.4 Point stabilizer subgroups

Point stabilizers are subgroups that fix a particular point. They play a central role in orbit-stabilizer arguments and in the classification of transitive and primitive actions. Many structural questions about a permutation group reduce to understanding its stabilizers.

Sylow subgroups appear naturally inside symmetric and alternating groups. Their structure can often be described in terms of cycle decompositions and p-power order permutations. These examples illustrate the interaction between the arithmetic of group order and the combinatorics of permutations.

8 Algorithms and computational aspects

Permutation groups are especially well suited to computation because their elements can be manipulated directly as rearrangements. This has made them a major subject in computational algebra.

8.1 Membership testing

Membership testing asks whether a given permutation lies in a subgroup generated by specified elements. This problem is central in computational group theory. Efficient solutions often rely on orbit methods and strong generating sets.

8.2 Schreier–Sims algorithm

The Schreier–Sims algorithm is a foundational method for working with permutation groups. It produces structural data that makes it possible to test membership, compute orders, and handle stabilizer chains efficiently. The algorithm is one of the main practical tools in the field.

8.3 Base and strong generating set

A base is a sequence of points whose pointwise stabilizer is trivial, while a strong generating set is a generating set adapted to a chosen stabilizer chain. Together they provide a compact representation of a permutation group. This framework underlies many fast algorithms for permutation groups.

8.4 Group order computation

The order of a permutation group can be computed by combining stabilizer information along a chain of orbits. For groups given by generators, direct enumeration is usually infeasible, so structured algorithms are essential. Order computations are a standard output of modern algebra systems.

8.5 Orbit algorithms

Orbit algorithms determine the orbit of a point or a set under the action of a group. They are used to find transitivity properties, compute stabilizers, and organize the search space in algorithms. These procedures are among the most basic computational techniques for permutation groups.

9 Applications

Permutation groups appear throughout mathematics wherever symmetry and rearrangement are present. Their applications range from geometry and counting to algebraic equations and algorithmic methods.

9.1 Symmetry in geometry

Geometric objects often have symmetry groups that can be expressed as permutation groups acting on vertices, edges, faces, or other distinguished features. This approach is especially effective for polygons, polyhedra, and finite incidence structures. It turns geometric symmetry into an algebraic problem.

9.2 Combinatorics and counting

Permutation groups are widely used in counting problems through orbit methods and Burnside-type arguments. By analyzing how a group permutes configurations, one can count distinct objects up to symmetry. This makes permutation groups a standard tool in enumerative combinatorics.

9.3 Galois theory

In Galois theory, the symmetries of algebraic roots are encoded by permutation groups. The Galois group of a polynomial acts on its roots and captures essential information about solvability and field extensions. This connection is one of the deepest links between permutations and abstract algebra.

9.4 Design theory

Permutation groups help study combinatorial designs by describing symmetries of blocks and incidence relations. Highly transitive groups often arise in this context because they preserve rich combinatorial structure. Group actions can simplify classification and construction of designs.

9.5 Computational group theory

Permutation groups are a cornerstone of computational group theory because they admit efficient algorithms and concrete data structures. Many algebra systems represent groups by permutations when possible. This representation supports calculation of orbits, stabilizers, subgroup chains, and related invariants.