Cycle Decomposition and Parity

Existence. Define a relation on $\{1,\dots,n\}$ by $a \sim b$ if $b = \sigma^t(a)$ for some integer $t$ (positive, negative, or zero, using that $\sigma$ is a bijection so $\sigma^{-1}$ exists). This is an equivalence relation: reflexive via $t=0$; symmetric since $b = \sigma^t(a) \implies a = \sigma^{-t}(b)$; transitive since $\sigma^t \circ \sigma^s = \sigma^{t+s}$. Let the equivalence classes (orbits of $\sigma$) be $O_1, \dots, O_k$, partitioning $\{1,\dots,n\}$. Fix an orbit $O_i$ and pick $a \in O_i$. Since $\{1,\dots,n\}$ is finite, the elements $a, \sigma(a), \sigma^2(a), \dots$ cannot all be distinct; let $r \ge 1$ be minimal with $\sigma^r(a) = \sigma^s(a)$ for some $0 \le s < r$. Applying $\sigma^{-s}$ (valid since $\sigma$ is a bijection) gives $\sigma^{r-s}(a) = a$ with $0 < r - s \le r$; by minimality of $r$ we must have $s = 0$, so $\sigma^r(a) = a$ and $a, \sigma(a), \dots, \sigma^{r-1}(a)$ are pairwise distinct (any earlier coincidence would contradict minimality of $r$ by the same argument). Since every element of $O_i$ is $\sigma^t(a)$ for some $t$, and $\sigma^r(a) = a$ forces $\sigma^t(a) = \sigma^{t \bmod r}(a)$, the orbit is exactly $O_i = \{a, \sigma(a), \dots, \sigma^{r-1}(a)\}$, of size $r$. Define $\gamma_i = (a\ \sigma(a)\ \sigma^2(a)\ \cdots\ \sigma^{r-1}(a))$, an $r$-cycle. By construction $\gamma_i$ agrees with $\sigma$ on $O_i$ and fixes everything outside $O_i$ (as a cycle by definition). Since $O_1,\dots,O_k$ partition $\{1,\dots,n\}$, the cycles $\gamma_1,\dots,\gamma_k$ are pairwise disjoint (disjoint supports), disjoint cycles commute (an element in one support is fixed by all other $\gamma_j$'s, so composing in any order gives the same map), and for any $x \in \{1,\dots,n\}$, $x$ lies in exactly one $O_i$, on which the product $\gamma_1\cdots\gamma_k$ acts exactly as $\gamma_i$ does, which is exactly as $\sigma$ does. Hence $\sigma = \gamma_1 \gamma_2 \cdots \gamma_k$.

Uniqueness. Suppose $\sigma = \delta_1 \cdots \delta_m$ is another expression as pairwise disjoint cycles with supports partitioning $\{1,\dots,n\}$. Fix $x$ in the support of some $\delta_j$ of length $\ell$, say $\delta_j = (x\ \sigma(x)\ \sigma^2(x)\ \cdots)$ — note that because the $\delta_i$ are disjoint and their product is $\sigma$, for $x$ in the support of $\delta_j$, the action of $\sigma$ on $x$ equals the action of $\delta_j$ alone (all other disjoint factors fix $x$). Iterating, $\sigma^t(x) = \delta_j^t(x)$ for all $t$, so the support of $\delta_j$ is precisely the orbit of $x$ under $\sigma$, and $\delta_j$ is the cycle $(x\ \sigma(x)\ \cdots\ \sigma^{\ell-1}(x))$ for $\ell = |O_i|$ where $O_i$ is that orbit. This is exactly the cycle $\gamma_i$ constructed above (possibly written starting at a different element of the same orbit, which is a cyclic rotation of the same cycle notation). Since every support of a $\delta_j$ must therefore be a full $\sigma$-orbit, and the orbits are exactly $O_1,\dots,O_k$, the multiset $\{\delta_1,\dots,\delta_m\}$ equals $\{\gamma_1,\dots,\gamma_k\}$ up to reordering and rotation. $\blacksquare$

By the Lemma it suffices to write an arbitrary cycle as a product of transpositions. For an $r$-cycle with $r \ge 2$,

which is verified directly: apply the right side to $a_1$ — only $(a_1\,a_2)$ moves it, sending $a_1 \mapsto a_2$, and no further transposition in the product (reading right to left) touches $a_2$ since none of them contain $a_2$, so the whole product sends $a_1 \mapsto a_2$, matching the cycle. Apply it to $a_i$ for $1 < i < r$: reading right to left, $(a_1\,a_2), \dots, (a_1\,a_{i-1})$ all fix $a_i$ (their supports are $\{a_1,a_j\}$ with $j < i$), then $(a_1\,a_i)$ sends $a_i \mapsto a_1$, then $(a_1\,a_{i+1})$ sends $a_1 \mapsto a_{i+1}$, and the remaining factors $(a_1\,a_{i+2}),\dots,(a_1\,a_r)$ fix $a_{i+1}$; so the total effect is $a_i \mapsto a_{i+1}$, matching the cycle. Finally apply it to $a_r$: all factors except the leftmost, $(a_1\,a_r)$, fix $a_r$, and that one sends $a_r \mapsto a_1$, matching the cycle. Every point outside $\{a_1,\dots,a_r\}$ is fixed by every factor, hence by the product. A $1$-cycle (identity on a point) is the empty product of transpositions. This proves the corollary, with $r-1$ transpositions used for an $r$-cycle. $\blacksquare$

We use the technique of tracking the change in cycle count under multiplication by a single transposition, which is the combinatorial heart of the argument.

Key Lemma. Let $\pi \in S_n$ have disjoint cycle decomposition (including $1$-cycles) with exactly $k$ cycles, and let $\tau = (a\,b)$ be a transposition, $a \ne b$. Then $\tau \pi$ has exactly $k+1$ or $k-1$ cycles in its disjoint decomposition: $k+1$ if $a,b$ lie in the same cycle of $\pi$, and $k-1$ if they lie in different cycles of $\pi$. Proof of Key Lemma. Case 1: $a$ and $b$ lie in the same cycle of $\pi$, say $\pi$'s decomposition contains the cycle $C = (a\ x_1\ x_2\ \cdots\ x_p\ b\ y_1\ \cdots\ y_q)$ (written so that reading forward from $a$ we reach $b$ after $p$ intermediate steps, possibly $p = 0$; here $p,q \ge 0$ and $p+q+2$ is the length of $C$), and all other cycles of $\pi$ are unaffected by left-multiplication by $\tau = (a\,b)$ since $\tau$ only touches $a,b$ and those other cycles don't contain $a$ or $b$. Compute directly: for $y_q$, $\pi$ sends $y_q \mapsto a$, then $\tau$ sends $a \mapsto b$, so $(\tau\pi)(y_q) = b$. For $x_p$, $\pi$ sends $x_p \mapsto b$, then $\tau$ sends $b \mapsto a$, so $(\tau\pi)(x_p) = a$. For all other elements $z$ of $C$ not equal to $x_p$ or $y_q$, $\pi(z) \notin \{a,b\}$ (since $\pi$ maps $z$ to the next element in the cycle, and only $x_p \mapsto b$ and $y_q \mapsto a$ hit $\{a,b\}$), so $\tau$ fixes $\pi(z)$ and $(\tau\pi)(z) = \pi(z)$. Tracing the action of $\tau\pi$ on $C$'s support starting at $a$: $a \mapsto x_1 \mapsto \cdots \mapsto x_p \mapsto a$ (a closed cycle of length $p+1$), and separately $b \mapsto y_1 \mapsto \cdots \mapsto y_q \mapsto b$ (a closed cycle of length $q+1$). So $C$ splits into two disjoint cycles under $\tau\pi$ (note $p+1 \ge 1$ and $q+1 \ge 1$ account correctly even when $p=0$ or $q=0$, giving a $1$-cycle fixed point). All other cycles of $\pi$ are untouched. Net change: one cycle becomes two, so the count goes from $k$ to $k+1$. Case 2: $a,b$ lie in different cycles of $\pi$, say $C_a = (a\ x_1\ \cdots\ x_p)$ and $C_b = (b\ y_1\ \cdots\ y_q)$ with $p, q \ge 0$. As before all other cycles are untouched. Compute: $\pi$ sends $x_p \mapsto a$ (or if $p=0$, $\pi$ sends $a \mapsto a$, i.e. the cycle is just $(a)$, handle uniformly by allowing the "previous element" of $a$ in its own cycle to be $a$ itself when $p=0$), then $\tau$ sends $a \mapsto b$. Similarly $\pi$ sends $y_q \mapsto b$ then $\tau$ sends $b \mapsto a$. All interior elements of $C_a, C_b$ are unaffected by $\tau$ since $\pi$ doesn't map them into $\{a,b\}$ except at the two junctions just described. Tracing $\tau\pi$ starting at $a$: $a \mapsto x_1 \mapsto \cdots \mapsto x_p \mapsto b \mapsto y_1 \mapsto \cdots \mapsto y_q \mapsto a$, a single cycle of length $p+q+2$ merging $C_a$ and $C_b$. Net change: two cycles become one, so the count goes from $k$ to $k-1$. This proves the Key Lemma. $\square$

Main argument by induction on $m$. We show: if $\sigma$ has disjoint decomposition with $k$ cycles and $\sigma = \tau_1 \cdots \tau_m$ is any product of $m$ transpositions, then $m \equiv n - k \pmod 2$. Base case $m = 0$: then $\sigma = e$, the identity, whose disjoint decomposition is $n$ trivial $1$-cycles, so $k = n$ and $n - k = 0 \equiv 0 = m \pmod 2$. ✓. Inductive step: Suppose the claim holds for all permutations expressible as a product of fewer than $m$ transpositions ($m \ge 1$), for every $n$. Let $\sigma = \tau_1 \cdots \tau_m$. Set $\pi = \tau_2 \cdots \tau_m$, a product of $m - 1$ transpositions, so $\sigma = \tau_1 \pi$. Let $\pi$ have $k'$ cycles in its disjoint decomposition; by the inductive hypothesis, $m - 1 \equiv n - k' \pmod 2$. By the Key Lemma applied to $\tau_1 \pi = \sigma$, the cycle count $k$ of $\sigma$ satisfies $k = k' + 1$ or $k = k' - 1$; either way $k \equiv k' + 1 \pmod 2$, i.e. $k' \equiv k - 1 \equiv k+1 \pmod 2$. Substituting,

so $m \equiv n - k \pmod 2$. This completes the induction. $\square$

Conclusion. Given the theorem's two expressions $\sigma = \tau_1\cdots\tau_m = \tau_1'\cdots\tau_{m'}'$, apply the main argument to each: with $k$ the (fixed, well-defined by the uniqueness Lemma above) number of cycles of $\sigma$'s disjoint decomposition, we get $m \equiv n-k \pmod 2$ and $m' \equiv n - k \pmod 2$, hence $m \equiv m' \pmod 2$. Therefore $(-1)^m = (-1)^{m'}$, so $\operatorname{sgn}(\sigma) := (-1)^m$ does not depend on which transposition expression was used — it is well-defined — and equals $(-1)^{n-k}$. $\blacksquare$

Write $\sigma$ as a product of $m$ transpositions and $\pi$ as a product of $m'$ transpositions (possible by the Corollary above). Concatenating gives an expression of $\sigma\pi$ as a product of $m + m'$ transpositions. By the Theorem, $\operatorname{sgn}(\sigma\pi) = (-1)^{m+m'} = (-1)^m(-1)^{m'} = \operatorname{sgn}(\sigma)\operatorname{sgn}(\pi)$, using that $\operatorname{sgn}$ is well-defined regardless of the transposition expression chosen. $\blacksquare$