# How do I determine the sign of this permutation

1. Mar 2, 2014

### KodRoute

1. The problem statement, all variables and given/known data
Find the sign of the permutation --> Picture here: http://tinypic.com/view.php?pic=2q8rkso&s=5
No other given data.

2. Relevant equations
ε(σ) = (-1)^m(σ).
If i < j and σ(i) > σ(j) then there's an inversion.
Where ε(σ) denotes the sign of the permutation and m(σ) the number of inversions.

3. The attempt at a solution
What I tried to do is this:
σ(1) = 2n + 1
σ(2) = 2n
2n + 1 > 2n -- yes
Now what? Should I go on doing the same?
I mean, if the permutation belongs directly to S2, S3 or any other number you can count the inversions but how do I count the inversions now?

Thank you.

2. Mar 2, 2014

### micromass

Staff Emeritus
Do you know about the "disjoint cycle notation"? This makes it a lot easier to "see" what the answer is. In this case, can you write this in cycle notation?

3. Mar 2, 2014

### KodRoute

No I don't know what cycle notation is. However, I do know about transpositions (if that's what you're reffering to).
Thx.

4. Mar 3, 2014

### HallsofIvy

Staff Emeritus
If n= 1, the permutation is
$$\begin{pmatrix}1 & 2 & 3 \\ 3 & 2 & 1\end{pmatrix}$$
1 is mapped to 3 which is mapped to 1 while 2 remains unchanged. The "cycle" is (13). There is one transposition so this is an odd permutation.
If n= 2, the permutation is
$$\begin{pmatrix}1 & 2 & 3 & 4 & 5 \\ 5 & 4 & 1 & 2 & 3\end{pmatrix}$$

Notice that 1 is mapped into 5 which is mapped into 3 which is mapped back to 1 again. That is the "cycle" (153). 2 is mapped into 4 which is mapped back into 4 so another cycle is (24). Since those are disjoint, it doesn't matter which we do first- we can write this permutation as (153)(24) or as (24)(153).

In any case, (153) has two "transpositions" (swap 1 and 5 and then 1 and 3) and (24) has one "transposition" (swap 2 and 4, of course). In general, a cycle of n numbers has n-1 transpositions. So the original transposition has a total of 2+ 1= 3 transpositions, an odd number.

If n= 3, this is
$$\begin{pmatrix}1 & 2 & 3 & 4 & 5 & 6 & 7 \\ 7 & 6 & 5 & 1 & 2 & 3 & 4\end{pmatrix}$$
1 maps into 7 which maps into 4 which maps into 1 again so one cycle is (174). 2 maps into 6 which maps into 3 which maps into 5 which maps into 2 so another cycle is (2635). The first cycle has two transpositions and the second has 3 so there are 2+ 3= 5 transpositions. This is also an odd permutation.

Looks to me like this is always an odd permutation but that has yet to be proved. Perhaps you could prove that this is always a product of two cycles, one with two transpositions, the other with an odd number of transpositions.
If the answer, as is implied by the question, is independent of n, then this is an odd permutation.

5. Mar 5, 2014

### KodRoute

Thank you for posting Hallsoflvy, someone explained this problem to me in this way:

"So an inversion is (i,j) with i<j and p(i)>p(j) and the sign is (-1)ⁿ with n the count of inversions. You have that permutation in tableau form, so you can read off what p(i) is for each i.

If i<j with i,j in 1..n, then p(i)>p(j), inversion, and there are C(n,2) of those.

If i<j with i,j in n+1..2n+1, then p(i)<p(j), and it's not an inversion.

If i<j with i in 1..n, and j in n+1..2n+1, then p(i)>p(j), inversion, and there are n² of those.

C(n,2) + n² = n(n-1)/2 + n² = n(3n-1)/2"

But I still don't understand it and neither the explanation mentioned by this person. I've had the help of other people as well but I still don't get it. It's easy to count the inversions in permutations of the form {2,4,5,1,3} etc. but this particular problem just seems so complicated to me (or maybe who knows, probably I have a learning disability of permutations?