# 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

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

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

- 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

- 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

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