Let the be the following permutation: $(1 5 4)(3 6)\in S_6$
How do I count the number of inversions to calculate the sign of the permutation?
$(1 5 4)(3 6)=(1 5)(1 4),(3 6)=3$ so it has an odd sign
\begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 5 & 2 & 6 & 1 & 4 & 3 \end{pmatrix}
before $5$ there are $0$ elements.
before $2$ there are $1$ elements (5).
before $6$ there are $0$ elements.
before $1$ there are $3$ elements (5,2,6).
before $4$ there are $2$ elements (5,6).
before $3$ there are $3$ elements (5,6,4).
Therefore there are $9$ inversions so it is $(-1)^9=-1$
Are both of the ways are ok?
$\endgroup$ 22 Answers
$\begingroup$If the goal is to calculate the sign of a permutation in $S_n$, then there is an easier method than calculating the number of inversions. The number of inversions in a permutation is the smallest length of an expression for the permutation in terms of transpositions of the form $(i,i+1)$. The permutation is odd if and only if this length is odd. However, it is easier to determine the smallest length of an expression for the permutation in terms of arbitrary transpositions. The permutation is odd if and only if this length is odd. A permutation can be expressed as a product of transpositions in many different ways, but the lengths of all of these products will have the same parity - always even or always odd, and this determines the sign of the permutation.
A $k$-cycle $(1,2,\ldots,k)$ can be expressed as a product of exactly $k-1$ transpositions. Thus, if the permutation consists of $r$ cycles, of lengths $k_1,\ldots,k_r$, respectively, then the permutation is odd iff $(k_1-1)+\cdots+(k_r-1)$ is odd. In the above example where the permutation was $(154)(36)$, the permutation can be expressed as a product of $(3-1)+(2-1)=2+1=3$ transpositions, hence is odd.
$\endgroup$ 2 $\begingroup$You have not done anything wrong except in thinking the permutation is even. There are indeed 9 inversions as you have calculated.
$\endgroup$ 2
