Group actions and permutation groups

Group actions

One of the most basic concepts of group theory is that of a group action. Informally we let a group act on a set by assigning a map (or function) from the set to itself to each element of the group. You may have heard that group theory is in some sense the study of symmetry; in order to unpack what this means we need to understand group actions.

The formal definition of a group action is a follows:

Let $G$ be a group and $\Omega$ be a set. Then $G$ acts on $\Omega$ if there exists some $\cdot : G \times \Omega \to \Omega$ such that:

(1) $1 \cdot x = x$ for all $x \in \Omega$

(2)$(gh) \cdot x = g \cdot (h \cdot x)$ for all $g,h\in G$ and $x \in \Omega$.

In a sense we are turning $G$ into a collection of functions from $\Omega$ to itself where the identity in $G$ becomes the identity function on $\Omega$, and the composition of two functions on $\Omega$ is just their product in $G$. We will sometimes write $g \cdot x$ as $x^g$.

The first and most obvious example of a group action is any group $G$ acting on itself by left multiplication (remember a group is just a set with extra structure, so a group can act on itself). By left multiplication we mean that for $g, h \in G$, $g \cdot h$ is simply $gh$.

Another common action of a group on itself is conjugation. Here we have $g \cdot h$ = $ghg^{-1}$. You can check that both of these actions satisfy (1) and (2) above.

For an action where the set is not the same as the group we first choose $\Omega = \{1,2,...,n\}$ for some natural number $n$. We define the nth symmetric group $S_n$ to be the group of all permutations of $\Omega$: functions that send each element of $\Omega$ to some other unique element. We call such a function a bijection. 

For example, consider the permutation of $\{1,2,3\}$ that switches $1$ with $2$ and thus necessarily fixes $3$. This will be an element of $S_3$; we normally write this as $(1,2)$. Then this element acts on $\{1,2,3\}$ in the obvious way: we have $(1,2) \cdot 1 = 2$,  $(1,2) \cdot 2 = 1$, and $(1,2) \cdot 3 = 3$. In a similar way we see that $S_n$ acts on $\{1,2,...,n\}$. This is the most simple example of a permutation group.

Permutation groups

Permutation groups are a very natural construction in group theory; they were in a sense the reason that group theory was created. Mathematicians originally came up with the idea of a group in order to describe collections of roots of polynomials: certain constructions swapped around (permuted) the roots of these polynomials in certain ways. The collections of all of the ways that these roots could be permuted were the first groups.

Formally a permutation group is a group acting on a set where the actions of each element are all bijections like above. Permutation groups can be very intuitive: we have a collection of things and we want to know how we can permute those things while preserving some structure.

The largest permutation group acting on $n$ points is the symmetric group $S_n$ described above. This is just the set of all possible permutation of the $n$ points. Another example of a permutation group are the dihedral groups $D_n$. These are thought of as the possible permutations of the vertices of the $n$-sided polygon. 

For example we can consider $D_4$: the symmetries of the square. This group has 8 elements: rotations by 0, 90, 180, and 270 degrees, and reflections in the diagonals and perpendicular lines through the centre of the square. Note that we need to include the rotation by 0 degrees as an element: a group always needs an identity element. 

We can see now that $D_4$ will be contained within $S_4$ as every symmetry of the square can be thought of as a permutation of the vertices. However $D_4$ is not equal to $S_4$. This is because the permutation that swaps any two vertices will be in $S_4$, but if those vertices are adjacent on the square this permutation will not be given by a reflection or a rotation and hence will not be in $D_4$. In general $D_n$ will contain $n$ reflection and $n$ rotations, and hence have $2n$ elements. It will be contained within $S_n$ which has $n!$ elements.

Every group, in fact, can be thought of as a permutation group as a result something called Cayley's theorem. Although this theorem is not massively useful today, it is very important historically as it shows the abstract definition of a group and the definition of a group as a collection of permutations are equivalent.