Inversions and Multiplicativity of the Sign of a Permutation

Question

The question is mainly about showing, for two permutations $\sigma, \pi \in S_{n}$, that $\mathrm{sgn}(\sigma \pi) = \mathrm{sgn}(\sigma) \mathrm{sgn}(\pi)$ using inversions of permutations (i.e. a pair $\{i,j\}$ where $i<j$ is an inversion of $\sigma$ if $\sigma(i) > \sigma{j}$).

The proof I saw was that $\{i,j\}$ is an inversion of $\sigma \pi$ if and only if $\{i,j\}$ is an inversion of $\pi$ and $\{\pi(i),\pi(j)\}$ is not an inversion of $\sigma$, OR $\{i,j\}$ is not an inversion of $\pi$ and $\{\pi(i),\pi(j)\}$ is an inversion of $\sigma$, which is easy to verify.

However, in the following step, it was claimed that $\mod 2$ we have:

$\#$ of inversions of $\sigma \pi$ $\equiv$ $\#$ of inversions of $\pi$ + $\#$ of inversions of $\sigma$

Then, the desired result follows as the sign of a permutation was defined to be the number of inversions. The main problem I have with this proof is the fact that the $\#$ of inversions of $\sigma \pi$ $\equiv$ $\#$ of inversions of $\pi$ + $\#$ of inversions of $\sigma$ in $\mod 2$. I don't see why does that relationship hold from the previous results.

Thanks for the help.

Answer 1

One way of looking at the given proof's argument is to take the $\binom{n}{2}$ pairs $\{i,j\}$, and count the number of each relevant occurrence:

1. Let $A$ be the number of pairs $\{i,j\}$ such that $\{i,j\}$ is an inversion of $\pi$ but $\{\pi(i), \pi(j)\}$ is not an inversion of $\sigma$.
2. Let $B$ be the number of pairs $\{i,j\}$ such that $\{\pi(i), \pi(j)\}$ is an inversion of $\sigma$ but $\{i,j\}$ is not an inversion of $\pi$.
3. Let $C$ be the number of pairs $\{i,j\}$ such that $\{i,j\}$ is an inversion of $\pi$ and $\{\pi(i), \pi(j)\}$ is an inversion of $\sigma$.

Note that $B+C$ is the number of inversions of $\sigma$, and $A+C$ is the number of inversions of $\pi$.

The given argument is that the number of inversions of $\sigma\pi$ is $A+B$, which is congruent mod 2 to $A+B+2C = (A+C)+(B+C)$. This is precisely the desired relation.