# Cayley's theorem

{{#invoke:Hatnote|hatnote}}

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, ${\displaystyle 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)):

${\displaystyle (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:

${\displaystyle 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 ${\displaystyle G}$ as a G-set, which can be shown to have permutation representation, say ${\displaystyle \phi }$.

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

Now, the representation is faithful if ${\displaystyle \phi }$ is injective, that is, if the kernel of ${\displaystyle \phi }$ is trivial. Suppose ${\displaystyle g\in \ker \phi }$ Then, ${\displaystyle g=g.e=\phi (g).e}$ by the equivalence of the permutation representation and the group action. But since ${\displaystyle g\in \ker \phi }$, ${\displaystyle \phi (g)=e}$ and thus ${\displaystyle \ker \phi }$ is trivial. Then ${\displaystyle \mathrm {Im} \phi 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)

## Notes

1. Jacobson (2009), p. 38.
2. Jacobson (2009), p. 72, ex. 1.
3. Jacobson (2009), p. 31.
4. {{#invoke:citation/CS1|citation |CitationClass=citation }}
5. {{#invoke:citation/CS1|citation |CitationClass=citation }}
6. {{#invoke:citation/CS1|citation |CitationClass=citation }}
7. {{#invoke:citation/CS1|citation |CitationClass=citation }}

## References

• {{#invoke:citation/CS1|citation

|CitationClass=citation }}.