1
$\begingroup$

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$
  • $\begingroup$ The sign is not even, it is odd. I'm not sure what you mean to show in that link, the permutation above is not there. $\endgroup$ – Matt Samuel May 4 '15 at 16:58
  • $\begingroup$ @MattSamuel a link to WolframAlpha, it do not work, edited $\endgroup$ – gbox May 4 '15 at 16:59
1
$\begingroup$

You have not done anything wrong except in thinking the permutation is even. There are indeed 9 inversions as you have calculated.

$\endgroup$
  • $\begingroup$ keep getting messed up with this thing, is there an "easiest" way to calculate the sign of a permutation? $\endgroup$ – gbox May 4 '15 at 17:03
  • $\begingroup$ For a computer there is a faster way but it's hard for a human to do and it's really only faster in large cases. In this case you can note that the 3-cycle is even and the transposition is odd, so the product is odd. $\endgroup$ – Matt Samuel May 4 '15 at 17:04
1
$\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$
  • $\begingroup$ "the smallest length" is the number of permutations written as $(i,i+1)$? $\endgroup$ – gbox May 6 '15 at 13:26
  • $\begingroup$ Imagine placing the numbers $5,2,6,1,4,3$ in order on a line. You want to sort the array by interchanging pairs of elements at a time, but suppose that you are allowed to only swap adjacent elements each time. What is the minimum number of swaps needed? This is the number of inversions of a permutation. If $k$ such adjacent swaps are used to sort the elements in increasing order, then the given permutation can be expressed as a product of $k$ transpositions, where each transposition is of the form $(i,i+1)$ for some i. $\endgroup$ – Ashwin Ganesan May 7 '15 at 3:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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