We define an inversion of a permutation $\sigma\in S_k$ to be a pair $(\sigma(i), \sigma(j))$ such that $i<j$ but $\sigma(i)> \sigma(j)$. The sign of $\sigma$, written $\text{sgn}(\sigma)$, is defined by
\begin{align*}
\text{sgn}(\sigma) = (-1)^{\# \text{ of inversions in }\sigma} =
\begin{cases}
+1 &\text{ if the number of inversions in $\sigma$ is even}\\
-1 &\text{ if the number of inversions in $\sigma$ is odd}
\end{cases}.
\end{align*}
I want to prove that: $\text{sgn}(\sigma \tau)= (\text{sgn }\sigma)(\text{sgn }\tau)$ for any two permutations $\sigma$ and $\tau$, using the above definition.
I tired many times but i failed. If I got some equation relating the number of inversions of $\sigma$, $\tau$ and the composite $\sigma\tau$, I had done. I need your help please.
Best Answer
Yes, one can prove it directly by counting inversions. Starting with $i<j$, apply $\tau$ and get the pair $(i_1,j_1)$ defined by $$i_1=\tau(i)\qquad j_1=\tau(j).$$ Then apply $\sigma$ and get the pair $(i_2,j_2)$ defined by $$i_2=\sigma(i_1)=\sigma\tau(i)\qquad j_2=\sigma(j_1)=\sigma\tau(j).$$ In summary $$(i,j)\to^{\tau}(i_1,j_1)\to^\sigma(i_2,j_2) $$ After applying each permutation, an inversion either occurs or not. Let $x$ count the number of pairs $i<j$ such that $i_1>j_1$ and $i_2<j_2$. Let $y$ count the number of pairs $i<j$ such that $i_1>j_1$ and $i_2>j_2$. Let $z$ count the number of pairs $i<j$ such that $i_1<j_1$ and $i_2>j_2$.
The permutations of interest then have the following numbers of inversions: $$N(\tau)=x+y$$ $$N(\sigma)=x+z$$ $$N(\sigma\tau)=y+z$$ It follows that $$sgn(\sigma)sgn(\tau)=(-1)^{N(\sigma)}(-1)^{N(\tau)}=(-1)^{x+z}(-1)^{x+y}$$
$$=(-1)^{2x+y+z}=(-1)^{y+z}=(-1)^{N(\sigma\tau)}=sgn(\sigma\tau)$$