## 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.