# How do i prove that the signature of a permutation $\sigma$ is equal to the parity of $\{(i,j):i<j ,\sigma(j)<\sigma(i)\}$?

Let $\sigma$ be a permutation of degree $n$ ($n>1$).

Then, there exists a finite sequence of transpositions $\tau_1,...,\tau_r$ such that $\sigma=\tau_1\cdots \tau_r$ and the parity of $r$ is unique for a given permutation $\sigma$.

So, I defined this parity as a signature of a permutation.

However, wikipedia defined the signature of $\sigma$ as the parity of $|\{(i,j)|i<j , \sigma(i)>\sigma(j)\}|$.

How do i prove that the parities of these two numbers are the same?

-

Let $P(x_1,\dots,x_n) = \prod\limits_{i<j} (x_i-x_j)$ (so for $n=3$ we have $P(x_1,x_2,x_3)=(x_1-x_2)(x_1-x_3)(x_2-x_3)$). Then the sign (or signature or parity) of $\sigma$ is nothing more than $$\mbox{sgn}(\sigma) = \frac{P(x_{\sigma(1)},\dots,x_{\sigma(n)})}{P(x_1,\dots,x_n)}$$ Why? Since the numerator and denominator have the same factors except for signs. The number of "$-$" contributed by the numerator is exactly the size of $\{(i,j)\;|\; i<j \mbox{ and } \sigma(i)>\sigma(j) \}$ (the number of factors flipped around). Also, notice that since this fraction is $\pm 1$ (it is a constant) so further shuffling of its inputs does not effect its value.
Now we can see that $$\mbox{sgn}(\sigma\tau) = \frac{P(x_{\sigma\tau(1)},\dots,x_{\sigma\tau(n)})}{P(x_1,\dots,x_n)} = \frac{P(x_{\sigma(1)},\dots,x_{\sigma(n)})}{P(x_1,\dots,x_n)} \frac{P(x_{\sigma\tau(1)},\dots,x_{\sigma\tau(n)})}{P(x_{\sigma(1)},\dots,x_{\sigma(n)}} = \mbox{sgn}(\sigma)\mbox{sgn}(\tau)$$
Finally notice that a transposition has sign $-1$. Thus each transposition flips the sign (parity/signature). So the definitions match.