3

Here is the question that I am working on:

Let $\sigma$ be the permutation of the numbers $1,2,...,n$ which reverses their order completely. That is,

$$\sigma=\begin{pmatrix} 1 & 2 & 3 &...&n \\ n & n-1 & n-2&...&1 \end{pmatrix}$$ Is $\sigma$ even or odd?

Here is what I noticed. In general, if I want to find whether a permutation is even or odd, I can write down the permutation in disjoint cycle form and then express that as a composition of transpositions. So, for example, $(123)$ would be even because $(123)$ = $(13)(12)$. The problem is that I'm not sure if this approach can apply to my original question since the permutation $\sigma$ depends on the number $n$. Any more insight on this question would be helpful.

EDIT As explained by the users below, I initially misinterpreted the question, so disregard my first comments in the chat below.

John W. Smith
  • 1,597
  • 1
    Doesn't look right. If you reverse 1, 2, 3 then you would get 3, 2, 1 and 2 has not moved. You have only switched 1 and 3 so the permutation is $(13)$ and hence odd. – badjohn Apr 10 '17 at 17:37
  • I actually have to disagree with you badjohn. A permutation is even if there are an even number of transpositions. $(123)$ clearly has $2$ transpositions, hence it's even. – John W. Smith Apr 10 '17 at 17:38
  • Unless you're referring to something else, then my apologies. – John W. Smith Apr 10 '17 at 17:39
  • Maybe I am misunderstanding your problem. By reversing the sequence, I took that to mean that 1, 2, 3 becomes 3, 2, 1. Is that right? If it is then 2 has not moved and only 1 and 3 have been interchanged. 1, 2, 3, 4, would become 4, 3, 2, 1, which seems like (14)(23) to me and hence even, – badjohn Apr 10 '17 at 17:42
  • Yeah, the wording of this question was confusing, but in your context then, it's correct. I had to re-read it a couple times to grasp what they question is asking. – John W. Smith Apr 10 '17 at 17:43
  • 1
    angryavian seems to have interpreted it my way. When n is even, you get $\frac{n}{2}$ 2-cycles. When n is odd, you get $\frac{n-1}{2}$ 2c-cycles. So, the answer will depend on the value n mod 4. In the 3 case, his formula gives just $(1 3)$. – badjohn Apr 10 '17 at 17:50
  • Yeah the wording of the question is what threw me off and yes angryavian did interpreted it your way. – John W. Smith Apr 10 '17 at 17:53

2 Answers2

6

It is hard to write the permutations neatly so I will use words instead.

Note that the first and last elements, $1$ and $n$, are just interchanged. Similarly, the second and second to last, $2$ and $n - 1$, are interchanged, $3$ and $n - 2$, etc.

If $n$ is even then every element is swapped and there are $\frac{n}{2}$ 2-cycles. So, if $\frac{n}{2}$ is even then the permutation is even and if $\frac{n}{2}$ is odd then the permutation is odd.

If $n$ is odd then the element in the middle, $\frac{n+1}{2}$ will be fixed. The remaining $n-1$ elements will be swapped by $\frac{n-1}{2}$ 2-cycles.

So summarising:

$n = 0 \mod 4$ No fixed element and the permutation is even.
$n = 1 \mod 4$ Middle element is fixed and the permutation is even.
$n = 2 \mod 4$ No fixed element and the permutation is odd.
$n = 3 \mod 4$ Middle element is fixed and the permutation is odd.

The Count
  • 3,620
badjohn
  • 8,204
  • 2
    Or in short: the permutation is even iff $\left\lfloor\frac{n}{2}\right\rfloor$ is even. – celtschk Apr 10 '17 at 19:19
  • 2
    Ah the floor function. – John W. Smith Apr 10 '17 at 19:32
  • @the-count Was your edit just to improve the formatting of my summary? Thanks, I am fairly new to this site and am not very fluent in MathJax yet. – badjohn Apr 10 '17 at 20:44
  • @badjohn yeah, if you click on the "edited x hours ago" above my avatar, you can see specifically what was changed by me. I just put slashes before the 'mod's since otherwise it reads them all as variables and looks really weird. and no problem at all, by the way. great answer, also. glad to have you around. – The Count Apr 10 '17 at 20:46
  • @TheCount I saw that I could compare it and the mod improvement was the only change that I noticed but I wanted to be sure. Thanks for the compliment. I am a rusty old guy trying to remember stuff I learned decades ago. – badjohn Apr 10 '17 at 20:48
  • 2
    @celtschk Yes, that's another way to look at it. I prefer the mod formulation, I find floor a bit computery, but each to his own. – badjohn Apr 10 '17 at 20:50
3

If $n$ is even, $\sigma=(1\; n)(2\; n-1) \cdots \left(\frac{n}{2} \; \frac{n}{2}+1\right)$.

If $n$ is odd, $\sigma = (1\; n)(2\; n-1) \cdots \left(\frac{n-1}{2}\; \frac{n+1}{2}\right)$.

Then count the number of transpositions. (Yes, it will depend on $n$.)

Nolan Faught
  • 332
angryavian
  • 89,882