I am trying to understand the definition of the sign of a permutation $\pi$.
My textbook only mentions that $\operatorname{sgn}(\pi) = (-1)^k$ , where $k$ is the number of transpositions .
But I have also found online that $\operatorname{sgn}(\pi) = (-1)^{\operatorname{inv}(\pi)}$, where $\operatorname{inv}(\pi)$ is the number of inversions on a permutation.
Does this mean $ k = \operatorname{inv} (\pi)$ in general ?
I am trying to show if $\pi$ is a product of $k$ transpositions , then $k \equiv \operatorname{inv}(\pi)\pmod2$
In general, the $\operatorname{sgn}(\pi) = 1$ if $\pi$ is a product of even number of transpositions.
And $\operatorname{sgn}(\pi) = -1$ if $\pi$ is a product of odd number of transpositions.
So I was thinking that if $k$ is even, then $\operatorname{inv}(\pi)$ is even and so $2\mid\operatorname{inv}(\pi) – k $ and similarly if $k $ is odd, then $\operatorname{inv}(\pi)$ is odd, so $2\mid\operatorname{inv}(\pi) – k$ . So $k \equiv \operatorname{inv}(\pi) \pmod 2$)
Can someone please verify this? Any better approach or feedback would help! Would I have to prove this part of the definition?
Thank you !
Best Answer
To see why they are both the same, first prove the following lemma:
Lemma 1 $$\mbox{sgn}(\sigma) =\prod_{1 \leq i < j \leq n} \frac{\sigma(j)-\sigma(i)}{ j-i}$$
To prove it, first note the the RHS must have absolute value 1, as every pair $(k,l)$ appears once at the bottom and once at the top. Therefore the RHS is $\pm 1$, and all you need to do is track the sign. Finally for the RHS you get a minus for each inversion.
Next, use this to get:
Lemma 2 $$\mbox{sgn}(\sigma \circ \tau) =\mbox{sgn}(\sigma)\mbox{sgn}( \tau)$$
Idea of proof: By Lemma 1: $$ \mbox{sgn}(\sigma \circ \tau)=\prod_{1 \leq i < j \leq n} \frac{\sigma \circ \tau (j)-\sigma \circ \tau(i)}{ j-i} \\ =\prod_{1 \leq i < j \leq n} \frac{\sigma \circ \tau (j)-\sigma \circ \tau(i)}{ \tau (j)- \tau(i)} \cdot \prod_{1 \leq i < j \leq n} \frac{ \tau (j)- \tau(i)}{ j-i}=\mbox{sgn}(\sigma)\mbox{sgn}( \tau) $$ by a similar computation to Lemma 1.
Lemma 3 If $\tau$ is a transposition $(i,j)$ then $$\mbox{sgn}(\tau)=-1$$
Proof Just count the inversions.
Combining Lemma 3 and Lemma 2, you finally get:
Theorem Let $\sigma=\tau_1 \cdot ...\cdot \tau_k$ where $\tau_j$ are all transposition. Then $$\mbox{sgn}(\sigma)=(-1)^k$$