Cayley's Theorem: Every Group Is a Group of Permutations in Disguise

The abstract concept of a group — a set with a single binary operation satisfying four short axioms — turns out to describe a startling variety of mathematical objects. Rotations and reflections of a regular polygon form a group. Invertible matrices of fixed size form a group. The integers under addition form a group. Modular arithmetic forms a group. Continuous deformations of geometric shapes form a group. The Galois group of a polynomial extension is a group. The fundamental group of a topological space is a group.

What do all these examples have in common, beyond the four axioms? At first glance, very little. They look like wildly different objects studied by mathematicians working in unrelated fields.

The remarkable answer, proved by Arthur Cayley in 1854, is that they are all, secretly, examples of the same thing. Every group, no matter how abstract or unusual, can be realised as a group of permutations — a subgroup of the symmetric group acting on some set. The symmetric groups are, in this sense, the universal examples: every group is a symmetric group in disguise.

This is Cayley’s theorem, one of the first major structural results of modern group theory, and the conceptual moment when “group theory” emerged from being a study of specific examples (rotations, permutations of roots, matrix groups) and became a general study of abstract algebraic structures. This article is about what the theorem says, why it works, and what it does (and does not) tell us.

The statement

Let $G$ be a group. The symmetric group $\mathrm{Sym}(X)$ on a set $X$ is the group of all bijections from $X$ to itself, with composition as the operation. Cayley’s theorem says:

There is an injective group homomorphism $\rho : G \to \mathrm{Sym}(G)$ .

In other words, $G$ is isomorphic to a subgroup of the group of permutations of itself (treated as a set). For finite $G$ of order $n$ , this means $G$ embeds in the symmetric group $S_n$ . For infinite $G$ , the conclusion is the same — $G$ embeds in the symmetric group on its underlying set.

The map $\rho$ is given by left multiplication: for each $g \in G$ , define the function $\rho(g) : G \to G$ by

$\rho(g)(x) \;=\; g \cdot x \quad \text{for all } x \in G.$

This is a permutation of $G$ — it is a bijection because $\rho(g^{-1})$ is its inverse. And it respects the group operation: $\rho(gh)(x) = (gh) x = g(hx) = \rho(g)(\rho(h)(x))$ , so $\rho(gh) = \rho(g) \circ \rho(h)$ . So $\rho$ is a group homomorphism. It is injective because if $\rho(g)$ is the identity permutation, then $g \cdot x = x$ for all $x$ , which forces $g$ to be the identity element of $G$ .

That is the entire proof: identify each $g \in G$ with the permutation “multiply by $g$ from the left”. The collection of such permutations is a subgroup of $\mathrm{Sym}(G)$ , and it is isomorphic to $G$ .

A worked example

Take $G = \mathbb{Z}/4\mathbb{Z}$ , the cyclic group of order $4$ with elements $\{0, 1, 2, 3\}$ and addition modulo $4$ . Then for each $g \in G$ , the left-multiplication map sends $x \mapsto g + x$ :

$\rho(0)$ is the identity permutation $(0, 1, 2, 3) \mapsto (0, 1, 2, 3)$ .
$\rho(1)$ sends $(0, 1, 2, 3) \mapsto (1, 2, 3, 0)$ — a cyclic shift.
$\rho(2)$ sends $(0, 1, 2, 3) \mapsto (2, 3, 0, 1)$ — a double shift.
$\rho(3)$ sends $(0, 1, 2, 3) \mapsto (3, 0, 1, 2)$ — a triple shift.

So $\mathbb{Z}/4$ is identified with the subgroup of $S_4$ consisting of cyclic shifts by $0, 1, 2, 3$ positions. This is a cyclic subgroup of $S_4$ of order $4$ .

The picture shows the four permutations of $\{0, 1, 2, 3\}$ produced by the Cayley embedding. The identity element gives the identity permutation; the element $1$ gives a 4-cycle; the element $2$ gives a product of two 2-cycles; the element $3$ gives a 4-cycle in the opposite direction. Together, these four permutations form a subgroup of $S_4$ isomorphic to $\mathbb{Z}/4$ .

The same construction works for any group. A group of order $n$ embeds into $S_n$ via the left-multiplication action. So group theory, in some sense, can be reduced to the theory of subgroups of symmetric groups.

Why the theorem matters

Cayley’s theorem has several significant consequences for the theory of groups.

Universality of symmetric groups. It establishes the symmetric groups $S_n$ (for $n = 1, 2, 3, \dots$ ) as universal examples for finite group theory: every finite group is a subgroup of some $S_n$ . This is structurally analogous to the way every vector space embeds in some standard space $\mathbb{R}^n$ (or its infinite-dimensional analog), or every metric space embeds in some Banach space. The presence of “universal examples” is a sign that the abstract theory is captured by concrete cases.

Abstract group theory is well-defined. Cayley’s theorem confirms that the abstract definition of a group (a set with one binary operation satisfying four axioms) does not produce anything stranger than concrete groups of permutations. Whatever you can prove about general abstract groups, you could in principle prove by working with permutations. This was historically important because in the mid-19th century, mathematicians were uncertain whether the axiomatic definition of a group was studying something real or just a formal exercise. Cayley’s theorem proved that the abstract definition is exactly the right one.

Computational tools. For finite groups, Cayley’s embedding gives a concrete representation by permutations, which can be manipulated by computer. Computer algebra systems for group theory (GAP, Magma) use permutation representations as one of their fundamental data structures, and Cayley’s construction underlies the most basic version of these.

