Conjugate Cycles

Definition: Let $\sigma$ be a permutation of the elements in $\{ 1, 2, ..., n \}$ and let $\alpha = (a_1a_2...a_s)$ be a cycle of length $s$. Then the Conjugate of $\alpha$ with respect to the permutation $\sigma$ is the permutation $\rho = \sigma \circ \alpha \circ \sigma^{-1}$.

For example, consider the set $\{ 1, 2, 3, 4, 5, 6 \}$ and the permutation $\sigma = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6\\ 2 & 4 & 1 & 3 & 5 & 6 \end{pmatrix}$ and the cycle $\alpha = (132) = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6\\ 3 & 1 & 2 & 4 & 5 & 6 \end{pmatrix}$. Then we have that $\sigma^{-1} = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 3 & 1 & 4 & 2 & 5 & 6 \end{pmatrix}$ and the conjugate of $\alpha$ with respect to the permutation $\sigma$ is:

(1)

\begin{align} \quad \rho = \sigma \circ \alpha \circ \sigma^{-1} = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6\\ 2 & 4 & 1 & 3 & 5 & 6 \end{pmatrix} \circ \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6\\ 3 & 1 & 2 & 4 & 5 & 6 \end{pmatrix} \circ \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 3 & 1 & 4 & 2 & 5 & 6 \end{pmatrix} = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 4 & 1 & 3 & 2 & 5 & 6 \end{pmatrix} \end{align}

We will now look at some nice theorems regarding conjugates.

Theorem 1: Let $\alpha = (a_1a_2...a_s)$ and $\beta = (b_1b_2...b_s)$ be two cycles of length $s$ from the set $\{ 1, 2, ..., n \}$. Then there exists a permutation $\sigma$ such that for all $i \in \{1, 2, ..., s \}$ we have that $\sigma(a_i) = b_i$.

• Proof: We will show that at least one such permutation $\sigma$ exists, although, many such permutations may exist.

• Since $\alpha$ and $\beta$ are cycles, by definition, the notation $\alpha = (a_1a_2...a_s)$ and $\beta = (b_1b_2...b_s)$ implies that $a_1, a_2, ..., a_s$ are distinct and that $b_1, b_2, ..., b_s$ are distinct. Define $\sigma$ for all $x \in \{ 1, 2, ..., n \}$ by:

(2)

\begin{align} \quad \sigma(x) = \left\{\begin{matrix} b_i & \mathrm{if} \: x = a_i\\ x & \mathrm{if} x \neq a_i \: \mathrm{for \: all} \: i \in \{ 1, 2, ..., s\} \end{matrix}\right. \end{align}

• We only need to show that $\sigma : \{1, 2, ..., n \} \to \{ 1, 2, ..., n \}$ is a bijection. We first show that $\sigma$ is injective. There are two cases to consider. Suppose that $x = a_i$ for some $i \in \{1, 2, ..., s \}$ and that $\sigma(x) = \sigma (y)$. Then:

(3)

\begin{align} \quad \sigma(x) = \sigma(y) \\ \quad b_i = \sigma(y) \end{align}

• This implies that $y = a_i$. Therefore $x = y$.

• Now suppose that $x \neq a_i$ for all $i \in \{ 1, 2, ..., s \}$ and that $\sigma(x) = \sigma(y)$. Then:

(4)

\begin{align} \quad \sigma(x) = \sigma(y) \\ \quad x = \sigma (y) \end{align}

• This implies that $x = y$. Hence $\sigma(x) = \sigma(y)$ implies that $x = y$, so $\sigma$ is injective.

• Now let $y \in \{ 1, 2, ..., n \}$. Then either $y \in \{ b_1, b_2, ..., b_s \}$ or $y \not \in \{ b_1, b_2, ..., b_s \}$. So:

(5)

\begin{align} \quad y = \left\{\begin{matrix} \sigma(a_i) & \mathrm{if} \: y = b_i \: \mathrm{for \: some} \: i \in \{1, 2, ..., s\}\\ \sigma(y) & \mathrm{if} \: y \neq b_i \: \mathrm{for \: all} \: i \in \{ 1, 2, ...,s\} \end{matrix}\right. \end{align}

• Therefore $\sigma$ is surjective. Hence $\sigma$ is bijective and therefore a permutation. $\blacksquare$

Theorem 2: Let $\alpha = (a_1a_2...a_s)$ and $\beta = (b_1b_2...b_s)$ be two cycles of length $s$ from the set $\{ 1, 2, ..., n \}$ and let $\sigma$ be a permutation. If for all $i \in \{ 1, 2, ..., s \}$, $\sigma (a_i) = b_i$ then $\beta$ is equal to the conjugate of $\alpha$ with respect to the permutation $\sigma$, that is $\beta = \sigma \circ \alpha \circ \sigma^{-1}$.

• Let $\alpha = (a_1a_2...a_s)$ and $\beta = (b_1b_2...b_s)$ be two cycles of length $s$ from $\{ 1, 2, ..., n \}$. Then $\alpha(a_1) = a_2$, $\alpha(a_2) = a_3$, …, $\alpha(a_{s-1}) = a_s$, $\alpha(a_s) = a_1$. Similarly, $\beta(b_1) = b_2$, $\beta(b_2) = b_3$, … $\beta(b_{s-1}) = b_s$, and $\beta(b_s) = b_1$. Let $\sigma$ be a permutation such that for all $i \in \{1, 2, ..., s \}$ we have that $\sigma(a_i) = b_i$. Then $\sigma^{-1} (b_i) = a_i$.

• Now for all $i \in \{ 1, 2, ..., s - 1 \}$ we have that

(6)

\begin{align} \quad [\sigma \circ \alpha \circ \sigma^{-1}] (b_i) = [\sigma \circ \alpha] (a_i) = \sigma (a_{i+1}) = b_{i+1} \end{align}

• And for $i = s$ we have that:

(7)

\begin{align} \quad [\sigma \circ \alpha \circ \sigma^{-1}](b_s) = [\sigma \circ \alpha](a_s) = \sigma(a_1) = b_1 \end{align}

• Therefore $[\sigma \circ \alpha \circ \sigma^{-1}] (b_1) = b_2$, $[\sigma \circ \alpha \circ \sigma^{-1}] (b_2) = b_3$, …, $[\sigma \circ \alpha \circ \sigma^{-1}] (b_{s-1}) = b_s$, and $[\sigma \circ \alpha \circ \sigma^{-1}] (b_s) = b_1$. We now only need to show that all $x \not \in \{ b_1, b_2, ..., b_s \}$ are invariant under $\sigma \circ \alpha \circ \sigma^{-1}$.

• For all elements $x \not \in \{ b_1, b_2, ..., b_s \}$ we have that $\sigma^{-1} (x) = y$. Since $\sigma(a_i) = b_i$, this implies that $a_i = \sigma^{-1}(b_i)$, so $\sigma^{-1}(x) \neq a_i$ and hence $\alpha (\sigma^{-1}(x)) = \alpha(y) = y$. We also have that $x = \sigma (y)$, and so:

(8)

\begin{align} \quad [\sigma \circ \alpha \circ \sigma^{-1}](x) = [\sigma \circ \alpha](y) = \sigma(y) = x \end{align}

• Hence we see that $\sigma \circ \alpha \circ \sigma^{-1} = \beta$. $\blacksquare$