TAOCP 1.3.3 Exercise 11
Let $\pi$ be a permutation expressed in cycle form as a product of disjoint cycles: \pi = (x_{11} x_{12} \dots x_{1n_1})(x_{21} x_{22} \dots x_{2n_2})\cdots(x_{k1} x_{k2} \dots x_{kn_k}), where each c...
Section 1.3.3: Applications to Permutations
Exercise 11. [15] Find a simple rule for writing $\pi^{-}$ in cycle form, if the permutation $\pi$ is given in cycle form.
Verified: yes
Solve time: 1m28s
Solution
Let $\pi$ be a permutation expressed in cycle form as a product of disjoint cycles:
$$ \pi = (x_{11} x_{12} \dots x_{1n_1})(x_{21} x_{22} \dots x_{2n_2})\cdots(x_{k1} x_{k2} \dots x_{kn_k}), $$
where each cycle $(x_{i1} x_{i2} \dots x_{in_i})$ contains $n_i \ge 1$ elements, and the cycles are disjoint. By definition, a cycle $(x_1 x_2 \dots x_n)$ represents the map
$$ x_1 \mapsto x_2,\quad x_2 \mapsto x_3,\quad \dots,\quad x_{n-1} \mapsto x_n,\quad x_n \mapsto x_1. $$
We seek the cycle form of $\pi^{-1}$, the inverse permutation. By the general property of inverses, for any element $y$ we have
$$ \pi^{-1}(\pi(y)) = y \quad \text{and} \quad \pi(\pi^{-1}(y)) = y. $$
Consider a single cycle $(x_1 x_2 \dots x_n)$ of $\pi$. We compute the action of its inverse. For each $i$ with $1 < i \le n$, we have $\pi(x_{i-1}) = x_i$, hence $\pi^{-1}(x_i) = x_{i-1}$. For $i=1$, $\pi(x_n) = x_1$, hence $\pi^{-1}(x_1) = x_n$. Consequently, the inverse permutation acts on the elements of the cycle as
$$ x_1 \mapsto x_n,\quad x_2 \mapsto x_1,\quad x_3 \mapsto x_2,\quad \dots,\quad x_n \mapsto x_{n-1}. $$
This is exactly the effect of writing the original cycle in reverse order:
$$ (x_1 x_2 \dots x_n)^{-1} = (x_n x_{n-1} \dots x_1). $$
Since the cycles of $\pi$ are disjoint, applying this procedure independently to each cycle yields the inverse permutation $\pi^{-1}$. That is, if
$$ \pi = C_1 C_2 \cdots C_k $$
with disjoint cycles $C_i$, then
$$ \pi^{-1} = C_1^{-1} C_2^{-1} \cdots C_k^{-1}, $$
where each $C_i^{-1}$ is obtained by reversing the order of the elements in $C_i$.
This gives the simple rule: To write $\pi^{-1}$ in cycle form, reverse the order of the elements in each cycle of $\pi$ while leaving the sequence of cycles unchanged. Singleton cycles are unaffected, since reversing a single element yields the same cycle.
Example. If
$$ \pi = (acf)(bd)(e), $$
then
$$ \pi^{-1} = (fca)(db)(e). $$
This completes the proof.
∎