3.16 Disjoint permutations
In this section, we show that any two disjoint permutation commute.
We call a subset \(S\subseteq [n]\) \(\sigma \)-stable if it is a sub-\(\mathbb {Z}\)-set of \([n]\) with \(\mathbb {Z}\) acting via \(\rho _{\sigma }\).
Suppose \(S\subset [n]\) and \(\sigma \in S_n\). The following are equivalent.
\(S\) is \(\sigma \)-stable.
\(S\) is a union of \(\sigma \)-orbits.
\(\sigma (S)\subseteq S\).
1 \(\Rightarrow \) 2 Obvious as, if \(S\) is \(\sigma \)-stable it is a sub-\(\mathbb {Z}\)-set of \([n]\), and thus itself a \(\mathbb {Z}\)-set. Therefore it has a partition into orbits.
2 \(\Rightarrow \) 3 Obvious as \(G\)-orbits are themselves sub-\(G\)-sets.
3 \(\Rightarrow \) 1 Suppose \(\sigma (S)\subseteq S\). Since \(\sigma \) is one-one, it follows that \(\sigma (S) = |S|\) and, thus, that \(\sigma (S) = S\). But then \(S = \sigma ^{-1}(S)\), and, consequently, \(\sigma ^k(S) = S\) for all \(k\in \mathbb {Z}\). So \(S\) is a sub-\(\mathbb {Z}\)-set of \([n]\).
Suppose \(\sigma \in S_n\). Then \(\operatorname{\mathrm{Mov}}\sigma \) is the union of all the nontrivial \(\sigma \)-orbits. Consequently, \(\operatorname{\mathrm{Mov}}\sigma \) and \(\operatorname{\mathrm{Fix}}\sigma \) are both \(\sigma \)-stable.
\(\operatorname{\mathrm{Fix}}\sigma \) is clearly the union of the trivial \(\sigma \)-orbits. So, as \([n]\) is a disjoint union of its \(\sigma \) orbits, \(\operatorname{\mathrm{Mov}}\sigma \) must itself be a disjoint union of all the nontrivial \(\sigma \) orbits.
Two cycles \(\sigma = (i_1\ldots i_a)\) and \(\tau = (j_1\ldots j_b)\) with \(a,b {\gt} 1\) are disjoint if and only if \(\{ i_1,\ldots , i_a\} \cap \{ j_1,\ldots , j_b\} = \emptyset \).
Obvious.
Suppose \(\sigma \) and \(\tau \) are disjoint permutations. Then \(\sigma \tau = \tau \sigma \).
Since \(\sigma \) and \(\tau \) are disjoint \(\operatorname{\mathrm{Mov}}\sigma \cap \operatorname{\mathrm{Mov}}\tau = \emptyset \). So \(\operatorname{\mathrm{Fix}}\sigma \cup \operatorname{\mathrm{Fix}}\tau = [n]\). To show that \(\sigma \tau = \tau \sigma \), it suffices to show that \(\sigma (\tau (j)) = \tau (\sigma (j))\) for all \(j\in [n]\). So take a \(j\in [n]\). Without loss of generality, we can assume that \(j\in \operatorname{\mathrm{Fix}}\sigma \). If \(j\in \operatorname{\mathrm{Fix}}\tau \), then \(\sigma \tau (j) = j = \tau \sigma (j)\). Otherwise, \(j\in \operatorname{\mathrm{Mov}}\tau \). So \(\tau (j)\in \operatorname{\mathrm{Mov}}\tau \) as well as \(\operatorname{\mathrm{Mov}}\tau \) is \(\tau \)-stable. Therefore, \(\tau (j)\in \operatorname{\mathrm{Fix}}\sigma \). So \(\sigma \tau (j) = \tau (j) = \tau \sigma (j)\) as desired.