## 4.5 The symmetric group

We have already met the symmetric group \((S_n,\circ)\) and studied its elements. Here’s a reminder of what we proved in the first part of the course:

- \(S_n\) is the set of all bijections from \(\{1,2,\ldots,n\}\) to itself, that is, all permutations of \(\{1,2,\ldots,n\}\). It is a group under composition of functions.
- If \(a_1,\ldots,a_m\) are distinct then \((a_1,\ldots,a_m)\) is the permutation which sends \(a_i\) to \(a_{i+1}\) for \(i<m\), \(a_m\) to \(a_1\), and anything not equal to \(a_i\) for some
*i*to itself. Such a permutation is called an*m*-cycle, and a permutation which is an*m*-cycle for some*m*is called a cycle. - Two cycles \((a_1,\ldots,a_m)\) and \((b_1,\ldots,b_l)\) are called disjoint if no \(a_i\) is equal to any \(b_j\).
- Any permutation \(\sigma \in S_n\) can be written as a product of disjoint cycles.
- \(|S_n|=n!= n(n-1)\cdots \cdot 2 \cdot 1\).

**Lemma 4.5**The order of an

*m*-cycle is

*m*.

*Proof.*Let \(\sigma = (a_0,a_1,\ldots,a_{m-1})\) be an

*m*-cycle. We have \(\sigma(a_i) = a_{i+1}\) for all

*i*, where the addition is done in \(\ZZ_m\). So \(\sigma^2(a_i) = \sigma(a_{i+1}) = a_{i+ 2}\), and you can prove by induction that \(\sigma^k(a_i) = a_{i+ k}\). The smallest \(k>0\) such that \(i + k = i\) is \(k=m\), so the smallest power of \(\sigma\) which is the identity is

*m*.

Not only did we prove that any element \(\sigma \in S_n\) equalled a product of
disjoint cycles, we saw how to find the disjoint cycles required by
finding the orbits of \(\sigma\). As a reminder, consider
\[ \sigma = \left(\begin{array}{ccccccc} 1 & 2 & 3 & 4 & 5 & 6 & 7\\
4 & 1 & 3 & 2 & 6 & 7 & 5 \end{array}\right). \]
At the first step we choose the number *1*. We have \(\sigma(1)=4, \sigma^2(1) = \sigma(\sigma(1))=2, \sigma^3(1) = \sigma(2) = 1\). So the
first cycle is \((1,4,2)\). Not all of the numbers \(1,2,\ldots,7\) appear
in this cycle, so we go back to step one and pick one that doesn’t
appear, say *3*. Since \(\sigma(3)=3\), the cycle that we add is just
\((3)\), so we now have \((1,4,2)(3)\).

Next we pick a number that hasn’t appeared yet, say 5. We have \(\sigma(5)=6, \sigma^2(5) = \sigma(6)=7, \sigma^3(5)=\sigma(7)=5\), and so the cycle we add is \((5,6,7)\) and we now have \[ \sigma = (1,4,2)(3)(5,6,7) \] and since there aren’t any elements of \(1,2,\ldots,7\) that don’t appear in one of our cycles, the algorithm stops.

Notice the one-cycle \((3)\) appears. But it is the identity permutation and composing with the identity doesn’t change anything, so we usually omit one-cycles when we write permutations like this.