Permutations and transpositions contradiction

[morrowcosom]

Homework Statement

(1 2 3 4 5)
(2 1 3 5 4) Write the bottom number as a product of transpositions

Homework Equations

The Attempt at a Solution

41352 41325 41235 42135 42315 24315 24351 21354
(2 4) (2 5) (2 3) (2 1) (3 1) (4 2) (5 1) (4 1)

This an even number of transpositions but I ended up with the number. I read somewhere that it is impossible to calculate these products with an even number of transpositions if there is an odd number of digits or vice-versa. What is up with this, or what am I doing wrong? Is there a method to finding these products, or do you just plug in random numbers after the n-1 transpositions (2, 4) (2, 5) (2, 3) (2, 1)?

 

[vela]

I don't follow what you did. Where did 41352 come from? Are you trying to apply the transpositions below each number to get the next? If you are, you don't seem to be doing it correctly. Could you explain more clearly what the problem is and your actual work?

Also, are you saying if you have an odd number of objects, there are no permutations of those objects that is the result of an even number of transpositions? That's obviously false because you can, say, start with 5 objects and apply two transpositions, right?

 

[JThompson]

Whether or not a permutation is even or odd depends on its sign; 1 if even, -1 if odd, with
\mbox{sgn }\pi=(-1)^{n-c(\pi)}
where c(\pi) is the number of cycles in the disjoint cycle representation of \pi.

It doesn't only depend on number of digits.

So in this problem,
<br /> \left(\begin{array}{ccccc}<br /> 1 &amp; 2 &amp; 3 &amp; 4 &amp; 5 \\<br /> 2 &amp; 1 &amp; 3 &amp; 5 &amp; 4<br /> \end{array}\right) = (1,2)(4,5)(3)<br />

So it's disjoint cycle rep. has 3 cycles. Therefore n-c(\pi) will be even, so the permutation's sign will be 1.

 

[morrowcosom]

Whether or not a permutation is even or odd depends on its sign; 1 if even, -1 if odd, with

where is the number of cycles in the disjoint cycle representation of .

It doesn't only depend on number of digits.

So in this problem,


So it's disjoint cycle rep. has 3 cycles. Therefore will be even, so the permutation's sign will be 1.

I worked a transposition problem
(1 2 3 4 5)
(2 5 4 3 1) find the the product of the bottom sequence in transpositions.

My first step was to determine whether the number of transpositions was to be even or odd.
I presumed n=5, since this was the total numbers in the sequence. I then found disjointed cycles of (1 2 5) (3 4). I finally subtracted the number of disjointed cycles from n, to arrive at the conclusion that there should be an odd number of transpositions, since 3 is an odd number. But, I was able to solve the problem with an even number of transpositions. Is this supposed to be impossible, or is it just wrong?

25431
1) 15432 (2 1)
2) 15423 (2 3)
3) 15243 (2 4)
4) 12543 (2 5)
5) 21543 (2 1)
6) 25143 (1 5)
7) 25413 (1 4)
8) 25431 (1 3)

 

[vela]

You're starting and ending at the same permutation, so of course you're going to find an even number of transpositions. You want to start with 12345 and find the number of transpositions needed to end at 25431.

 

[HallsofIvy]

\begin{pmatrix}1 &amp; 2 &amp; 3 &amp; 4 &amp; 5 \\ 2 &amp; 1 &amp; 3 &amp; 5 &amp; 4 \end{pmatrix}

I see immediately that 1 and 2 are swapped, that 3 remains in the same position and that 4 and 5 are swapped. This is the same as (12)(45).

" I read somewhere that it is impossible to calculate these products with an even number of transpositions if there is an odd number of digits"
No, that is not true. All transpositions on any number of digits are either "even" (require an even number of transpositions) or "odd" (require an odd number of transpositions)- and that, for any number of digits, exactly half of the transpositons are of each kind.

I suspect that you are incorrectly remembering that, while there may be many different ways of resolving a given permutation into a product of transpositions, they are either all odd or all even.

If one way of resolving a given permutation into a product of transpostions requires an odd number of transpositions, then there cannot be a way of resolving that same permutation into an even number of transpositions.

That has nothing to do with the number of digits.