# 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\}.$

### Multiplication of Permutations

• 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)$

## Cycles

See this video and these notes.

• A cycle $\sigma$ of length $k$ is a permutation of the form
$\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.

### Main Cycle results

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

## Parity of permutations

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 Alternating Group

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

## Geometric Symmetry Groups

### Dihedral groups

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.

### Symmetries of the cube

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

• The symmetry group of the cube is $S_{4}$.