Theorem. If the identity is written as the product of $r$ transpositions, $id=τ_1τ_2\dots τ_r$, then $r$ is an even number.
Proof. We will employ induction on $r$. A transposition cannot be the identity; hence, $r > 1$. If $r = 2$, then we are done. Suppose that $r > 2$. In this case the product of the last two transpositions, $τ_{r−1}τ_r$, must be one of the following cases:
$(ab)(ab) = id\\ (bc)(ab) = (ac)(bc)\\ (cd)(ab) = (ab)(cd)\\ (ac)(ab) = (ab)(bc),$
where $a$, $b$, $c$, and $d$ are distinct.
The first equation simply says that a transposition is its own inverse. If this case occurs, delete $τ_{r−1} τ_r$ from the product to obtain $id=τ_1τ_2···τ_{r−3}τ_{r−2}$. By induction $r − 2$ is even; hence, $r$ must be even.
In each of the other three cases, we can replace $τ_{r−1} τ_r$ with the right-hand side of the corresponding equation to obtain a new product of $r$ transpositions for the identity. In this new product the last occurrence of $a$ will be in the next-to-the-last transposition. We can continue this process with $τ_{r−2} τ_{r−1}$ to obtain either a product of $r − 2$ transpositions or a new product of $r$ transpositions where the last occurrence of $a$ is in $τ_{r−2}$. If the identity is the product of $r − 2$ transpositions, then again we are done, by our induction hypothesis; otherwise, we will repeat the procedure with $τ_{r−3}τ_{r−2}$.
At some point either we will have two adjacent, identical transpositions canceling each other out or $a$ will be shuffled so that it will appear only in the first transposition. However, the latter case cannot occur, because the identity would not fix $a$ in this instance. Therefore, the identity permutation must be the product of $r − 2$ transpositions and, again by our induction hypothesis, we are done.
Question: That is the proof written in the book, but unfortunately after more than $10$ times reading I don't understand the last two paragraph (i.e., from "In each of the other three cases"). Is there another simpler proof or could someone please clarify what is going on?
Thank you.
Best Answer
Notice that in each of the three given identities
$(bc)(ab)=(ac)(bc)$
$(cd)(ab)=(ab)(cd)$
$(ac)(ab)=(ab)(bc)$
if you replace the left side with the right side, there is no longer an $a$ in the second parentheses. This means that each time you apply any of these identities, the rightmost occurrence of $a$ is one transposition further to the left.
Eventually either you will get two identical adjacent transpositions $(ax)(ax)=id$, so they disappear and you can apply induction to the shorter string of transpositions; or you end up with $a$ only appearing in the leftmost transposition of the entire product of transpositions, but this is impossible since then the permutation doesn't fix $a$, and so is not the identity.