# 2.16 Sign

## 2.16.1 Definition of odd and even permutations

Theorem 2.15.3 says that every permutation can be expressed as a product of transpositions.

###### Definition 2.16.1.

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.)

###### Example 2.16.1.
• $(1,2)$ is odd.

• $\operatorname{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},\ldots,a_{m})$ as a product of $m-1$ transpositions

 $(a_{1},\ldots,a_{m})=(a_{1},a_{2})(a_{2},a_{3})\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.

## 2.16.2 The odd xor even theorem

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.

###### Theorem 2.16.1.

No permutation is both odd and even.

###### Proof.

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}\cdots t_{2a}=t^{\prime}_{1}t^{\prime}_{2}\cdots t^{\prime}_{2b+1}$

then we could rearrange to get

 $\operatorname{id}=t_{2a}t_{2a-1}\cdots t_{2}t_{1}t^{\prime}_{1}t^{\prime}_{2}% \cdots t^{\prime}_{2b+1}$

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},\ldots,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

 $\displaystyle s(f)$ $\displaystyle=x_{s(1)}x_{s(2)}+x_{s(3)}^{4}+x_{s(5)}$ $\displaystyle=x_{2}x_{3}+x_{1}^{4}+x_{5}.$

Now define

 $\Delta_{n}=\prod_{1\leqslant i

so that, for example,

 $\Delta_{3}=(x_{1}-x_{2})(x_{1}-x_{3})(x_{2}-x_{3}).$

Let $t=(a,b)$ be any transposition, where $a. We have $t(\Delta_{n})=-\Delta_{n}$, because $t$ only affects factors of $\Delta_{n}$ containing $x_{a}$ or $x_{b}$, and the only factors to change sign are $(x_{a}-x_{i})$ with $a and $(x_{i}-x_{b})$ with $a\leqslant i, 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 $\Delta_{n}$ to $-\Delta_{n}$. Since the identity sends $\Delta_{n}$ to $\Delta_{n}$, it cannot be written as the product of an odd number of transpositions. ∎

## 2.16.3 Sign of a permutation

###### Definition 2.16.2.
• The sign of a permutation is $1$ if it is even and $-1$ if it is odd.

• We write $\operatorname{sign}(s)$ for the sign of the permutation $s$.

So if $s$ can be written as a product of $m$ transpositions, $\operatorname{sign}(s)=(-1)^{m}$.

###### Lemma 2.16.2.

For any two permutations $s$ and $t$, $\operatorname{sign}(st)=\operatorname{sign}(s)\operatorname{sign}(t)$

###### Proof.

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

 $\displaystyle\operatorname{sign}(st)$ $\displaystyle=(-1)^{n+m}$ $\displaystyle=(-1)^{m}(-1)^{n}$ $\displaystyle=\operatorname{sign}(s)\operatorname{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.

## 2.16.4 Two results on the sign of a permutation

###### Lemma 2.16.3.
1. 1.

Even length cycles are odd and odd length cycles are even.

2. 2.

If $s$ is any permutation, $\operatorname{sign}(s)=\operatorname{sign}(s^{-1})$.

###### Proof.
1. 1.

We saw in the proof of Lemma 2.15.2 that if $a=(a_{1},\ldots,a_{m})$ is any $m$-cycle,

 $(a_{1}\ldots,a_{m})=(a_{1},a_{2})(a_{2},a_{3})\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.

2. 2.

If $s=t_{1}\cdots t_{m}$ is a product of $m$ transpositions, $s^{-1}=t_{m}^{-1}\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 $\operatorname{sign}(a_{1},\ldots,a_{m})=(-1)^{m-1}$.