# Cayley's theorem

For the number of labeled trees in graph theory, see Cayley's formula.

In group theory, Cayley's theorem, named in honour of Arthur Cayley, states that every group G is isomorphic to a subgroup of the symmetric group acting on G.[1] This can be understood as an example of the group action of G on the elements of G.[2]

A permutation of a set G is any bijective function taking G onto G; and the set of all such functions forms a group under function composition, called the symmetric group on G, and written as Sym(G).[3]

Cayley's theorem puts all groups on the same footing, by considering any group (including infinite groups such as (R,+)) as a permutation group of some underlying set. Thus, theorems which are true for subgroups of permutation groups are true for groups in general.

## History

Although Burnside[4] attributes the theorem to Jordan,[5] Eric Nummela[6] nonetheless argues that the standard name—"Cayley's Theorem"—is in fact appropriate. Cayley, in his original 1854 paper,[7] showed that the correspondence in the theorem is one-to-one, but he failed to explicitly show it was a homomorphism (and thus an isomorphism). However, Nummela notes that Cayley made this result known to the mathematical community at the time, thus predating Jordan by 16 years or so.

## Proof of the theorem

Where g is any element of a group G with operation ∗, consider the function fg : GG, defined by fg(x) = gx. By the existence of inverses, this function has a two-sided inverse, $f_{g^{-1}}$. So multiplication by g acts as a bijective function. Thus, fg is a permutation of G, and so is a member of Sym(G).

The set K = {fg : gG} is a subgroup of Sym(G) that is isomorphic to G. The fastest way to establish this is to consider the function T : G → Sym(G) with T(g) = fg for every g in G. T is a group homomorphism because (using · to denote composition in Sym(G)):

$(f_g \cdot f_h)(x) = f_g(f_h(x)) = f_g(h*x) = g*(h*x) = (g*h)*x = f_{g*h}(x) ,$

for all x in G, and hence:

$T(g) \cdot T(h) = f_g \cdot f_h = f_{g*h} = T(g*h) .$

The homomorphism T is also injective since T(g) = idG (the identity element of Sym(G)) implies that gx = x for all x in G, and taking x to be the identity element e of G yields g = ge = e. Alternatively, T is also injective since, if gx = g′ ∗ x implies that g = g (because every group is cancellative).

Thus G is isomorphic to the image of T, which is the subgroup K.

T is sometimes called the regular representation of G.

### Alternative setting of proof

An alternative setting uses the language of group actions. We consider the group $G$ as a G-set, which can be shown to have permutation representation, say $\phi$.

Firstly, suppose $G=G/H$ with $H=\{e\}$. Then the group action is $g.e$ by classification of G-orbits (also known as the orbit-stabilizer theorem).

Now, the representation is faithful if $\phi$ is injective, that is, if the kernel of $\phi$ is trivial. Suppose $g\in\ker\phi$ Then, $g=g.e=\phi(g).e$ by the equivalence of the permutation representation and the group action. But since $g \in \ker\phi$, $\phi(g)=e$ and thus $\ker\phi$ is trivial. Then $\mathrm{Im} \phi < G$ and thus the result follows by use of the first isomorphism theorem.

## Remarks on the regular group representation

The identity group element corresponds to the identity permutation. All other group elements correspond to a permutation that does not leave any element unchanged. Since this also applies for powers of a group element, lower than the order of that element, each element corresponds to a permutation which consists of cycles which are of the same length: this length is the order of that element. The elements in each cycle form a left coset of the subgroup generated by the element.

## Examples of the regular group representation

Z2 = {0,1} with addition modulo 2; group element 0 corresponds to the identity permutation e, group element 1 to permutation (12). E.g. 0 +1 = 1 and 1+1 = 0, so 1 -> 0 and 0 -> 1, as they would under a permutation.

Z3 = {0,1,2} with addition modulo 3; group element 0 corresponds to the identity permutation e, group element 1 to permutation (123), and group element 2 to permutation (132). E.g. 1 + 1 = 2 corresponds to (123)(123)=(132).

Z4 = {0,1,2,3} with addition modulo 4; the elements correspond to e, (1234), (13)(24), (1432).

The elements of Klein four-group {e, a, b, c} correspond to e, (12)(34), (13)(24), and (14)(23).

S3 (dihedral group of order 6) is the group of all permutations of 3 objects, but also a permutation group of the 6 group elements:

* e a b c d f permutation
e e a b c d f e
a a e d f b c (12)(35)(46)
b b f e d c a (13)(26)(45)
c c d f e a b (14)(25)(36)
d d c a b f e (156)(243)
f f b c a e d (165)(234)