Cayley's Theorem

This article is about a sentence from group theory. A theorem in graph theory named after Cayley can be found under Cayley's formula .

The set of Cayley is after the English mathematician Arthur Cayley named set from the algebra . It says that each group can be realized as a subgroup of a symmetrical group .

This result played an important role in the development of group theory in the 19th century, because it ensures that every abstract group is isomorphic to a concrete group of permutations. In other words, each group can be faithfully represented as a permutation group . Cayley's theorem thus forms a starting point for representation theory , which examines a given group by using its representations on concrete and well-understood groups.

Statement of the sentence

Cayley's theorem says:

Each group is isomorphic to a subgroup of a symmetric group .

In more detail, this means the following:

Be a group. Then there exists a set and in the symmetric group a subgroup such that is isomorphic to . ${\displaystyle (G,*)}$ ${\displaystyle M}$ ${\displaystyle \mathrm {Sym} (M)}$ ${\displaystyle U}$ ${\displaystyle (G,*)}$ ${\displaystyle (U,\circ )}$

If the given group is also finite, one can choose a finite set for it. More precisely: If is of order , then is isomorphic to a subgroup of . ${\displaystyle G}$ ${\displaystyle M}$ ${\displaystyle G}$ ${\displaystyle n}$ ${\displaystyle G}$ ${\displaystyle S_{n}}$

Applications

The practical meaning of Cayley's theorem is to represent any group as a subgroup of a specific group. As a concrete group we consider a symmetrical group consisting of all bijective images of a set in itself. The link in the symmetrical group is given by the sequential execution . Permutation groups are very useful in the sense that their elements (the permutations ) can be conveniently written down and easily calculated. This is particularly useful in computer algebra . ${\displaystyle G}$ ${\displaystyle \mathrm {Sym} (M)}$ ${\displaystyle M}$ ${\displaystyle \mathrm {Sym} (M)}$ ${\displaystyle (f\circ g)(x):=f(g(x))}$

At the theoretical level, Cayley's theorem opens up the possibility of applying the theory of permutation groups to any group. One speaks of a permutation representation of the given group. There are also other ways of representing groups in a special form, for example as a matrix group, i.e. as a subgroup of a linear group. One then speaks of a linear representation , see also the article Representation theory (group theory) .

Proof of the theorem

Before the actual proof, it is worthwhile to illustrate the essential idea with a simple example. The following proof then only formulates the observations made.

Introductory example

To illustrate this, let us consider Klein's group of four , which we represent here by the set with the following table : ${\displaystyle (V,*)}$ ${\displaystyle V=\{1,2,3,4\}}$

${\displaystyle *}$	1	2	3	4th
1	1	2	3	4th
2	2	1	4th	3
3	3	4th	1	2
4th	4th	3	2	1

In the first line we see the permutation and in the following lines the permutations , , . These permutations are different from one another, so the mapping with is injective. You can then directly recalculate that a group homomorphism is, i.e. fulfilled for all . This follows quite generally from the group axioms, as we shall now show. ${\displaystyle \tau _{1}={\bigl (}{\begin{smallmatrix}1&2&3&4\\1&2&3&4\end{smallmatrix}}{\bigr )}}$ ${\displaystyle \tau _{2}={\bigl (}{\begin{smallmatrix}1&2&3&4\\2&1&4&3\end{smallmatrix}}{\bigr )}}$ ${\displaystyle \tau _{3}={\bigl (}{\begin{smallmatrix}1&2&3&4\\3&4&1&2\end{smallmatrix}}{\bigr )}}$ ${\displaystyle \tau _{4}={\bigl (}{\begin{smallmatrix}1&2&3&4\\4&3&2&1\end{smallmatrix}}{\bigr )}}$ ${\displaystyle T\colon V\to S_{4}}$ ${\displaystyle a\mapsto \tau _{a}}$ ${\displaystyle T}$ ${\displaystyle T(a*b)=T(a)\circ T(b)}$ ${\displaystyle a,b\in V}$

General construction

Be a group. We choose the amount . For each group element we define a mapping by . This mapping is called left multiplication with . ${\displaystyle (G,*)}$ ${\displaystyle M:=G}$ ${\displaystyle a\in G}$ ${\displaystyle \tau _{a}\colon M\to M}$ ${\displaystyle \tau _{a}(x):=a*x}$ ${\displaystyle a}$

1. Associativity for all and is synonymous with . ${\displaystyle a*(b*x)=(a*b)*x}$ ${\displaystyle a,b\in G}$ ${\displaystyle x\in M}$ ${\displaystyle \tau _{a}\circ \tau _{b}=\tau _{a*b}}$
2. The fact that the neutral element is, i.e. fulfilled for all , is synonymous with . ${\displaystyle e\in G}$ ${\displaystyle e*x=x}$ ${\displaystyle x\in M}$ ${\displaystyle \tau _{e}=\mathrm {id} _{M}}$
3. Are mutually inverse elements, so it follows . ${\displaystyle a,b\in G}$ ${\displaystyle a*b=e}$ ${\displaystyle \tau _{a}\circ \tau _{b}=\tau _{a*b}=\tau _{e}=\mathrm {id} _{M}}$

Since all elements in a group can be inverted, each of the images is bijective . So we get a group homomorphism by . This homomorphism is injective: if , then in particular and therefore holds . So there is an isomorphism between the group and the subgroup . ${\displaystyle G}$ ${\displaystyle \tau _{a}}$ ${\displaystyle T\colon G\to \mathrm {Sym} (M)}$ ${\displaystyle T(a)=\tau _{a}}$ ${\displaystyle \tau _{a}=\tau _{b}}$ ${\displaystyle \tau _{a}(e)=\tau _{b}(e)}$ ${\displaystyle a=a*e=b*e=b}$ ${\displaystyle T}$ ${\displaystyle G}$ ${\displaystyle U=\mathrm {Bild} (T)=\{\tau _{a}\mid a\in G\}=\{\sigma \in \mathrm {Sym} (M)\mid \forall x\in M:\sigma (x)=\sigma (e)*x\}}$

