Group actions: Permutation representations

A group action of a group \(G\) on a set \(A\) is a function \(\varphi : G \times A \to A\) satisfying the following properties (here \(\varphi(g,a)\) will be denoted by \(g \cdot a\) and so we shall dispense with \(\varphi\) altogether):

1. \(g \cdot (h \cdot a) = (gh) \cdot a\) for all \(g,h \in G\), \(a \in A\)
2. \(1 \cdot a = a\) for all \(a \in A\)

A fundamental result is the existence of a bijection between group actions and homomorphisms \(\phi\) from \(G\) to \(S_A\).

Let \(g \in G\) be arbitrary. The function \(\sigma_g\) is defined such that \(\sigma_g(a) = g \cdot a\) for all \(a \in A\). We can verify that \(\sigma_g\) is a permutation of \(A\): since \((\sigma_g\sigma_{g^{-1}})(a) = \sigma_g(\sigma_{g^{-1}}(a)) = g \cdot (g^{-1} \cdot a) = (gg^{-1}) \cdot a = a\) for all \(a \in A\), \(\sigma_g\sigma_{g^{-1}}\) is precisely the identity permutation. Thus \(\sigma_g\) has an inverse (namely \(\sigma_{g^{-1}}\)), and so it is a bijection in \(A\). Now, we can define the function \(\phi : g \to \sigma_g\) mapping \(G\) to \(S_A\), and show that it is indeed a homomorphism: \(\phi(gh)(a) = \sigma_{gh}(a) = (gh) \cdot a = g \cdot (h \cdot a) = (\sigma_g\sigma_h)(a) = (\phi(g)\phi(h))(a)\) for all \(a \in A\).

So far we have established the existence of a homomorphism \(\phi : G \to S_A\) for any group action. What remains is to prove the existence of a group action  given a homomorphism \(\phi\). This is in fact rather trivial: simply define \(g \cdot a = \phi(g)(a)\); it is easy to check that the properties of group actions are satisfied. In light of this result, we can say that a group action affords or induces the associated permutation representation \(\phi\).

We can proceed by defining the left regular representation of \(G\) to be the permutation representation afforded by the action of the group \(G\) on the set \(G\) by left multiplication (meaning that \(g \cdot h = gh\)). Similarly we can define right regular representations (where \(g \cdot h = hg\)). Given the intimate relation between operations on group elements and permutations, the following result seems quite natural:

(Cayley's Theorem) Every group of order \(n\) is isomorphic to a subgroup of \(S_n\).