Section 2.5 The Symmetric Group
For a set \(X\text{,}\) denote by \(S_X\) the set of bijective maps \(f: X \to X\text{.}\) We make \(S_X\) into a group with composition of functions as the binary operation: \((f,g)\mapsto f\circ g\text{,}\) so \(f\circ g(x) = f(g(x))\text{.}\)
The identity element is the identity map \(id_X:X
\to X\) defined by \(id_X(x) = x\) for all \(x \in X\text{.}\) Every element \(f
\in S_X\) has an inverse since each \(f\) is one-to-one and onto. The operation is associative since composition of maps is.
When \(X\) is finite, say \(|X| = n\text{,}\) we assume \(X =
\{1, 2, \dots, n\}\) and write \(S_n\) for \(S_X\text{.}\) It is easy to check that \(|S_n| = n!\text{.}\) The group \(S_n\) is called the symmetric group on \(n\) letters. Any subgroup of \(S_n\) is called a permutation group.
Note that \(S_1= \{id\}\) and \(S_2 = \{id, \sigma\}\) (where \(\sigma\) interchanges 1 and 2) are cyclic groups. For \(n\ge 3\text{,}\) it is easy to check that \(S_n\) is nonabelian.
Consider \(\sigma \in S_{11}\) described somewhat cumbersomely by
\begin{equation*}
\sigma = \begin{pmatrix}1\amp 2\amp 3\amp 4\amp 5\amp 6\amp 7\amp 8\amp 9\amp 10\amp 11\\
5\amp 1\amp 3\amp 2\amp 7\amp 6\amp 4\amp 9\amp 8\amp 11\amp
10\end{pmatrix}
\end{equation*}
where \(\sigma\) takes an element in the top row to the element directly below it. It is more convenient to write \(\sigma\) as a product of disjoint cycles.
Recall that a cycle of length \(k\) (or a \(k\)-cycle) is a permutation, \(\tau\in S_X\text{,}\) for which there exist \(a_1, \dots, a_k \in X\) satisfying
\begin{equation*}
\tau(a_i) = a_{i+1} \text{ for } 1\le i \le k,\ \tau(a_k)
= a_1,\text{ and } \tau(x) = x \text{ for all other } x\in
X.
\end{equation*}
The cycle \(\tau\) is written as \(\tau = (a_1\ a_2\
\cdots \ a_k).\)
Example 2.5.1.
For example, we can write
\begin{equation*}
\sigma = \begin{pmatrix}1\amp 2\amp 3\amp 4\amp 5\amp 6\amp 7\amp 8\amp 9\amp 10\amp 11\\
5\amp 1\amp 3\amp 2\amp 7\amp 6\amp 4\amp 9\amp 8\amp 11\amp
10\end{pmatrix}
\end{equation*}
as as a product of disjoint cycles:
\begin{equation*}
\sigma=\underbrace{(1\ 5\ 7\ 4\
2)}_{5-cycle}\underbrace{(3)(6)}_{1-cycles} \underbrace{(8\ 9)(10\ 11)}_{2-cycles}.
\end{equation*}
Recall the the following properties:
Proposition 2.5.2.
Every permutation can be written uniquely as the product of disjoint cycles.
The cycle can be represented as
\begin{equation*}
(a_1\ \dots \ a_r) = (a_2\ a_3\ \dots a_r\ a_1) = (a_3\
a_4\ \dots, \ a_r\ a_1\ a_2) = \cdots
\end{equation*}
Disjoint cycles commute.
The process by which we write a permutation as a product of disjoint cycles can be presented as algorithmic, but it also has a natural interpretation in terms of group actions.
Suppose we are given a permutation \(\sigma\) in \(S_n\) and want to find its representation as a product of disjoint cycles. Let \(G = \la \sigma \ra\) be the cyclic group generated by \(\sigma.\) Then \(G\) acts on \(X = \{1, \dots, n\}\) by \((\tau, k) \mapsto \tau(k).\) Given a group action, we know that the set \(X\) is partitioned into orbits. Each orbit corresponds to one of the disjoint cycles in the decomposition:
\begin{equation*}
G\cdot k = \text{Orbit of }(k) = \{\tau(k)\mid \tau\in \la \sigma
\ra\}.
\end{equation*}
The only difference between the orbit and the cycle, is that the elements in the cycle are ordered to convey a bit more information:
\begin{equation*}
(k\ \sigma(k)\ \sigma^2(k)\ \cdots\ \sigma^{\ell-1}(k))
\end{equation*}
where \(\ell\) is the smallest positive integer such that \(\sigma^\ell(k) = k.\) So now the proposition above is clearer: the cycles are uniquely determined because the orbits under the action of \(\la \sigma\ra\) are, an orbit can be named by any element it contains since the group acts transitively on each orbit, and \(X\) being the disjoint union of orbits does not depend on the order in which you write the orbits in the union.
Exercise 2.5.1.
(a)
Show that the order (as a group element in \(S_n\)) of an \(r\)-cycle \(\sigma=(a_1\ a_2\ \cdots \ a_r)\) is \(r.\)
Solution.
\(\sigma\) takes \(a_i\) to \(a_{i+1}\) for \(1 \le
i \le r\) and \(a_r\) to \(a_1,\) it is straightforward to check by induction that \(\sigma^j\) takes \(a_i\) to \(a_{i+j}\) with \(i+j\) read with least positive residues modulo \(r.\) It follows that the order of \(\sigma\) is \(r.\)
(b)
Write a permutation \(\sigma \in S_n\) as a product of disjoint cycles: \(\sigma=\sigma_1\cdots \sigma_s\text{.}\) Show that the order of \(\sigma\) is the least common multiple of the lengths of the cycles \(\sigma_i.\)
Solution.
Let \(m_j\) be the length (order) of the cycle \(\sigma_j,\) and let \(M = \lcm\{m_1,\dots, m_s\}.\) Then, since disjoint cycles commute,
\begin{equation*}
\sigma^M = (\sigma_1\cdots \sigma_s)^M = \sigma_1^M\cdots
\sigma_s^M=1
\end{equation*}
since each \(m_j\) is a multiple of \(M.\) It follows from Lagrange that the order of \(\sigma\) divides \(M.\) Suppose that \(N =
|\sigma|\text{,}\) then since disjoint cycles commute,
\begin{equation*}
\sigma^N = (\sigma_1\cdots \sigma_s)^N = \sigma_1^N\cdots
\sigma_s^N=1\text{,}
\end{equation*}
hence
\begin{equation*}
\sigma_1^{-N} = \sigma_2^n\cdots \sigma_t^N.
\end{equation*}
Recall that the \(\sigma_j\) are disjoint cycles so as permutations only move sets which are disjoint from one another. That is, \(\sigma_1\) cannot move any integer in the sets moved by \(\sigma_2, \dots, \sigma_s\text{,}\) yet their \(N\)th powers are equal. The only resolution is that \(\sigma_1^{-N} = 1 =
\sigma_1^N\text{.}\) This implies \(m_1 \mid N\text{.}\) Since the cycles commute, we may do the same trick for all the \(\sigma_j\) to conclude \(m_j \mid N\) for all \(j\text{,}\) and hence \(M \mid N\text{.}\) Thus \(|\sigma| = M\text{.}\)
Exercise 2.5.2.
Write a permutation \(\sigma\in S_n\) as the product of disjoint cycles —including the 1-cycles:
\begin{equation*}
\sigma
= \sigma_1 \cdots \sigma_r\text{,}
\end{equation*}
and let
\(a_i\) denote the length of
\(\sigma_i.\) Because disjoint cycles commute, we may assume that the cycles are arranged in so their lengths appear in descending order and since we include the 1-cycles their lengths form a
partition of the integer
\(n.\)
If \(\sigma
= \sigma_1 \cdots \sigma_r\) has lengths \(a_1 \ge \cdots \ge
a_r \ge1\text{,}\) then we call the \(r\)-tuple \((a_1, \dots,
a_r)\) the cycle type of \(\sigma.\)
(a)
Let \(\tau = (a_1\ a_2\ \cdots \ a_k)\) be any \(k\)-cycle. Show that for any permutation \(\sigma\text{,}\)
\begin{equation*}
\sigma\tau \sigma^{-1} =(\sigma(a_1)\ \sigma(a_2)\ \cdots \
\sigma(a_k)) \text{,}
\end{equation*}
so in particular, conjugation takes a \(k\)-cycle to another \(k\)-cycle.
Solution.
Let’s first see where we send an integer of the form \(\ell = \sigma(a_i)\) for some \(i\text{.}\) We see that \[\sigma\tau\sigma^{-1}(\sigma(a_i)) = \sigma\tau(a_i) = \sigma(a_{i+1}),\] where we read the subscripts modulo \(k\text{,}\) so we might conjecture that \(\sigma\tau\sigma^{-1} =
(\sigma(a_1)\,\sigma(a_2)\,\cdots\,\sigma(a_k)),\) however to be sure, we must show that \(\sigma\tau\sigma^{-1}\) fixes all other integers. So now let \(\ell\) be an integer, with \(\ell \ne \sigma(a_i)\) for any \(i\text{.}\) Then \(\sigma^{-1}(\ell) \ne a_i\) for any \(i\text{,}\) so \(\tau\) leaves it unchanged, so that \(\sigma\) takes it back to \(\ell\text{.}\) So no integer other than the \(\sigma(a_i)\) is moved by \(\sigma\tau\sigma^{-1}\text{,}\) and our decomposition is complete.
(b)
Let \(\tau, \tau' \in S_n\) be any two cycles of length \(k.\) Show that there is an element \(\sigma \in
S_n\) so that
\begin{equation*}
\tau' = \sigma \tau \sigma^{-1}.
\end{equation*}
This means that for each \(k\)-cycles in \(S_n\) form their own and complete conjugacy class.
Solution.
Let \(\tau = (a_1\,a_2\, \cdots \,a_k)\) and \(\mu = (b_1\,b_2\,
\cdots \,b_k)\text{.}\) Then for any permutation \(\sigma\) which takes \(a_i \mapsto b_i\) we have the desired equality.
Use the exercises above to deduce the following proposition.
Proposition 2.5.3.
There is a one-to-one correspondence between conjugacy classes of elements in \(S_n\) are partitions of the integer \(n.\)
Proof.
Let \(\sigma \in S_n\) and consider its conjugacy class. Write \(\sigma\) as the product of disjoint cycles (including the 1-cycles):
\begin{equation*}
\sigma = \sigma_1 \cdots \sigma_r \text{ with } m_i =
|\sigma_i|.
\end{equation*}
We have observed that (arranged in descending order since disjoint cycles commute), \(m_1, \dots, m_r\) is a partition of \(n.\) Since conjugation is an (inner) automorphism,
\begin{equation*}
\tau\sigma\tau^{-1} = \tau\sigma\tau^{-1}\cdots
\tau\sigma_r\tau^{-1}\text{,}
\end{equation*}
and by the exercises above \(\tau\sigma_j\tau^{-1}\) is again a cycle of length \(m_j\text{,}\) so the resulting cycles in \(\tau\sigma\tau^{-1}\) again produce the same partition of \(n.\)
Given a partition of \(n\text{,}\) there is certainly a permutation with that cycle type, just by listing the integers from 1 to \(n\text{,}\) and grouping them into cycles of the desired length.
So we have a surjective map from permutations to partitions which is well-defined on conjugacy classes. We have another exercise which shows that two cycles of a given length are always conjugate and this extends to a product of disjoint cycles.
Permutations are divided into even and odd permutations according to one of the following two equivalent schemes. The virtue of the first definition is that it is clearly well-defined.
Define a function \(\sgn: S_n \to \{\pm1\}\) as follows: for a permutation \(\sigma \in S_n,\) write \(\sigma\) as the product of disjoint cycles (including the 1-cycles), say \(\sigma = \sigma_1\cdots \sigma_t\text{.}\) Then we define
\begin{equation*}
\sgn(\sigma) = (-1)^{n-t}.
\end{equation*}
It follows that \(\sgn(1) = 1 =(-1)^{n-n}\text{,}\) and \(\sgn( (a\ b)) =
(-1)^{n - (n-1)} = -1.\) For a permutation \(\sigma\text{,}\) the value \(\sgn(\sigma)\) is called the sign of the permutation.
For the second definition, note that any cycle can be written as the product of transpositions:
\begin{equation*}
(a_1\ a_2\ \cdots \ a_r) = (a_1\ a_r)\cdots(a_1\ a_3)(a_1\
a_2)\text{,}
\end{equation*}
hence so can any permutation (though not in a unique way). If
\begin{equation*}
\sigma = \tau_1 \cdots \tau_r\text{,}
\end{equation*}
where all the \(\tau_i\) are transpositions, then it is also true that
\begin{equation*}
\sgn(\sigma) = (-1)^r\text{.}
\end{equation*}
Proposition 2.5.4.
The definitions are the sign function given above are equivalent. Moreover, \(\sgn: S_n \to \{\pm1\}\) is a group homomorphism, and is surjective for \(n \ge 2.\) It’s kernel is called the alternating group, denoted \(A_n\text{.}\)
