Proposition 9.1.1.
Disjoint cycles commute.
Section 9.1 Cycle Decomposition
A permutation \(\sigma \in S_n\) is a cycle of length \(k\) if there exist \(a_1, \ldots, a_k\) such that \(\sigma(a_1) = a_2, \sigma(a_2) = a_3, \ldots, \sigma(a_k) = a_1\text{,}\) and \(\sigma\) fixes every other element. We write \((a_1, a_2, \ldots, a_k)\) for this cycle. For example, in \(S_7\text{,}\)
\begin{equation*}
\begin{pmatrix}
1 & 2 & 3 & 4 & 5 & 6 & 7\\
6 & 3 & 5 & 1 & 4 & 2 & 7
\end{pmatrix}
= (1\, 6\, 2\, 3\, 5\, 4 )
\end{equation*}
is a single cycle, whereas
\begin{equation*}
\begin{pmatrix}
1 & 2 & 3 & 4 & 5 & 6 \\
2 & 4 & 1 & 3 & 6 & 5
\end{pmatrix}
= (1\, 2\, 4\, 3)(5\, 6)
\end{equation*}
is not a cycle, but a product of a \(4\)-cycle and a \(2\)-cycle.
Two cycles \((a_1, \ldots, a_k)\) and \((b_1, \ldots, b_l)\) are disjoint if no \(a_i\) equals any \(b_j\text{.}\)
Proof.
Let \(\sigma = (a_1, \ldots, a_k)\) and \(\tau = (b_1, \ldots, b_l)\) be disjoint. If \(x\) is fixed by both, then \(\sigma\tau(x) = x = \tau\sigma(x)\text{.}\) If \(x = a_i\text{,}\) then \(\tau\) fixes \(a_i\) (since the cycles are disjoint), so
\begin{equation*}
\sigma\tau(a_i) = \sigma(a_i) = \tau(\sigma(a_i)) = \tau\sigma(a_i)\text{,}
\end{equation*}
using that \(\tau\) also fixes \(\sigma(a_i)\text{,}\) another \(a_j\text{.}\) The case \(x = b_i\) is symmetric.
Theorem 9.1.2.
Every permutation in \(S_n\) can be written as a product of disjoint cycles.
Proof.
Let \(\sigma \in S_n\) and set \(X_1 = \{\sigma(1), \sigma^2(1), \ldots\}\text{,}\) a finite set since \(\{1, \ldots, n\}\) is finite. Let \(i\) be the first integer not in \(X_1\) and set \(X_2 = \{\sigma(i), \sigma^2(i), \ldots\}\text{;}\) continue in this way to obtain finite, pairwise disjoint sets \(X_1, \ldots, X_r\) covering \(\{1, \ldots, n\}\text{.}\) Let \(\sigma_j\) agree with \(\sigma\) on \(X_j\) and fix everything else. Each \(\sigma_j\) is a cycle, the \(\sigma_j\) are pairwise disjoint since the \(X_j\) are, and \(\sigma = \sigma_1 \sigma_2 \cdots \sigma_r\text{.}\)
