Link Search Menu Expand Document

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)\]


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


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


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