Theorem 2.15.3 says that every permutation can be expressed as a product of transpositions.
A permutation is odd if it can be expressed as a product of an odd number of transpositions and even if it can be expressed as a product of an even number of transpositions.
(Sometimes people refer to the parity of a permutation to mean whether it is odd or even.)
$(1,2)$ is odd.
$\mathrm{id}=(1,2)(1,2)$ is even.
$(1,2,3)=(1,2)(2,3)$ is even.
The expression for an $m$-cycle $a=({a}_{1},\mathrm{\dots},{a}_{m})$ as a product of $m-1$ transpositions
$$({a}_{1},\mathrm{\dots},{a}_{m})=({a}_{1},{a}_{2})({a}_{2},{a}_{3})\mathrm{\cdots}({a}_{m-1},{a}_{m})$$ |
in Lemma 2.15.2 shows that an $m$ cycle is even if $m$ is odd and odd if $m$ is even.
It seems possible that a permutation could be odd AND even at the same time, but this isn’t the case. The proof is a little strange because it involves a seemingly-unrelated polynomial — if you prefer a proof that refers only to permutations, take a look at the unassessed exercises.
No permutation is both odd and even.
Let $s\in {S}_{n}$. If $s$ could be written both as a product of an even number and an odd number of transpositions, say
$$s={t}_{1}{t}_{2}\mathrm{\cdots}{t}_{2a}={t}_{1}^{\prime}{t}_{2}^{\prime}\mathrm{\cdots}{t}_{2b+1}^{\prime}$$ |
then we could rearrange to get
$$\mathrm{id}={t}_{2a}{t}_{2a-1}\mathrm{\cdots}{t}_{2}{t}_{1}{t}_{1}^{\prime}{t}_{2}^{\prime}\mathrm{\cdots}{t}_{2b+1}^{\prime}$$ |
which expresses the identity permutation as a product of an odd number $2(a+b)+1$ of transpositions. So it’s enough to show that this is impossible.
Introduce variables ${x}_{1},{x}_{2},\mathrm{\dots},{x}_{n}$. Given any polynomial $f$ in these variables and any permutation $s\in {S}_{n}$, we define a new polynomial $s(f)$ which is obtained by replacing every variable ${x}_{i}$ in $f$ by ${x}_{s(i)}$. For example, if $s=(1,2,3)$ and $f={x}_{1}{x}_{2}+{x}_{3}^{4}+{x}_{5}$ then
$s(f)$ | $={x}_{s(1)}{x}_{s(2)}+{x}_{s(3)}^{4}+{x}_{s(5)}$ | ||
$={x}_{2}{x}_{3}+{x}_{1}^{4}+{x}_{5}.$ |
Now define
$$ |
so that, for example,
$${\mathrm{\Delta}}_{3}=({x}_{1}-{x}_{2})({x}_{1}-{x}_{3})({x}_{2}-{x}_{3}).$$ |
Let $t=(a,b)$ be any transposition, where $$. We have $t({\mathrm{\Delta}}_{n})=-{\mathrm{\Delta}}_{n}$, because $t$ only affects factors of ${\mathrm{\Delta}}_{n}$ containing ${x}_{a}$ or ${x}_{b}$, and the only factors to change sign are $({x}_{a}-{x}_{i})$ with $$ and $({x}_{i}-{x}_{b})$ with $$, a total of $2(b-a)-1$ sign changes (as $({x}_{a}-{x}_{b})$ appears in both cases). It follows that any product of an odd number of transpositions sends ${\mathrm{\Delta}}_{n}$ to $-{\mathrm{\Delta}}_{n}$. Since the identity sends ${\mathrm{\Delta}}_{n}$ to ${\mathrm{\Delta}}_{n}$, it cannot be written as the product of an odd number of transpositions. ∎
The sign of a permutation is $1$ if it is even and $-1$ if it is odd.
We write $\mathrm{sign}(s)$ for the sign of the permutation $s$.
So if $s$ can be written as a product of $m$ transpositions, $\mathrm{sign}(s)={(-1)}^{m}$.
For any two permutations $s$ and $t$, $\mathrm{sign}\mathit{}\mathrm{(}s\mathit{}t\mathrm{)}\mathrm{=}\mathrm{sign}\mathit{}\mathrm{(}s\mathrm{)}\mathit{}\mathrm{sign}\mathit{}\mathrm{(}t\mathrm{)}$
If $s$ can be written as a product of $m$ transpositions and $t$ can be written as a product of $n$ transpositions, then $st$ can be written as a product of $m+n$ transpositions. So
$\mathrm{sign}(st)$ | $={(-1)}^{n+m}$ | ||
$={(-1)}^{m}{(-1)}^{n}$ | |||
$=\mathrm{sign}(s)\mathrm{sign}(t)$ |
∎
This rule about the sign of a product means that
an even permutation times an even permutation is even,
an even permutation times an odd permutation is odd, and
an odd permutation times an odd permutation is even
just like when we multiply odd and even integers.
Even length cycles are odd and odd length cycles are even.
If $s$ is any permutation, $\mathrm{sign}(s)=\mathrm{sign}({s}^{-1})$.
We saw in the proof of Lemma 2.15.2 that if $a=({a}_{1},\mathrm{\dots},{a}_{m})$ is any $m$-cycle,
$$({a}_{1}\mathrm{\dots},{a}_{m})=({a}_{1},{a}_{2})({a}_{2},{a}_{3})\mathrm{\cdots}({a}_{m-1},{a}_{m})$$ |
so an $m$-cycle can be written as a product of $m-1$ transpositions. The number of transpositions in this expression therefore has the opposite parity to $m$, as required.
If $s={t}_{1}\mathrm{\cdots}{t}_{m}$ is a product of $m$ transpositions, ${s}^{-1}={t}_{m}^{-1}\mathrm{\cdots}{t}_{1}^{-1}$. But the inverse of a transposition is a transposition, so ${s}^{-1}$ is also the product of $m$ transpositions.
∎
Another way to express the first part of this lemma would be to say that $\mathrm{sign}({a}_{1},\mathrm{\dots},{a}_{m})={(-1)}^{m-1}$.