What is a simple proof for a $k-\text{Cycle}$ Permutation needing at least $(k-1)$ transpositions in its decomposition?

Let's consider what (cycle types of) permutations we can possibly get from a product of $d$ transpositions, as $d$ grows.

• When $d = 1$ we can only get a transposition (cycle type $2$).
• When $d = 2$ we can only get either a $3$-cycle or two disjoint transpositions (cycle types $3$ and $22$). If we allow the two transpositions to cancel each other out, we can also get the identity (cycle type $1$).
• When $d = 3$ we can only get either a $4$-cycle, a $3$-cycle and a transposition, or three disjoint transpositions (cycle types $4, 32, 222$). Again if we allow two of the transpositions to cancel each other out we can also get a transposition (cycle type $2$).

And so forth. Each small value of $d$ is a nice little puzzle you can go through quite explicitly with students. Eventually you and/or your students might formulate a conjecture about which cycle types appear, and that conjecture might look like the following: if a product of $d$ transpositions has cycles of length $\ell_1, \ell_2, \dots \ell_k$, then

$$\sum_{i=1}^k (\ell_i - 1) \le d.$$

(and moreover the difference is even). This is true and you can prove it straightforwardly by induction on $d$, just by looking at the effect of multiplying by a transposition on a cycle decomposition. There are four cases:

• You multiply by a transposition disjoint from your existing cycle decomposition. Then you just add a new transposition, and $\sum_{i=1}^k (\ell_i - 1)$ goes up by $1$.
• You multiply by a transposition $(ij)$ which is connected to one cycle $(i_1 \dots i_{\ell}), i_1 = i, i_k \neq j$. Then $(i_1 \dots i_{\ell})(ij) = (i_1 j i_2 \dots i_{\ell})$ which is an $\ell+1$-cycle, and again $\sum_{i=1}^k (\ell_i - 1)$ goes up by $1$.
• You multiply by a transposition $(ij)$ which is connected to two cycles $(i_1 \dots i_{\ell}), i_1 = i$ and $(j_1 \dots j_m), j_1 = j$. Then $(i_1 \dots i_{\ell})(j_1 \dots j_m)(ij) = (ij_2 \dots j_m j i_2 \dots i_{\ell})$ which is an $\ell + m$-cycle, and again $\sum_{i=1}^k (\ell_i - 1)$ goes up by $1$.
• You multiply by a transposition $(ij)$ which is connected to one cycle twice $(i_1 \dots i_{\ell}), i_1 = i, i_m = j$. Then $(i_1 \dots i_{\ell})(ij) = (i i_{m+1} \dots i_{\ell})(j i_2 \dots i_{m-1})$ is an $\ell-m+1$-cycle and an $m-1$-cycle, and now $\sum_{i=1}^k (\ell_i - 1)$ goes down by $1$.

(All of this should be done with pictures, ideally; working with cycle notation is really ugly compared to literally drawing some cycles.)

The desired result for a single cycle follows. The point of proving this stronger result is that it makes for a better inductive hypothesis. The issue with only thinking about a single cycle is that in the course of building up a cycle by transpositions some of the intermediate permutations may not be cycles, and an induction over arbitrary products of transpositions deals with this cleanly.

The quantity $\sum_{i=1}^k (\ell_i - 1)$ is called by at least one author the length of a permutation, although unfortunately that term already has a well-established meaning for Coxeter groups (which include the symmetric groups) and means something different (equivalent, for the symmetric groups, to computing the minimal number of simple transpositions $(i, i+1)$ needed to produce a given permutation, and in turn equivalent to the number of inversions). I don't know if this quantity has a well-established name but it really should. Note that $(-1)^{\sum (\ell_i-1)}$ is the sign.