Proof that no permutation can be expressed both as the product of an even number of transpositions and as a product of an odd number of transpositions

I am aware that there are a couple of well-known proofs of this theorem, but I'm specifically grappling with the proof given in Fraleigh's A First Course in Abstract Algebra (Theorem 9.15 in the textbook).

Let $s$ be a permutation in the symmetric group of degree $n$, and let $t$ be a transposition $(i,j)$ in the same group. If $n$ is $1$ or infinite, we are done. Otherwise, ....[details of the proof omitted.] (We use the right-to-left convention to multiply permutations.)

Okay, we have shown that the number of orbits of $s$ and $ts$ differ by 1. This part, I understand. But I don't understand how to infer the theorem from here. I would be very grateful if someone can help me clear my blind spot. Thank you so much!

Added by Dylan. Here is Fraleigh's explanation (please don't sue me):

We have shown that the number of orbits of $\tau \sigma$ differs from the number of orbits of $\sigma$ by $1$. The identity permutation $\iota$ has $n$ orbits, because each element is the only member of its orbit. Now the number of orbits of a given permutation $\sigma \in S_n$ differs from $n$ by either an even or odd number, but not both. Thus it is impossible to write $$ \sigma = \tau_1 \tau_2 \cdots \tau_m \iota $$ where the $\tau_k$ are transpositions, in two ways, once with $m$ even and once with $m$ odd. $\qquad \diamond$

Solution 1:

Let $\newcommand{\orb}{\operatorname{orbits}} \orb(s)$ be the number of orbits in $s$. I will assume you have already showed that $\orb(ts)$ differs from $\orb(s)$ by $1$ for any transposition $t$. In particular, we have $$\orb(ts) \equiv \orb(s) + 1 \pmod 2 .$$ By a simple induction (on $k$), this implies that $$\orb(t_1 t_2 \cdots t_k s) \equiv \orb(s) + k \pmod 2$$ for any sequence of $k$ transpositions $t_1, \ldots, t_k$. Finally, setting $s$ to be the identity permutation, we have $$ \orb(t_1 t_2 \cdots t_k) \equiv n + k \pmod 2. \tag{$\dagger$} $$

Now if a permutation $\sigma$ is expressed as a product of transpositions as $\sigma= t_1 t_2 \cdots t_k$, then $(\dagger)$ says that $k \equiv \orb(\sigma) + n \pmod 2$. In other words, in any representation of $\sigma$ as a product of transpositions, the parity of the number of transpositions used is an invariant, equal to $(\orb(\sigma) + n) \bmod 2$. This invariant of the permutation is what will shortly (in your book!) be called its signature.

Solution 2:

I still find the polynomial (in $n$ commuting indeterminates) $s(x_1,x_2,\ldots, x_n) = \prod _{i < j} (x_i - x_j)$ to be the easiest way to see that the sign of a permutation $\sigma$ is well defined. Setting $s^{\sigma}(x_1,x_2,\ldots, x_n) = \prod _{i < j} (x_{\sigma(i)} - x_{\sigma(j)})$ for a permutation $\sigma$ makes it clear that $s^{\sigma} = \pm s,$ and that the sign is $(-1)^{m(\sigma)},$ where $m(\sigma)$ is the number of ordered pairs $(i,j)$ with $i < j$ and $\sigma(i) > \sigma(j).$ It is clear that $(-1)^{m(\sigma)} = -1$ if $\sigma$ is a transposition. This doesn't really help to explain the proof in Fraleigh, though.