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

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. –  Dylan Moreland Dec 27 '11 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.) –  Martin Sleziak Dec 27 '11 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. –  Ryan Dec 27 '11 at 10:25

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 –  Ryan Dec 27 '11 at 10:30
@Ryan Glad to be of help; you're welcome. Thank you for your kind words, Ryan. –  Srivatsan Dec 27 '11 at 10:33

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 \}.$ –  Geoff Robinson Dec 27 '11 at 11:18

Sorry if this should be a new post. Please let me know if it should. I'm asking for clarification for Srivatsan's proof - based on Fraleigh's - so I thought it'd be more convenient for future readers if I asked here. Thanks.

$\Large{\text{1 -}}$ How exactly does $\orb(ts) \equiv \orb(s) + 1 \pmod 2 \Longrightarrow \orb(t_1 t_2 \cdots t_k s) \equiv \orb(s) + k \pmod 2$?

My guess --- I understand the proof for any transposition $t$ - $$\orb(\color{green}{ts}) \equiv \orb(\color{cornflowerblue}{s}) +1\pmod 2 \tag{\clubsuit}$$ So do we just apply this to $\orb(\color{green}{t_1 t_2s})$ to get - $$\orb(\color{green}{t_1 t_2s}) \equiv \orb(\color{cornflowerblue}{t_1s}) + 1 \pmod 2 ?$$

My concern is that the RHS of {$\clubsuit$} has $\color{cornflowerblue}{s}$, NOT ($ts$).

$\Large{\text{2 -}}$ Shouldn't $$\orb(t_1 t_2 \cdots t_k) \equiv n + k \pmod 2 \iff k \equiv \orb(t_1 t_2 \cdots t_k) \LARGE{\text{ MINUS }} \normalsize n \pmod 2 ?$$ $\Large{\text{3 -}}$ How does $k \equiv \orb(\sigma) - n \pmod 2$ mean that k (= parity of the number of transpositions) cannot be both odd and even? My introductory course didn't cover signature or invariant.

$\Large{\text{4 -}}$ Many thanks to Ryan and Srivatsan for separating ($\clubsuit$) as a lemma. I was completely confused over - in Fraleigh's book - how ($\clubsuit$) related to the Theorem. But how would you expect to need ($\clubsuit$) to prove the theorem? If not for you and the textbook, I'd never see to start with ($\clubsuit$).

-
Yes. This should be a comment to Srivatsan's answer and possibly a new question. –  robjohn Dec 23 '12 at 23:07
The website won't let me add comments to Srivatsan's answer? Does anyone else have this problem? If yes, I'll start a new question. –  Frank Dec 24 '12 at 20:59
As described here, you need at least 50 reputation to comment on someone else's post. –  robjohn Dec 24 '12 at 21:40