Product formula for sign of permutation

Question

I would like help (a complete proof) that $$ (-1)^{Inv(\sigma)} = \prod_{1\leq i<j\leq n} \frac{\sigma(j)-\sigma(i)}{j-i} ,$$ where $Inv(\cdot)$ is the number of inversions of the permutation received as argument and $\sigma$ is a permutation in $S_n$.

The formula seems intuitive somehow, but I cannot manage to fully write a proof for it. The factors of the numerator product seem to coincide with the ones in the denominator, albeit with a negative sign where inversions are happening, but I can't fully convince myself each element at the numerator has exactly one correspondent in the denominator and vice versa.

EDIT: My book states as an obvious fact that the product in the numerator is equal to the one in the denominator, where each factor is multiplied by $\epsilon(i,j)$ ($-1$ iff (i,j) is an inversion for $\sigma$).. I can finish the proof from here, but it is not obvious to me.

Answer 1

1. Let $P = \{(i,j) \mid 1 \le i < j \le n \}$. Instead of $\prod_{1\leq i<j\leq n}$ we shall now write $\prod_{(i,j) \in P}$

2. Let $Q$ denote the set of all sets $\{i, j\}$ with $1 \le i, j \le n$ and $i \ne j$, i.e. the set of all subsets of $I = \{ 1, \ldots, n\}$ that have exactly two elements. Define $$s : P \to Q, s((i,j)) = \{i,j\} .$$ This is a bijection. Therefore for each function $f : Q \to \mathbb R$ $$\prod_{(i,j) \in P} f(s((i,j))) = \prod_{M \in Q} f(M) \tag{1}.$$

3. For a subset $M \subset I$ we define its diameter as $d(M) = \max( \lvert j - i \rvert \mid i, j \in M\}$. Clearly, if $M = \{i, j\} \in Q$, then $d(M) = \lvert j - i \rvert$. Hence for $\mathfrak p = (i,j) \in P$ we have $d(s(\mathfrak p)) = j - i$.

4. $\sigma$ induces a bijection $\sigma' : Q \to Q, \sigma'(M) =$ image of $M \in Q$ under $\sigma$, i.e. $\sigma'(M) = \{ \sigma(m) \mid m \in M \}$.

We now recall the following general commutativity law for real multiplication:

If $\varphi : F \to F$ is a bijection on a finite set $F$ and $x_\alpha \in \mathbb R$ for $\alpha \in F$, then $\prod_{\alpha \in F} x_\alpha = \prod_{\alpha \in F} x_{\varphi(\alpha)}$.

We apply it for $F = Q$, $\varphi = \sigma'$ and $x_M = d(M)$ and use $(1)$ to get

$$\prod_{(i,j) \in P}(j - i) = \prod_{\mathfrak p \in P} d(s(\mathfrak p)) = \prod_{M \in Q } d(M) = \prod_{M \in Q } d(\sigma'(M)) = \prod_{\mathfrak p \in P} d(\sigma'(s(\mathfrak p))) \\= \prod_{(i,j) \in P} d(\{\sigma(i), \sigma(j)\}) .$$

An inversion of $\sigma$ is a pair $(i,j) \in P$ such that $\sigma(i) > \sigma(j)$. Let $\text{inv}(\sigma) \subset P$ denote the set of all inversions of $\sigma$ and $\text{Inv}(\sigma)$ the number of elements of $\text{inv}(\sigma)$. Morever let $\epsilon(i,j) = 1$ for $(i,j) \in \text{inv}(\sigma)$ and $\epsilon(i,j) = 0$ for $(i,j) \in P \setminus \text{inv}(\sigma)$. We have $$\sum_{(i,j) \in P} \epsilon(i,j) = \text{Inv}(\sigma) ,$$ $$d(\{\sigma(i), \sigma(j)\}) = \lvert \sigma(j) - \sigma(i)\rvert = (-1)^{\epsilon(i,j)}(\sigma(j) - \sigma(i)) .$$ Therefore

$$\prod_{(i,j) \in P} d(\{\sigma(i), \sigma(j)\}) = \prod_{(i,j) \in P } (-1)^{\epsilon(i,j)}(\sigma(j) - \sigma(i)) \\ = \prod_{(i,j) \in P } (-1)^{\epsilon(i,j)} \prod_{(i,j) \in P } (\sigma(j) - \sigma(i)) = (-1)^{\sum_{(i,j) \in P } \epsilon(i,j)} \prod_{(i,j)\in P } (\sigma(j) - \sigma(i)) \\ = (-1)^{\text{Inv}(\sigma)} \prod_{(i,j) \in P} (\sigma(j) - \sigma(i)) .$$ This proves your claim.

Answer 2

You can rewrite your formula as $\prod_{i=1}^{n}\prod_{j=i+1}^{n}{1 \over {j-i}} \times \prod_{i=1}^{n}\prod_{j=i+1}^{n} {\sigma(j)-\sigma(i)}$.

Let $i< j$ and $\varepsilon(i,j) = -1$ if $\sigma(i) > \sigma(j)$, $1$ otherwise.

For each pair $i < j$, there exists a (unique) pair $i'< j'$ such that $|\sigma(i')-\sigma(j)| = |i'-j'|$ (this is basically because $\varphi : (i,j) \mapsto \varepsilon(i,j)(\min({\sigma(i),\sigma(j)}),\max({\sigma(i),\sigma(j)}))$ is a bijection (the reciprocal is $\varphi^{-1}(1,i,j) = (\sigma^{-1}(i), \sigma^{-1}(j)) $ and $\varphi^{-1}(-1,i,j) = (\sigma^{-1}(j), \sigma^{-1}(i)) $.

Hence, we have $\sigma(j)-\sigma(i) = \varepsilon(i,j)(j'-i')$ for some $i'<j'$.

We get
\begin{align*} \prod_{1\leq i < j \leq n} {\sigma(j)-\sigma(i)\over j-i}&=\prod_{i=1}^{n}\prod_{j=i+1}^{n}{1 \over {j-i}} \times \prod_{i=1}^{n}\prod_{j=i+1}^{n} {\sigma(j)-\sigma(i)} \\ &=\prod_{i=1}^{n}\prod_{j=i+1}^{n}{1 \over {j-i}} \times \prod_{i=1}^{n}\prod_{j=i+1}^{n} {\sigma(j)-\sigma(i)} \\ &=\prod_{i=1}^{n}\prod_{j=i+1}^{n}{1 \over {j-i}} \times \prod_{i=1}^{n}\prod_{j=i+1}^{n} \varepsilon(i,j)({j'-i'}) \\ &=\prod_{i=1}^{n}\prod_{j=i+1}^{n}{1 \over {j-i}} \times \prod_{i=1}^{n}\prod_{j=i+1}^{n} \varepsilon(i,j)\times \prod_{i=1}^{n} \prod_{j'=i+1}^{n}({j'-i}) \\ &= \prod_{i=1}^{n}\prod_{j=i+1}^{n} \varepsilon(i,j)\\ &= (-1)^{Inv(\sigma)} \end{align*}