Let $\sigma \in S_n$ be a product of $r$ disjoint cycles. Show that $\sigma$ can be written as $n-r$ transpositions.

Question

Note that in this problem we are counting all $1-$cycles when computing $r$. For example, if we are in $S_4$ and we have the permutation $\sigma = (1 \ 2)$, $r$ in this case would be $3$ because $(1 \ 2)$ can be also written as $(1 \ 2)(3)(4)$. In this case, it is obvious that we can indeed write this as $4-3=1$ transpositions.

The trouble is that I'm not quite sure how to approach this question. I tried some things with induction (on $r$) and it doesn't seem to work for me. The base case when $r=1$ is quite simple but I cannot get the induction step to follow.

I also tried constructing an argument that would use the fact that each cycle of length $k$ can be written as exactly $k-1$ transpositions, but I'm not quite sure how to morph that into something that would produce a complete proof.

As always, any and all help is much appreciated.

Answer 1

Fix the integer $m \ge 1$.

Statement $\quad \mathcal C(r): \;$ Any permutation $\sigma$ of a set $X$ with cardinality $n$ less than or equal to $m$ that can expressed as the product of $r$ disjoint cycles can be expressed as the product of $n-r$ transpositions.

Induction on $r$

Base Case: $r = 1$ - ✔.

Step Case:

Assume $\mathcal C(r)$ is true for $r \ge 1$ and let $\sigma$, a permutation on a set with $n$ elements where $n \le m$, be decomposed into $r+1$ disjoint cycles ,

$\tag 1 \sigma = \bigr(\sigma_1 \circ \dots \circ \sigma_r \bigr) \circ (\sigma_{r+1})$

Let $k$ be the length of cycle $\sigma_{r+1}$ so that

$\quad \sigma_1 \circ \dots \circ \sigma_r$

represents a permutation on a set with $n - k$ elements as the product of $r$ cycles. Since $\mathcal C(r)$ is true and $n - k \le n \le m$, it can be expressed as $(n - k) -r$ transpositions.

Also, $\sigma_{r+1}$ can be expressed as $k - 1$ transposition (see base case).

Substituting these transposition back into $\text{(1)}$ we see that $\sigma$ can be written as

$\quad \bigr(n - k -r\bigr) + (k - 1) = n -(r+1)$

and the induction is complete.

Answer 2

Hint: Let $\sigma$ be a permutation of a finite set $X$ with $n$ elements. If $\sigma$ is represented as the product of $r$ disjoint cycles, $\sigma_1,\sigma_2,\dots,\sigma_r$ there is a corresponding partition of $X$ into $r$ blocks $X_1,X_2,\dots,X_r$ with full cycle permutations $\sigma_k: X_k \to X_k$.