8.5 Symmetric Groups and Cycles
We have already met symmetric groups, but not with that name. A symmetric group is just the group of all permutations of a set. We’ll only really consider finite sets, although the definition makes sense for any set.
Let \(X\) be a set. The symmetric group on \(X\) is the group \(S(X)\) of all permutations of \(X\) (i.e., bijective functions \(f:X\to X\)), with composition as the group operation.
The symmetric group \(S_n\) of degree \(n\) is the group of all permutations of the set \(\{1,2,\dots,n\}\) of \(n\) elements.
Let’s think of ways of describing permutations. Of course, we could just say what \(f(i)\) is for each value of \(i\), and so, for example, refer to the element \(f\) of \(S_6\) with \(f(1)=3\), \(f(2)=6\), \(f(3)=1\), \(f(4)=4\), \(f(5)=2\) and \(f(6)=5\).
This is quite hard to read, and one easy way to set out the information in a more easily readable form is to use a “double row” notation with \(1,2,\dots,n\) along the top row, and \(f(1),f(2),\dots,f(n)\) along the bottom row.
For example, if \(f\) is the element of \(S_6\) described above, then we could write \[f=\begin{pmatrix}1&2&3&4&5&6\\3&6&1&4&2&5\end{pmatrix}.\]
But there’s an even more compact method, that is also much more convenient for understanding group theoretic aspects of permutations.
Let \(k\) and \(n\) be positive integers with \(k\leq n\). A \(k\)-cycle \(f\) in \(S_n\) is a permutation of the following form. There are \(k\) distinct elements \(i_1,i_2,\dots,i_k\in\{1,2,\dots,n\}\) such that \[f(i_1)=i_2, f(i_2)=i_3, \dots, f(i_{k-1})=i_k,f(i_k)=i_1\] and \(f(i)=i\) for \(i\not\in\{i_1,i_2,\dots,i_k\}\). (So \(f\) “cycles” the elements \(i_1,i_2,\dots,i_k\) and leaves other elements unmoved.)
Such an \(f\) is denoted by \(f=(i_1,i_2,\dots,i_k)\).
We call \(k\) the length of this cycle.In \(S_8\), the \(6\)-cycle \[g=(2,7,8,5,6,3)\] has \[g(2)=7,g(7)=8,g(8)=5,g(5)=6,g(6)=3,g(3)=2,g(1)=1\text{ and }g(4)=4,\] or, written in double row notation, \[\begin{pmatrix} 1&2&3&4&5&6&7&8\\1&7&2&4&6&3&8&5\end{pmatrix}.\] The notation \((2,7,8,5,6,3)\) would also denote an element of \(S_9\) with \(g(9)=9\), so this notation doesn’t specify which symmetric group we’re looking at, although that is rarely a problem.
Note that the \(6\)-cycle \((7,8,5,6,3,2)\) is exactly the same permutation as \(g\), so the same cycle can be written in different ways (in fact, a \(k\)-cycle can be written in \(k\) different ways, as we can choose to start the cycle with any of the \(k\) elements \(i_1,i_2,\dots,i_k\)).Transposition comes from the Latin trans meaning “across, beyond” and positus meaning “to put”. A transposition takes two elements and put them across each other, i.e. swap position.
Of course, not every permutation is a cycle. For example, the permutation \[f=\begin{pmatrix}1&2&3&4&5&6\\3&6&1&4&2&5\end{pmatrix}\] that we used as an example earlier is not. However, we can write it as a composition \[f=(1,3)(2,6,5)\] of two cycles. These two cycles are “disjoint” in the sense that they move disjoint set of elements \(\{1,3\}\) and \(\{2,5,6\}\), and this means that it makes no difference which of the two cycles we apply first. So also \[f=(2,6,5)(1,3).\]
A set of cycles in \(S_n\) is disjoint if no element of \(\{1,2,\dots,n\}\) is moved by more than one of the cycles.
Every element of \(S_n\) is may be written as a product of disjoint cycles.
We give a constructive proof, that is we give a method which will write any \(f \in S_n\) as such a product.
We’ll write down a set of disjoint cycles by considering repeatedly applying \(f\) to elements of \(\{1,2,\dots,n\}\), starting with the smallest elements.
So we start with \(1\), and consider \(f(1),f^2(1),\dots\) until we reach an element \(f^k(1)\) that we have already reached. The first time this happens must be with \(f^k(1)=1\), since if \(f^k(1)=f^l(1)\) for \(0<l<k\) then \(f^{k-1}(1)=f^{l-1}(1)\), and so we’d have repeated the element \(f^{l-1}(1)\) earlier. So we have a cycle \[(1,f(1),f^2(1),\dots,f^k(1)).\]
Now we start again with the smallest number \(i\) that is not involved in any of the cycles we’ve already written down, and get another cycle \((i,f(i),\dots, f^s(i))\) for some \(s\).
We keep repeating until we’ve dealt with all the elements of \(\{1,2,\dots,n\}\).□
This will probably be clearer if we look at an example.
Consider the element \[f=\begin{pmatrix} 1&2&3&4&5&6&7&8&9\\ 2&5&1&9&7&6&3&4&8\end{pmatrix}\] of \(S_9\) written in double row notation. To write this as a product of disjoint cycles, we start with \(1\), and calculate \[f(1)=2,f(2)=5,f(5)=7,f(7)=3,f(3)=1,\] so we have a \(5\)-cycle \((1,2,5,7,3)\).
The smallest number we haven’t yet dealt with is \(4\), and \[f(4)=9,f(9)=8,f(8)=4,\] so we have a \(3\)-cycle \((4,9,8)\).
The only number we haven’t dealt with is \(6\), and \[f(6)=6,\] so finally we have a \(1\)-cycle \((6)\).
So \[f=(1,2,5,7,3)(4,9,8)(6)\] as a product of disjoint cycles. Since \(1\)-cycles are just the identity permutation, we can (and usually will) leave them out, and so we can write \[f=(1,2,5,7,3)(4,9,8).\]
Since the order in which we apply disjoint permutations doesn’t matter, we could write the cycles in a different order, or we could start each cycle at a different point. So, for example, \[f=(9,8,4)(5,7,3,1,2)\] is another way of writing the same permutation as a product of disjoint cycles.It’s very easy to read off the product of permutations written in disjoint cycle notation, just by using the method in the proof of Theorem 8.25.
Let \[f=(1,5,3,4)(2,6,7)\] and \[g=(3,4,8,1,2,5)\] be elements of \(S_8\) written in disjoint cycle notation. Let’s calculate \(fg\) and \(gf\). \[fg=(1,5,3,4)(2,6,7)(3,4,8,1,2,5),\] but of course these are not disjoint cycles. So we start with \(1\) and calculate where it is sent by performing the permutation \(fg\) repeatedly:
- \(1\) is sent to \(2\) by \((3,4,8,1,2,5)\), which is sent to \(6\) by \((2,6,7)\), which is not moved by \((1,5,3,4)\). So \(fg(1)=6\).
- \(6\) is not moved by \((3,4,8,1,2,5)\). It is sent to \(7\) by \((2,6,7)\), which is not moved by \((1,5,3,4)\). So \(fg(6)=7\).
- \(7\) is not moved by \((3,4,8,1,2,5)\). It is sent to \(2\) by \((2,6,7)\), which is not moved by \((1,5,3,4)\). So \(fg(7)=2\).
- \(2\) is sent to \(5\) by \((3,4,8,1,2,5)\), which is not moved by \((2,6,7)\) and is sent to \(3\) by \((1,5,3,4)\). So \(fg(2)=3\).
- \(3\) is sent to \(4\) by \((3,4,8,1,2,5)\), which is not moved by \((2,6,7)\), and sent to \(1\) by \((1,5,3,4)\). So \(fg(3)=1\).
- So we’ve completed our first cycle \((1,6,7,2,3)\).
- \(4\) is sent to \(8\) by \((3,4,8,1,2,5)\), which is not moved by \((2,6,7)\) or \((1,5,3,4)\). So \(fg(4)=8\).
- \(8\) is sent to \(1\) by \((3,4,8,1,2,5)\), which is not moved by \((2,6,7)\) and sent to \(5\) by \((1,5,3,4)\). So \(fg(8)=5\).
- \(5\) is sent to \(3\) by \((3,4,8,1,2,5)\), which is not moved by \((2,6,7)\) and sent to \(4\) by \((1,5,3,4)\). So \(fg(5)=4\).
- So we’ve completed another cycle \((4,8,5)\).
- We’ve now dealt with all the numbers from \(1\) to \(8\), so \(fg=(1,6,7,2,3)(4,8,5)\) as a product of disjoint cycles.
Symmetric groups were one of the first type of groups to emerge as mathematicians studied the permutation of roots of equations in the 1770s. This was before the formal abstract definition of a group was introduced - around 100 years later in the 1870s.