TAOCP 1.3.3 Exercise 37

The forward direction is correct and standard.

taocpmathematicsalgorithmsvolume-1math-hard

Section 1.3.3: Applications to Permutations

Exercise 37. [M26] (Even permutations.) Let $\pi$ be a permutation of ${1,\ldots,n}$. Prove that $\pi$ can be written as the product of an even number of 2-cycles if and only if $\pi$ can be written as the product of exactly two $n$-cycles.

Verified: no
Solve time: 3m09s

The forward direction is correct and standard. The reverse direction fails because it does not construct the required factorization. A complete proof must explicitly build two $n$-cycles whose product is the given even permutation.

Proof

Forward direction

Assume $\pi = \alpha\beta$, where $\alpha$ and $\beta$ are $n$-cycles.

Any $n$-cycle $(a_1,a_2,\dots,a_n)$ can be written as a product of $n-1$ transpositions:

$$ (a_1,a_2,\dots,a_n) = (a_1,a_n)(a_1,a_{n-1})\cdots(a_1,a_2). $$

Hence each of $\alpha$ and $\beta$ is a product of $n-1$ transpositions, so

$$ \pi = \alpha\beta $$

is a product of $2n-2$ transpositions, an even number. Therefore $\pi$ is even.

Reverse direction

Assume $\pi \in S_n$ is even. We construct $n$-cycles $\alpha,\beta$ such that

$$ \pi = \alpha\beta. $$

Step 1: Cycle decomposition

Write $\pi$ as a product of disjoint cycles:

$$ \pi = C_1 C_2 \cdots C_r, \quad C_i = (c_{i,1},c_{i,2},\dots,c_{i,m_i}). $$

Let $n = m_1 + \cdots + m_r$.

Since $\pi$ is even, we use the standard parity fact:

$$ \operatorname{sgn}(\pi) = (-1)^{n-r}. $$

Thus $\pi$ even implies $n-r$ is even.

Step 2: Construct a single $n$-cycle $\alpha$

List the elements block by block:

$$ S = (c_{1,1},\dots,c_{1,m_1},c_{2,1},\dots,c_{2,m_2},\dots,c_{r,1},\dots,c_{r,m_r}). $$

Define $\alpha$ to be the $n$-cycle following this list:

$$ \alpha = (c_{1,1},c_{1,2},\dots,c_{r,m_r}). $$

So $\alpha$ moves forward along the concatenated list $S$, and $\alpha^{-1}$ moves backward along $S$.

Step 3: Define $\beta = \alpha^{-1}\pi$

We now set

$$ \beta = \alpha^{-1}\pi. $$

Then automatically $\pi = \alpha\beta$. It remains to prove that $\beta$ is an $n$-cycle.

Compute $\beta(x) = \alpha^{-1}(\pi(x))$.

Take $x = c_{i,j}$. Then:

$$ \pi(c_{i,j}) = c_{i,j+1} \quad (\text{indices mod } m_i). $$

Now apply $\alpha^{-1}$. This sends each element to its predecessor in the global list $S$.

There are two cases:

  • If $j < m_i$, then $c_{i,j+1}$ is immediately followed in $S$ by $c_{i,j+2}$ or belongs inside the same block, so its predecessor under $\alpha$ is $c_{i,j}$. Hence:

$$ \beta(c_{i,j}) = c_{i,j}. $$

This shows that within each cycle block, $\beta$ moves backward along the cycle.

  • If $j = m_i$, then $\pi(c_{i,m_i}) = c_{i,1}$. The predecessor of $c_{i,1}$ in the global list $S$ is the last element of the previous block, namely $c_{i-1,m_{i-1}}$ (with indices cyclically interpreted). Hence:

$$ \beta(c_{i,m_i}) = c_{i-1,m_{i-1}}. $$

So $\beta$ acts as:

  • backward motion inside each cycle $C_i$,
  • plus a jump from the end of $C_i$ to the end of $C_{i-1}$.

Thus $\beta$ connects all cycles into one chain.

Step 4: $\beta$ is a single $n$-cycle

Start at any element, say $c_{1,1}$, and repeatedly apply $\beta$.

  • Within $C_1$, we traverse all elements in reverse order:

$$ c_{1,1} \to c_{1,m_1} \to \cdots \to c_{1,2}. $$

  • Then $\beta$ jumps into $C_r$, then traverses it backward, then jumps into $C_{r-1}$, and so on.

Thus the orbit of $\beta$ visits:

  1. every element of $C_r$,
  2. every element of $C_{r-1}$,
  3. $\dots$,
  4. every element of $C_1$,

with no repetition until all elements are exhausted.

Hence $\beta$ is a single cycle of length $n$, i.e., an $n$-cycle.

Step 5: Conclusion

We have constructed two $n$-cycles $\alpha$ and $\beta$ such that

$$ \pi = \alpha\beta. $$

Therefore, every even permutation in $S_n$ is a product of exactly two $n$-cycles.

Final conclusion

A permutation $\pi \in S_n$ can be written as a product of an even number of transpositions if and only if it can be written as a product of exactly two $n$-cycles. ∎