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 $P=\{(i, j)|1\leq i<j\leq n\}. $For $\sigma\in S_n$, define $\operatorname{sgn}\colon S_{n}\rightarrow \{\pm 1\}$ by $$ \operatorname{sgn}(\sigma)=\prod_{(i, j)\in P}\operatorname{sgn}(\sigma(j)-\sigma(i)).$$ How to prove the following?

  1. $\displaystyle{\operatorname{sgn}(\sigma)=\prod_{1\leq i<j\leq n}\left(\frac{\sigma(j)-\sigma(i)}{j-i}\right)}$.

  2. Consider the polynomial $\displaystyle{p(x_{1},...,x_{n})=\prod_{1\leq i<j\leq n}(x_{j}-x_{i})}$.

    For $\sigma\in S_n$ prove that $\displaystyle{\operatorname{sgn}(\sigma)=\frac{p(x_{\sigma(1)},\ldots,x_{\sigma(n)}) }{p(x_{1},\ldots,x_{n})}}$.

  3. Let $N_{\sigma}$ be the number of orbits of $\sigma$ acting on $\{1,\ldots,n\}$. Show $\operatorname{sgn}(\sigma)=(-1)^{n-N_{\sigma}}$.

share|improve this question
1  
Surely you know how to solve some of these! Please show what you tried and where you are stuck. –  Did May 24 '12 at 21:00
    
You have a conflicting notation: you use sgn for two different functions. –  M Turgeon May 24 '12 at 21:05
4  
Maybe you should first write them informally? –  Phira May 24 '12 at 21:52
1  
@Andres If $x\in\mathbb{R}$ is non zero, we have $sgn(x)=\frac{|x|}{x}$ (by definition). If this doesn't help, I don't know what will. –  M Turgeon May 25 '12 at 1:45
4  
Then write what you have for particular cases, but write something. Yourself. Mathematics is not a spectator sport. –  Did May 25 '12 at 21:15
show 7 more comments

1 Answer

up vote 1 down vote accepted

Pay attention to the fact that in the formula in $\,(1)\,$ , for any $\,1\leq i<j\leq n\,$, the denominator $\,j-i\,$ is always positive , so what "decides" the sign there is merely the numerator $\,\sigma(j)-\sigma(i)\,$ , thus: both "definitions" you wrote down of sgn are exactly the same.

Now, let us write down the given information: $$\frac{p\left(x_{\sigma(1)},...,x_{\sigma(n)}\right)}{p\left(x_1,...,x_n\right)}=\frac{\prod_{1\leq i<j\leq n}\left(x_{\sigma(j)}-x_{\sigma(i)}\right)}{\prod_{1\leq i<j\leq n}\left(x_j-x_i\right)}=\prod_{1\leq i<j\leq n}\frac{x_{\sigma(j)}-x_{\sigma(i)}}{x_j-x_i}\,\,(**)$$and as before: the factors in the denominator are the very same factors in the numerator up to sign, and there's a change of sign, say for some pairs $\,(r,s)\,,\,(i,j)\in P\,$: $$\frac{x_{\sigma(j)}-x_{\sigma(i)}}{x_r-x_s}=\frac{-(x_r-x_s)}{x_r-x_s}=-1$$iff exactly the same change exists in $$\frac{\sigma(j)-\sigma(i)}{r-s}=\frac{-(r-s)}{r-s}=-1$$ so from here clearly we have that $\,\,(**)=sgn(\sigma)\,$

Finally, we can try to attack $\,(3)\,$ with the following:

Lemma: For every permutation $\,\sigma\in S_n\,\,,\,n-N_\sigma=T_\sigma $ , with $\,T_\sigma:=\,$number of transpositions $\,(i \,j)\,,\,1\leq i\neq j\leq n\,$ , needed to express $\,\sigma\,$ as a product of transpositions.

Proof: It is enough to prove for cycles, as any permutation can be written as a product of (disjoint) cycles: let $\,\sigma = (i_1\,i_2\,,...,i_r)\,$ be an $\,r-\,$cycle , then $$\sigma=(i_1\,i_r)(i_1\,i_{r-1})\cdot...\cdot (i_1\,i_3)(i_1\,i_2)$$and we can see that the number of transpositions in the right hand side is $$\,r-1=n-N_\sigma\Longleftrightarrow N_\sigma=n-r+1$$ which is clearly the number of orbits of $\,\sigma\,$ , as it fixes $\,n-r\,$ points in $\,\{1,2,...,n\}\,$ Q.E.D.

Well, then we already are there since any transposition has sign $\,-1\,$, obviously, so that $$(-1)^{n-N_\sigma}=(-1)^{r-1}$$and let us not forget that the number of orbits of $\,\sigma\,$ is just another name for "the number of different (disjoint) cycles in the decomposition of $\,\sigma\,$"

share|improve this answer
    
@Andres Did you see my answer above? –  DonAntonio Jun 10 '12 at 3:46
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.