Permutation Groups

Key definitions and Notation

See this video and these notes.

If $X$ is a set, a bijection $f:X\to X$ is called a permutation of $X$
The permutations of a set form a group $S_{X}$ under composition of functions, with identity element $id_X:X\to X$.
If $X$ is finite with $n$ elements then $S_{X}$ has $n!$ elements.
If $X$ is finite with $n$ elements we can assume $X= \{1,2,\ldots, n\}$. The permutations of this $X$ is called the symmetric group on $n$ elements and written $S_{n}$.
An element $\sigma\in S_{n}$ sending $\sigma(i)=x_i$ can be written

\[\sigma = \left(\begin{matrix} 1 & 2 & \cdots & n \\ x_1 & x_2 &\cdots & x_n\end{matrix}\right)\]

where $\{x_1,\ldots, x_n\} = \{1,2,\ldots, n\}.$

The multiplication $\sigma\tau$ of two permutations gets worked out by taking $i$, finding $\tau(i)$, and then finding $\sigma(\tau(i))$ since the operation is composition of functions. So in some sense the multiplication is “right to left.”
For example if

\[\sigma = \left(\begin{matrix} 1 & 2 & 3 & 4\\ 2 & 1 & 4 & 3\end{matrix}\right)\]

and

\[\tau = \left(\begin{matrix} 1 & 2 & 3 & 4 \\ 2 & 3 & 4 & 1 \end{matrix}\right)\]

then

\[\sigma\tau = \left(\begin{matrix} 1 & 2 & 3 & 4 \\ 1 & 4 & 3 & 2\end{matrix}\right)\]

See this video and these notes.

\[\sigma(a_1)=a_2,\sigma(a_2)=a_3,\ldots, \sigma(a_k)=a_1\]

We write $(a_1\ a_2\ a_3\ \cdots\ a_k)$ as a shorthand for this cycle.
If an index $i$ isn’t mentioned in a cycle $\sigma$, it is fixed, so $\sigma(i)=i$.
Cycles are multiplied right to left as with permutations generally: $(1 3 5 4 2)(3 4) = (1 3 2)(4 5).$
Cycles of length 2 are called transpositions.

Proposition: Disjoint cycles commute with one another.
Proposition: Every permutation in $S_{n}$ can be written as a product of disjoint cycles.

See this video and these notes.

Theorem: Every permutation in $S_{n}$ can be written as a product of transpositions. If $\sigma\in S_{n}$, then either every expression of $\sigma$ as a product of transpositions involves an even number of transpositions, or every such expression involves an odd number of transpositions. In the first case we say $\sigma$ is an even permutation, in the second case we say it is odd.
The product of even permutations is even; the product of odd and even permutation is odd; the product of odd permutations is even.

The subgroup of $S_{n}$ consisting of even permutations is called the alternating group $A_{n}$. $A_{n}$ has $n!/2$ elements.

See these notes and video

The symmetry group of a regular $n$-gon is a group with $2n$ elements called the dihedral group $D_{n}$. Each symmetry is determined by how it permutes the vertices of the $n$-gon, and so $D_{n}$ is a subgroup of $S_{n}$.
The group $D_{n}$, for $n\ge 3$, consists of all products of two elements $r$ and $s$, where

\[\begin{matrix} r^{n}=1 \\ s^2=1 \\ srs = r^{-1} \\ \end{matrix}\]

Here $r$ is the rotation of the $n$-gon about its center and $s$ is a reflection.

See these notes and this video. Also, this app.