Cayley diagrams (Cayley graphs). The same idea — represent a group by its action on itself — leads to the construction of Cayley graphs: vertices labelled by group elements, edges labelled by generators. Cayley graphs are central tools in geometric group theory, in coding theory (where they produce expander graphs), and in algorithm analysis (random walks on Cayley graphs give the foundations of many randomised algorithms).

What the theorem does not give

Cayley’s theorem is an existence theorem, not an efficiency theorem. The embedding $G \hookrightarrow S_n$ for $|G| = n$ usually requires the very large symmetric group $S_n$ , which has order $n!$ . For most groups, much smaller permutation representations exist.

For example, the cyclic group $\mathbb{Z}/n$ embeds into $S_n$ by Cayley’s construction, but also embeds into $S_{m}$ for any $m \geq \log_2 n$ via more clever embeddings. The smallest $m$ such that $G$ embeds in $S_m$ is called the minimal degree of $G$ , and finding it is an active research problem. The Frobenius–Burnside theorem and related results give bounds, but the exact minimal degree depends delicately on the group structure.

Similarly, beyond permutation groups, the theory of representations of groups by matrices (rather than by permutations) often gives much more efficient embeddings — and the rich theory of representations is one of the most active branches of modern algebra. Cayley’s theorem is the original ancestor of representation theory, with permutations as the basic representations.

The historical moment

Cayley’s 1854 paper, “On the theory of groups, as depending on the symbolic equation $\theta^n = 1$ ,” is one of the most influential short papers in the history of algebra. In it, Cayley:

Gave the abstract definition of a group in essentially modern form.
Proved his theorem — every group is a group of permutations.
Constructed multiplication tables (now called Cayley tables) as a tool for studying groups.
Began the systematic study of small groups, identifying the groups of orders up to about $6$ .

Before Cayley, “group theory” had meant the study of specific types of groups — permutation groups, in Galois’s theory of polynomial equations; rotation groups, in the geometry of regular polyhedra; transformation groups, in the work of Sophus Lie on continuous symmetries. After Cayley, “group theory” became a unified abstract subject, in which all these examples were special cases of a single theory governed by four short axioms. The shift was epoch-defining: it inaugurated modern abstract algebra, with consequences that ramified through the subsequent two centuries of mathematics.

A theorem that organised a subject

What Cayley’s theorem accomplished is something every mathematician hopes to do at least once: it gave a unifying result that organised a field of study. Before 1854, group theory was a list of distinct examples. After 1854, group theory was the study of a single abstract concept whose universal examples were the symmetric groups.

The same kind of move recurs throughout mathematics. The Yoneda lemma plays a similar organising role in category theory: every category embeds in a category of functors. The Cayley–Hamilton theorem does it within linear algebra: every matrix satisfies its own characteristic polynomial. Each of these is, in its own subject, the analogous foundational result — the moment when the abstract definition is shown to be no broader than the concrete examples, and the subject becomes a study of those examples organised by their abstract structure.

For group theory, Cayley’s theorem was that moment. Every group is, secretly, a permutation group. From this innocent-looking observation in 1854 grew the abstract algebra of the next two centuries.

Frequently asked

Who was Arthur Cayley?

Arthur Cayley was a 19th-century British mathematician who, alongside James Joseph Sylvester, founded modern algebraic theory. He published nearly a thousand papers in his lifetime, an extraordinary output for the era. The theorem now bearing his name appeared in an 1854 paper that effectively defined the abstract concept of a group for the first time in print — the modern definition, where a group is a set with a binary operation satisfying four axioms, is essentially Cayley's. He spent much of his career at the University of Cambridge as the first Sadleirian Professor of Pure Mathematics.

What does the theorem actually say?

Every group G is isomorphic to a subgroup of the symmetric group of permutations of G itself. That is: there is a homomorphism from G to the group of permutations of G that is injective. Concretely, each element g of G corresponds to the permutation 'left multiplication by g', which is indeed a bijection of G to itself, and the assignment g ↦ left-multiplication-by-g preserves the group structure. So every group, no matter how abstract, can be realised as a concrete group of permutations of some set.

Why is this surprising?

Because group theory at first glance seems to study many different sorts of objects — rotations of polygons, invertible matrices, modular arithmetic, even continuous deformations of geometric shapes. Cayley's theorem asserts that all of these are, structurally, examples of the same kind of thing: permutation groups. It is one of the first results in group theory to show that abstract algebra has a unifying simplicity hiding behind the diversity of concrete examples. The symmetric group is, in this precise sense, universal.

Is the embedding ever efficient in practice?

Not very. A group of order n embeds in S_n by Cayley's construction — but S_n has order n!, which is astronomically larger than n. For most finite groups, the Cayley embedding is wildly inefficient. Better embeddings come from representation theory: many groups embed in much smaller permutation groups (or in matrix groups), and finding the smallest faithful permutation representation is a delicate problem. Cayley's theorem is a beautiful existence result; the search for efficient embeddings is a subject in its own right.

Cayley's Theorem: Every Group Is a Group of Permutations in Disguise

The statement

A worked example

Why the theorem matters

What the theorem does not give

The historical moment

A theorem that organised a subject

Frequently asked

Continue reading

The 15 Puzzle: How a Simple Sign Proves Half of All Positions Are Impossible

Sylow's Theorems: The Hidden Architecture of Finite Groups

Burnside's Lemma: Counting Things When Symmetry Says Some of Them Are the Same

Keep exploring