Question about permutations: How to show $\sigma(P)=(-1)^{\imath(\sigma)}P$?

Question

A permutation of a finite set $X$ is any bijection from $X$ to $X$. We denote by $S(X)$ the set of all permutations of $X$. If $I_n:=\{1, \ldots, n\}$ we write $S_n$ instead of $S(I_n)$.

Define $$P:=\prod_{i<j} (j-i)\quad\textrm{and}\quad \sigma(P)=\prod_{i<j}(\sigma_j-\sigma_i),$$ where $\sigma\in S_n$ and $\sigma_j:=\sigma(j)$.

How to show $$\sigma(P)=(-1)^{\imath(\sigma)} P,$$ where $$\imath(\sigma):=\#\{(i, j)\in I_n\times I_n; i<j\quad \textrm{and}\quad \sigma_i>\sigma_j\}?$$ In other $\imath(\sigma)$ is the number of inversions of $\sigma$.

Since the product $\displaystyle \prod_{i<j}$ makes the notation a little hard it worths to notice the following identity $$\prod_{i<j}(j-i)=\prod_{j=2}^{n} \prod_{i=1}^{j-1}(j-i)=\prod_{j=1}^n (j-1)!$$

Obs: This is related with my previous question How to write $\displaystyle\prod_{i<j} (j-i)$ as an explicit sum?

Answer 1

Hint: Show first that $$\prod_{i<j} (j-i) = \prod_{i<j} (\max(\sigma_i,\sigma_j) - \min(\sigma_i,\sigma_j)).$$ This holds because the set of unordered pairs $\{i,j\}$ is the same as the set of unordered pairs $\{\sigma_i,\sigma_j\}$ (there are several ways of showing this).

Given that, complete the proof by showing that $$ \prod_{i<j} (\max(\sigma_i,\sigma_j) - \min(\sigma_i,\sigma_j)) = (-1)^{\iota(\sigma)} \prod_{i<j} (\sigma_j-\sigma_i).$$ This follows directly from the definition of $\iota(\sigma)$.

Answer 2

The symmetric group is generated by the elementary transpositions. These are odd permutations, hence the signature of a permutation $\sigma$ is also the parity of the number of elementary transpositions which compose $\sigma$.

Thus it is enough to show that for an elementary transposition $\tau=(i\,i+1)$, $\tau(P)=-P$.

Only the factors of $P$ that involve $i$ or $i+1$ are changed in $\tau(P). There ar of 3 kinds:

• if $j>i+1$, the factors $ j-i$ and $ j-i-1$ are simply exchanged.
• if $j<i$, the factors $i-j$ and $i+1-j$ are exchanged.
• lastly, $i+1-i=1$ becomes $i-i-1=-1$.

Thus under an elementary transposition, $P$ becomes $-P$. As for any permutation $\sigma$, $i(\sigma)=(-1)^r$, where $r$ is the number of transpositions which compose $\sigma$, the proof is complete.