1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: How do I determine the sign of this permutation

  1. Mar 2, 2014 #1
    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. jcsd
  3. Mar 2, 2014 #2
    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?
  4. Mar 2, 2014 #3
    No I don't know what cycle notation is. However, I do know about transpositions (if that's what you're reffering to).
  5. Mar 3, 2014 #4


    User Avatar
    Science Advisor

    If n= 1, the permutation is
    [tex]\begin{pmatrix}1 & 2 & 3 \\ 3 & 2 & 1\end{pmatrix}[/tex]
    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
    [tex]\begin{pmatrix}1 & 2 & 3 & 4 & 5 \\ 5 & 4 & 1 & 2 & 3\end{pmatrix}[/tex]

    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
    [tex]\begin{pmatrix}1 & 2 & 3 & 4 & 5 & 6 & 7 \\ 7 & 6 & 5 & 1 & 2 & 3 & 4\end{pmatrix}[/tex]
    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.
  6. Mar 5, 2014 #5
    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?
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted