# 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$

• I added a scan of Fraleigh's proof. What seems confusing about it? In any event, I think Srivatsan's perspective should clear it up. Dec 27, 2011 at 3:04
• Related: math.stackexchange.com/questions/46403/… (But not a duplicate, since OP specifically says that he know that there are several proof s of this and he is asking about one specific proof. I added the link since it might be useful for someone looking for other proofs.) Dec 27, 2011 at 9:04
• Thanks for helpfully adding the scan! My confusion arose from Fraleigh implicitly setting s to be the identity here (multiplying it by the sequence of transpositions), but still using the same symbol to now refer to the new expression, without explicitly indicating the switch. And I guess I confused myself further by carelessly thinking about the number of orbits instead of the parity of the number of orbits. Srivatsan's answer below is excellent because he used different symbols to denote the two different permutations, and it also reads more intuitively than Fraleigh's concise proof. Dec 27, 2011 at 10:25

## 2 Answers

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.

• Thank you! Excellent elucidation! This was my maiden post in this forum, and I'm astonished at the responsiveness and quality of the community. Loving it! Such a useful resource for students who have to rely on self-study. Cheers! Oh, and I now realise that the sign of a permutation is actually short for "signature" lol Dec 27, 2011 at 10:30
• @Ryan Glad to be of help; you're welcome. Thank you for your kind words, Ryan. Dec 27, 2011 at 10:33
• Does Fraleigh actually ever define the signature? Apr 19, 2016 at 3:43

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.

• I should probably have added that it is clear that $\sigma \to (-1)^{m(\sigma)}$ is a group homomorphism from $S_n \to \{1,-1 \}.$ Dec 27, 2011 at 11:18