Cayley's theorem is a foundational result in group theory stating that every group is isomorphic to a subgroup of a symmetric group. More precisely, a group acts on its own underlying set by left multiplication, and this action identifies with a group of permutations of that set. Consequently, every finite group of order can be represented as a subgroup of , the symmetric group on symbols. The theorem connects the abstract definition of a group with the concrete study of permutations.
Statement
Let be a group, with identity element , and let denote the group of all bijections from the underlying set of to itself, with composition as its operation. Cayley's theorem states that there is an injective group homomorphism
Thus,
Here is the image of , a subgroup of the symmetric group. The map is an embedding: it preserves the group operation and distinguishes every pair of distinct group elements.
For a finite group with , choosing a labeling of its elements by identifies with . The theorem then gives
The general statement also applies to infinite groups. In that case, means the full symmetric group of the possibly infinite underlying set, not merely the permutations that move finitely many elements.
Proof by left multiplication
For each , define the left multiplication map
The proof consists of three observations.
Each left multiplication map is a permutation
The inverse of is , since
Therefore is a permutation of the set .
Left multiplication preserves the group operation
Using the convention that the rightmost function is applied first,
Hence the map
is a group homomorphism.
The homomorphism is injective
If , evaluating both functions at the identity gives
Thus is an injective function, and it is an isomorphism from onto its image.
The proof is constructive: a group's multiplication table directly determines a corresponding collection of permutations. Each row of a finite multiplication table lists the images under one left multiplication map.
The regular action
The action
is called the left regular action of . In the language of group actions, it has three important properties:
- Faithfulness: only the identity acts as the identity permutation.
- Transitivity: any element of the underlying set can be carried to any other.
- Freeness: if , then .
The last two properties together imply that for any , exactly one element sends to , namely . Such an action is also called regular or sharply transitive.
Faithfulness is the property that makes the action an embedding. A general group action need not be faithful: different group elements may induce the same permutation.
Right multiplication requires care with composition order. If , then
so reverses multiplication. A right regular embedding compatible with the usual composition convention is instead
Examples
Addition modulo three
Consider the group , whose operation is addition in arithmetic modulo three. Its elements are .
Translation by produces the permutation
written in cycle notation as . Translation by gives . Thus the regular embedding has image
Addition of group elements corresponds exactly to composition of these translations.
The Klein four-group
Let
where each nonidentity element squares to , and . Its left regular embedding sends
These permutations form a subgroup of isomorphic to the original group. Although the original group is an abelian group, its containing symmetric group is not; the embedding preserves the group's own operation without requiring the ambient group to share all its properties.
An infinite group
The additive group of integers embeds into by translations:
For , the permutation moves every integer. This illustrates why the infinite version uses all permutations, including those with infinite support.
Actions on cosets and smaller embeddings
The regular representation is not necessarily the most economical permutation representation. A broader construction uses the set of left cosets of a subgroup .
The rule
defines an action on , the set of left cosets. Here is a set and need not be a quotient group; it is a quotient group only when is normal.
If has finite index , the action gives a homomorphism
Its kernel is
called the core of in . It is the largest normal subgroup of contained in . The action is faithful precisely when this intersection is .
Taking recovers Cayley's regular embedding. A larger subgroup with trivial core may produce an embedding on fewer points.
For example, has six elements, so Cayley's construction embeds it in . Its usual action on three symbols already gives a faithful representation in .
For a finite group , the least size of a finite set admitting a faithful action of is called its minimal faithful permutation degree, often denoted . Cayley's theorem provides the bound
but does not generally determine the minimum.
Significance and applications
Cayley's theorem establishes that permutation groups are universal models for abstract groups. This does not mean every group is itself a full symmetric group: it is isomorphic to a subgroup of one.
The theorem supports several important constructions:
- Concrete descriptions of groups. Abstract elements can be replaced by explicit permutations while preserving multiplication.
- Computational group theory. Finite groups represented by permutation generators can be studied through algorithms for orbits, stabilizers, and subgroup membership. The regular embedding guarantees a representation, although a smaller faithful action may be computationally preferable.
- Linear representations. A permutation of points determines a permutation matrix. Combining this construction with Cayley's theorem gives a faithful representation of every finite group of order by invertible matrices over any field.
- Regular representations. In representation theory, left multiplication permutes a basis indexed by the group elements. This yields the linear regular representation, which is closely related to, but distinct from, the permutation action itself.
The theorem is a representation result rather than a classification theorem. It provides a common setting for all groups, but does not by itself classify finite groups, identify the smallest possible permutation representation, or make every question about a group computationally simple.
Historical context and terminology
The theorem is named after Arthur Cayley, who presented the essential result in an 1854 paper on the theory of groups. It helped connect the emerging abstract conception of a group with the earlier study of groups of substitutions, now called permutation groups.
The name should be distinguished from Cayley's formula in graph theory, which counts labeled trees, and from the Cayley–Hamilton theorem in linear algebra, which states that a square matrix satisfies its own characteristic polynomial.