1
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.