4.4 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.6 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.