How do I determine the sign of this permutation

In summary: P)In summary, a permutation is a rearrangement of a set of objects. If there are an odd number of inversions, it is called an odd permutation. If there are an even number of inversions, it is called an even permutation. If there are no inversions, it is called a simple permutation. If there is only a single transposition, it is called a transposition.
  • #1
KodRoute
5
0

Homework Statement


Find the sign of the permutation --> Picture here: http://tinypic.com/view.php?pic=2q8rkso&s=5
No other given data.

Homework 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.

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.
 
Physics news on Phys.org
  • #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?
 
  • #3
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
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.
 
  • #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?
 

1. How do I determine the sign of a permutation with an even number of inversions?

To determine the sign of a permutation with an even number of inversions, you can use the following formula: (-1)^n, where n is the number of inversions. This means that if n is an even number, the sign of the permutation will be positive (+1).

2. How do I determine the sign of a permutation with an odd number of inversions?

If the number of inversions in a permutation is odd, the sign of the permutation will be negative (-1). You can use the same formula as mentioned above: (-1)^n, where n is the number of inversions.

3. Can the sign of a permutation be zero?

No, the sign of a permutation cannot be zero. It will always be either positive (+1) or negative (-1), depending on the number of inversions in the permutation.

4. How do I account for repeated elements in a permutation when determining the sign?

If a permutation has repeated elements, the sign remains the same. You only need to consider the number of inversions in the permutation, regardless of any repeated elements.

5. Is there a shortcut or easier way to determine the sign of a permutation?

Yes, you can use the Lehmer code to determine the sign of a permutation. This method involves counting the number of inversions in the permutation and can be more efficient for longer permutations.

Similar threads

  • Engineering and Comp Sci Homework Help
Replies
7
Views
624
  • Linear and Abstract Algebra
Replies
2
Views
917
  • Introductory Physics Homework Help
2
Replies
41
Views
4K
Replies
4
Views
1K
  • Linear and Abstract Algebra
Replies
3
Views
1K
  • Precalculus Mathematics Homework Help
Replies
1
Views
3K
  • Advanced Physics Homework Help
Replies
3
Views
1K
  • Precalculus Mathematics Homework Help
Replies
3
Views
2K
  • Precalculus Mathematics Homework Help
Replies
18
Views
2K
  • Precalculus Mathematics Homework Help
Replies
8
Views
2K
Back
Top