A permutation is a rearrangement, and rearrangements were the first groups ever studied: Lagrange and Galois looked at how the roots of a polynomial can be shuffled. Formally a permutation is a bijection from a set to itself.
Definition. $S_{n}$ is the set of all bijections $\sigma: \{1, \dots, n\} \to \{1, \dots, n\}$, with composition as the operation. It has $n!$ elements. We write $\sigma$ in two-row notation, with each number above its image: $$\sigma = \begin{pmatrix} 1 & 2 & 3 \\ 2 & 3 & 1 \end{pmatrix}$$ means $\sigma(1) = 2$, $\sigma(2) = 3$, $\sigma(3) = 1$.
Why it works
Our convention. $\sigma\tau$ means $\sigma \circ \tau$: do $\tau$ first, then $\sigma$, exactly as for functions, $(\sigma\tau)(x) = \sigma(\tau(x))$. (Some books compose left to right; always check.)
Worked example: Two products in $S_{3}$
- $\sigma\tau$: $1 \xrightarrow{\tau} 2 \xrightarrow{\sigma} 3$, $\ 2 \xrightarrow{\tau} 1 \xrightarrow{\sigma} 2$, $\ 3 \xrightarrow{\tau} 3 \xrightarrow{\sigma} 1$. So $\sigma\tau = \begin{pmatrix} 1 & 2 & 3 \\ 3 & 2 & 1 \end{pmatrix}$.
- $\tau\sigma$: $1 \xrightarrow{\sigma} 2 \xrightarrow{\tau} 1$, $\ 2 \xrightarrow{\sigma} 3 \xrightarrow{\tau} 3$, $\ 3 \xrightarrow{\sigma} 1 \xrightarrow{\tau} 2$. So $\tau\sigma = \begin{pmatrix} 1 & 2 & 3 \\ 1 & 3 & 2 \end{pmatrix}$.
- They differ, so $S_{3}$ is not abelian. (In fact $S_{n}$ is nonabelian for every $n \ge 3$.)
Answer: $\sigma\tau \ne \tau\sigma$.
Worked example: An inverse
- Swap the rows: $\begin{pmatrix} 3 & 1 & 4 & 2 \\ 1 & 2 & 3 & 4 \end{pmatrix}$.
- Sort the columns by the top row: $\sigma^{-1} = \begin{pmatrix} 1 & 2 & 3 & 4 \\ 2 & 4 & 1 & 3 \end{pmatrix}$.
- Check: $\sigma(\sigma^{-1}(1)) = \sigma(2) = 1$, and so on for each number.
Answer: $\sigma^{-1} = \begin{pmatrix} 1 & 2 & 3 & 4 \\ 2 & 4 & 1 & 3 \end{pmatrix}$.
Counting: to build a permutation, choose $\sigma(1)$ ($n$ ways), then $\sigma(2)$ ($n - 1$ ways), and so on, giving $n!$. So $|S_{3}| = 6$, $|S_{4}| = 24$, $|S_{5}| = 120$: these groups grow fast.
Permutation groups matter far beyond shuffling. Later in the course, Cayley's theorem shows that every group can be pictured as a group of permutations, so the habits you build here (follow one input at a time, read right to left) work for every group you will meet.
Common mistake
Key idea