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

Question

I am a high school teacher attempting to prove in a programming class why the answer to http://www.usaco.org/index.php?page=viewproblem2&cpid=785, at least if all the cow heights are unique, is $1$ less than the number of cows that are out of order from their original positions (slightly trickier to deal with duplicate heights, but the simpler version here is enough trouble for now).

This is because the cows that are out of order form a cycle permutation, and the problem asks us to undo this cycle with transpositions. I know from my own college-level classes that a $k-\text{cycle}$ decomposes to at most $k-1$ transpositions, if you're trying to minimize number of transpositions, and I can demonstrate via construction that $(1 2 3 4 ... k)[x] = (1 2) (2 3) \dots (k-1 k)[x],$ and my students get this.

My more astute students want to know how I know it can't be done in any fewer than $k-1$ transpositions, but they do not have the necessary background in Group Theory or permutations to make this easy to prove to them. For instance, this exact question was already asked at every k cyclic is a product of at least k-1 distinct tranpositions, but the answers there are too rigorous for your average $10^{\text{th}}$ grader.

FWIW, because we have already covered minimum spanning trees, I attempted to make an argument that if you consider the swapped elements as vertices and the transpositions ("swaps") as edges in a graph, that you need $k-1$ edges/swaps for the same reason a spanning tree needs $k-1$ edges. But the proof of this, showing how disconnected components in the graph can't "connect" with each other to form a cycle that touches all elements, did not land, and I fear that $-$ even though I'm blessed my students know some graph theory from my prior lessons $-$ your average $10^{\text{th}}$ grader isn't going to follow all of that either.

What's a simple, intuitive explanation for why there's no magic combination of $k-2$ transpositions (or less) for a $k-\text{cycle}?$

Answer 1

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.

Answer 2

Three ingredients can be used to supply a demonstration.

$\text{(1)}$ If $\sigma$ is a cycle of length $l$ and $a \in \text{Orbit}(\sigma)$ then $\bigr(a \,\sigma(a) \bigr) \circ \sigma$ is a cycle of length $l - 1$.

$\text{(2)}$ Induction.

$\text{(3)}$ A symbol processing algorithm based on the transposition algebra rules:

\begin{align}(1) \quad (ab)(ab)&=1_{Id}\\ (2) \quad (ab)(cd)&=(cd)(ab)\\ (3) \quad (ab)(bc)&=(ca)(ab)\\ (4) \quad (ab)(bc)&=(bc)(ca)\end{align}

Here is a mathematical statement underpinning such an algorithm:

Let any permutation $\psi$ be represented as a product (composition) of $t$ transpositions,

$\tag 1 \psi = {\displaystyle \prod _{i=1}^{t}\, \tau_i}$

such that $\psi(a) \ne a$.

Then there exists a representation (but not unique)

$\tag 2 \psi = \bigr(a \,\psi(a) \bigr) \,{\displaystyle \prod _{i=1}^{t'}\, {\tau}'_i}$

satisfying the following two conditions:

$\tag 3 \forall i \; {\tau}'_i(a) = a$

$\tag 4 t' \in \{ t - 1 - 2m \mid m \in \{0,1,2,\dots\}\}$

---

The OP could challenge their students to implement such algorithms in a computer language.