I learned the following theorem about the properties of permutation from Gallian's Contemporary Abstract Algebra.
Theorem 5.4 $\;$ Always Even or Always Odd
If a permutation $\alpha$ can be expressed as a product of an even number of $2$-cycles, then every decomposition of $\alpha$ into a product of $2$-cycles must have an even number of $2$-cycles. In symbols, if
$$
\alpha = \beta_1 \beta_2 \dotsm \beta_r
\quad\text{and}\quad
\alpha = \gamma_1 \gamma_2 \dotsm \gamma_s
$$
where the $\beta$'s and the $\gamma$'s are $2$-cycles, then $r$ and $s$ are both even or both odd.
When I tried to reconstruct the proof myself, I found that it suffices to prove the following lemma:
If $\epsilon=\beta_1\beta_2\cdots\beta_r$ where $\beta$'s are $2$-cycles, then $r$ is even.
The original proof for this lemma uses the following key property of the product of $\beta_1\beta_2$:
The product can always be expressed in one of the following forms on the left:
$$\begin{align}(ab)(ab)&=\epsilon\\
(ab)(ac)&=(bc)(ab)\\
(ab)(cd)&=(cd)(ab)\\
(ab)(bc)&=(bc)(ac)\end{align}$$
The proof for the lemma is based on such property and mathematical induction. I found it really hard to remind of such property, so I set it as an exercise to give another proof. However, I have no idea how to actually do it.
So here is my question:
Does anybody know an alternative proof of the lemma or the theorem?
Best Answer
Here's a nice proof that uses group actions.
Let $x_1,\ldots,x_n$ be $n$ unknowns, and consider $$\Delta= \prod_{1\leq i\lt j\leq n} (x_j-x_i).$$
For example, for $n=4$, we would have $$\Delta = (x_2-x_1)(x_3-x_1)(x_4-x_1)(x_3-x_2)(x_4-x_2)(x_4-x_3).$$
Given a permutation $\sigma\in S_n$, define a function $f_{\sigma}\colon \{\Delta,-\Delta\} \to \{\Delta,-\Delta\}$ by letting $$f_{\sigma}(\Delta) = \prod_{1\leq i\lt j\leq n} (x_{\sigma(j)}-x_{\sigma(i)}),$$ and $f_{\sigma}(-\Delta)=-f_{\sigma}\Delta$.
Note that since $\sigma$ is a permutation, $f_{\sigma}(\Delta)=\Delta$ or $f_{\sigma}(\Delta) = -\Delta$. Also, if $\sigma,\rho$ are two permutations, then $f_{\sigma}\circ f_{\rho} = f_{\sigma\rho}$, as is easy to verify.
Now, let's consider what a transposition $\tau=(a,b)$ does to $\Delta$. Without loss of generality, say $a\lt b$.
The factors $(x_j-x_i)$ with neither $i$ nor $j$ equal to $a$ nor $b$ are unchanged.
For the pairs with exactly one index in $\{a,b\}$, we have two classes: those in which the other index is between $a$ and $b$, and those where the other index is not between $a$ and $b$.
If the other index is between $a$ and $b$, then $x_j-x_a$ is sent to $-(x_b-x_j)$ and $x_b-x_j$ is sent to $-(x_j-x_a)$; the two sign changes cancel each other out.
If the other index is larger than $b$, then $x_j-x_a$ and $x_j-x_b$ are swapped, with no sign changes.
If the other index is smaller than $a$, then $x_a-x_i$ and $x_b-x_i$ are swapped, with no sign changes.
Finally, the factor $x_b-x_a$ is sent to $-(x_b-x_a)$.
In summary, if $\tau$ is a transposition, then $f_{\tau}(\Delta)=-\Delta$, $f_{\tau}(-\Delta)=\Delta$.
Now take an arbitrary permutation $\sigma$, and express it as a product of transpositions in two different ways: $$\sigma = \tau_1\cdots \tau_r = \rho_1\cdots\rho_s.$$ Then $$f_{\sigma}(\Delta) = f_{\tau_1\cdots\tau_r}(\Delta) = f_{\tau_1}\circ\cdots\circ f_{\tau_r}(\Delta) = (-1)^r\Delta$$ and $$f_{\sigma}(\Delta) = f_{\rho_1\cdots\rho_s}(\Delta) = f_{\rho_1}\circ\cdots\circ f_{\rho_s}(\Delta) = (-1)^s\Delta.$$ Therefore, $(-1)^r\Delta = (-1)^s\Delta$, so $r$ and $s$ have the same parity: both odd, or both even.