Remarks

The above proof is based on the observation that left multiplication is a group operation of the group on itself, namely with . He then shows that every group operation induces a group homomorphism . In the special case of left multiplication, it is even injective and is called the (left) regular representation . ${\displaystyle G}$ ${\displaystyle G\times G\to G}$ ${\displaystyle (g,x)\mapsto g*x}$ ${\displaystyle G\times M\to M}$ ${\displaystyle T\colon G\to \mathrm {Sym} (M)}$ ${\displaystyle T}$

The proof can be carried out in the same way if one uses the right multiplication with the inverse instead of the left multiplication. Under certain circumstances it then delivers another subgroup of , which, however, is also isomorphic to . ${\displaystyle \mathrm {Sym} (G)}$ ${\displaystyle G}$

Minimal permutation representations

Instead of the set used in the proof above , one can often find smaller sets. For example, the proof provides a representation of the alternating group with elements as a subgroup of , although the set would be sufficient as a basic set , because we have the inclusion . ${\displaystyle M=G}$ ${\displaystyle A_{4}}$ ${\displaystyle 12}$ ${\displaystyle S_{12}}$ ${\displaystyle \{1,2,3,4\}}$ ${\displaystyle M}$ ${\displaystyle A_{4}\hookrightarrow S_{4}}$

For a given group , one can therefore ask at what level an injective group homomorphism exists (also called true permutation representation or embedding - see also the article permutation group for the questions described in this section ). The sentence makes it clear that this is always possible for in any case. It is an interesting and sometimes difficult question to determine the minimum degree to which this is possible. ${\displaystyle G}$ ${\displaystyle n}$ ${\displaystyle G\hookrightarrow S_{n}}$ ${\displaystyle n=|G|}$ ${\displaystyle m(G)}$

Interestingly, there are groups for whom the regular representation is already minimal, ie . For such a group there are only embeddings for . This applies, for example, to every cyclic group of prime order, because no symmetric group with contains an element of the order ( Lagrange's theorem ). The same applies to every cyclic group whose order is a prime power: no symmetric group with contains an element of the order . (This follows from the decomposition of a permutation into a product of disjoint cycles .) The small group of four of the order can also be embedded in but not in (also according to Lagrange's theorem). The following result provides a complete overview: ${\displaystyle G}$ ${\displaystyle m(G)=|G|}$ ${\displaystyle G\hookrightarrow S_{n}}$ ${\displaystyle n\geq |G|}$ ${\displaystyle \mathbb {Z} /p}$ ${\displaystyle S_{k}}$ ${\displaystyle k<p}$ ${\displaystyle p}$ ${\displaystyle \mathbb {Z} /p^{k}}$ ${\displaystyle S_{k}}$ ${\displaystyle k<p^{n}}$ ${\displaystyle p^{n}}$ ${\displaystyle \mathbb {Z} /2\times \mathbb {Z} /2}$ ${\displaystyle 4}$ ${\displaystyle S_{4}}$ ${\displaystyle S_{3}}$

The regular display is already minimal for the following groups , i.e. there are only embeddings for : ${\displaystyle G}$ ${\displaystyle G\hookrightarrow S_{n}}$ ${\displaystyle n\geq |G|}$

1. ${\displaystyle \mathbb {Z} /2\times \mathbb {Z} /2}$, the small group of four.
2. ${\displaystyle \mathbb {Z} /p^{k}}$, a cyclic group whose order is a prime power.
3. ${\displaystyle Q_{2^{k}}}$, a generalized quaternion group of the order with . ${\displaystyle 2^{k}}$ ${\displaystyle k\geq 3}$

In cases (2) and (3), every embedding with is conjugated to the regular representation. ${\displaystyle G\hookrightarrow S_{n}}$ ${\displaystyle n=|G|}$

Conversely, if the regular representation is minimal for a finite group , then a group is from this list. For all other groups, the degree from Cayley's Theorem can be reduced. ${\displaystyle G}$ ${\displaystyle G}$ ${\displaystyle n=|G|}$

history

The sentence is generally attributed to Arthur Cayley , who formulated the basic idea as early as 1854 in one of the first articles in group theory. However, William Burnside, in his book on group theory, attributes the full evidence to Camille Jordan in 1870. However, Eric Nummela argues that the usual designation as Cayley's theorem is entirely correct: Cayley had shown in his work of 1854 that the above mapping is injective into the symmetric group, even if he has not explicitly shown that it is a group homomorphism .

Individual evidence

1. ^ David L. Johnson: Minimal permutation representations of finite groups . In: American Journal of Mathematics . 93, 1971, pp. 857-866.
2. ↑ Arthur Cayley : On the theory of groups as depending on the symbolic equation θ ⁿ = 1 . In: Phil. Mag . 7, No. 4, 1854, pp. 40-47.
3. ^ William Burnside: Theory of Groups of Finite Order , 2nd edition 1911.
4. ↑ Camille Jordan: Traité des substitutions et des equations algébriques . Gauthier-Villars, Paris 1870.
5. ↑ Eric Nummela: Cayley's Theorem for Topological Groups . In: American Mathematical Monthly . 87, No. 3, 1980, pp. 202-203. doi : 10.2307 / 2321608 .