Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
add comment

1 Answer

up vote 1 down vote accepted

I believe you are looking for this part of the wikipedia page.

To repeat proof 2 (I like that one -- it's nice and clean):

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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