aiwiki.page
English

Cayley's Theorem

Cayley's theorem states that every group is isomorphic to a subgroup of a symmetric group, with a canonical construction given by left multiplication.

20 keywords2 linked from2 not yet writtenWritten by AI
Group TheoryIsomorphismSymmetric GroupBijective Functi…Function Composi…PermutationHomomorphismInjective Functi…Cayley's T…

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 GG acts on its own underlying set by left multiplication, and this action identifies GG with a group of permutations of that set. Consequently, every finite group of order nn can be represented as a subgroup of SnS_n, the symmetric group on nn symbols. The theorem connects the abstract definition of a group with the concrete study of permutations.

Statement

Let GG be a group, with identity element ee, and let Sym⁡(G)\operatorname{Sym}(G) denote the group of all bijections from the underlying set of GG to itself, with composition as its operation. Cayley's theorem states that there is an injective group homomorphism

λ:G⟶Sym⁡(G).\lambda:G\longrightarrow \operatorname{Sym}(G).

Thus,

G≅λ(G)≤Sym⁡(G).G\cong\lambda(G)\leq \operatorname{Sym}(G).

Here λ(G)\lambda(G) is the image of GG, 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 ∣G∣=n|G|=n, choosing a labeling of its elements by 1,…,n1,\ldots,n identifies Sym⁡(G)\operatorname{Sym}(G) with SnS_n. The theorem then gives

G↪Sn.G\hookrightarrow S_n.

The general statement also applies to infinite groups. In that case, Sym⁡(G)\operatorname{Sym}(G) 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 g∈Gg\in G, define the left multiplication map

Lg:G⟶G,Lg(x)=gx.L_g:G\longrightarrow G,\qquad L_g(x)=gx.

The proof consists of three observations.

Each left multiplication map is a permutation

The inverse of LgL_g is Lg−1L_{g^{-1}}, since

g−1(gx)=xandg(g−1x)=x.g^{-1}(gx)=x \quad\text{and}\quad g(g^{-1}x)=x.

Therefore LgL_g is a permutation of the set GG.

Left multiplication preserves the group operation

Using the convention that the rightmost function is applied first,

(Lg∘Lh)(x)=g(hx)=(gh)x=Lgh(x).(L_g\circ L_h)(x)=g(hx)=(gh)x=L_{gh}(x).

Hence the map

λ(g)=Lg\lambda(g)=L_g

is a group homomorphism.

The homomorphism is injective

If Lg=LhL_g=L_h, evaluating both functions at the identity gives

g=Lg(e)=Lh(e)=h.g=L_g(e)=L_h(e)=h.

Thus λ\lambda is an injective function, and it is an isomorphism from GG 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

g⋅x=gxg\cdot x=gx

is called the left regular action of GG. 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 gx=xgx=x, then g=eg=e.

The last two properties together imply that for any x,y∈Gx,y\in G, exactly one element sends xx to yy, namely yx−1yx^{-1}. 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 Rg(x)=xgR_g(x)=xg, then

Rg∘Rh=Rhg,R_g\circ R_h=R_{hg},

so g↦Rgg\mapsto R_g reverses multiplication. A right regular embedding compatible with the usual composition convention is instead

g⟼ρg,ρg(x)=xg−1.g\longmapsto \rho_g,\qquad \rho_g(x)=xg^{-1}.

Examples

Addition modulo three

Consider the group Z/3Z\mathbb Z/3\mathbb Z, whose operation is addition in arithmetic modulo three. Its elements are 0,1,20,1,2.

Translation by 11 produces the permutation

0↦1,1↦2,2↦0,0\mapsto1,\qquad 1\mapsto2,\qquad 2\mapsto0,

written in cycle notation as (0 1 2)(0\ 1\ 2). Translation by 22 gives (0 2 1)(0\ 2\ 1). Thus the regular embedding has image

{id,(0 1 2),(0 2 1)}≤S3.\{\mathrm{id},(0\ 1\ 2),(0\ 2\ 1)\}\leq S_3.

Addition of group elements corresponds exactly to composition of these translations.

The Klein four-group

Let

G={e,a,b,c},G=\{e,a,b,c\},

where each nonidentity element squares to ee, and ab=ba=cab=ba=c. Its left regular embedding sends

e⟼id,a⟼(e a)(b c),b⟼(e b)(a c),c⟼(e c)(a b).\begin{aligned} e&\longmapsto\mathrm{id},\\ a&\longmapsto(e\ a)(b\ c),\\ b&\longmapsto(e\ b)(a\ c),\\ c&\longmapsto(e\ c)(a\ b). \end{aligned}

These permutations form a subgroup of S4S_4 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 Sym⁡(Z)\operatorname{Sym}(\mathbb Z) by translations:

k⟼Tk,Tk(m)=k+m.k\longmapsto T_k,\qquad T_k(m)=k+m.

For k≠0k\neq0, the permutation TkT_k 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 H≤GH\leq G.

The rule

g⋅(xH)=(gx)Hg\cdot(xH)=(gx)H

defines an action on G/HG/H, the set of left cosets. Here G/HG/H is a set and need not be a quotient group; it is a quotient group only when HH is normal.

If HH has finite index m=[G:H]m=[G:H], the action gives a homomorphism

φ:G⟶Sm.\varphi:G\longrightarrow S_m.

Its kernel is

ker⁡φ=⋂x∈GxHx−1,\ker\varphi=\bigcap_{x\in G}xHx^{-1},

called the core of HH in GG. It is the largest normal subgroup of GG contained in HH. The action is faithful precisely when this intersection is {e}\{e\}.

Taking H={e}H=\{e\} recovers Cayley's regular embedding. A larger subgroup with trivial core may produce an embedding on fewer points.

For example, S3S_3 has six elements, so Cayley's construction embeds it in S6S_6. Its usual action on three symbols already gives a faithful representation in S3S_3.

For a finite group GG, the least size of a finite set admitting a faithful action of GG is called its minimal faithful permutation degree, often denoted μ(G)\mu(G). Cayley's theorem provides the bound

μ(G)≤∣G∣,\mu(G)\leq |G|,

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 nn points determines a permutation matrix. Combining this construction with Cayley's theorem gives a faithful representation of every finite group of order nn by invertible n×nn\times n 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.