2

For the permutation $\begin{pmatrix}5&2&4&3&6&1\\4&1&3&2&6&5\end{pmatrix}$, determine if it is even based on its inversions.

So here's my trouble; I've worked out the inversions for the top row as $(5,2),(5,4),(5,3),(5,1),(2,1),(4,3),(4,1),(6,1)$ for a total of $8$ and for the bottom row $(4,1),(4,2),(4,3),(3,2),(6,5)$ for a total of $5$.

This sums to 13 inversions for the permutation making it odd? My understanding is that I look at a number and see how many smaller numbers are to the right, each pair forms an inversion ie. $(5,2)$ from the top row.

Can anyone shed some light on this? Is there some double-counting rule I'm missing

pjs36
  • 17,979
marquis
  • 21

1 Answers1

1

Let's call your permutation $p$, so that $p = \begin{pmatrix}5&2&4&3&6&1\\4&1&3&2&6&5\end{pmatrix}$.

Using this definition of an inversion, I'm not quite sure why you've done the work you have done. We need to find pairs $(i, j)$, such that $i > j$ yet $p(i) < p(j)$.

I personally think it helps to write your permutation in the standard way, with the top row increasing:

$$p = \begin{pmatrix}1&2&3&4&5&6\\5&1&2&3&4&6\end{pmatrix}.$$

Now finding inversions amounts to counting pairs $(p(i), p(j))$ in the bottom row, where $p(i)$ appears to the left of $p(j)$, yet $p(i) > p(j)$. In that case, I'm only seeing $4$ inversions, not $13$.

I don't think you're missing any double counting rules or anything, but rather that only when the top row is $(1\ 2\ \ldots\ n)$ can we find inversions by looking for decreasing pairs in the bottom row.

pjs36
  • 17,979
  • Thanks for the help. I'm confident that I know what you're saying but I still get the wrong answers. My TA for the module told us to take the inversions of both the top and bottom row and add them together but I haven't seen or heard that anywhere else online. – marquis Apr 07 '15 at 14:50
  • I did the next question where the permutation was p=(5 2 6 3 4 1)(4 1 3 2 6 5) and rewrote that in order as (1 2 3 4 5 6)(5 1 2 6 4 3) and listed the inversions as (5,1),(5,2),(5,4)(5,3),(6,4),(6,3) - 6 total so I concluded as 6 is even then the permutation must be too. However I checked Wolfram and that said it was odd. Do you know where I'm going wrong? – marquis Apr 07 '15 at 14:57
  • I've never seen inversions tied to even/oddness of a permutation. Maybe there is a relationship, but nothing is coming to mind. In the example you wrote, we can write $p$ in cycle notation as $(1 5 4 3 2)$ and then decompose as $(1 2)(1 3)(1 4)(1 5)$, which is even. For the one in your comment, $(1 5 4 6 3 2)$ can be decomposed as $(1 2)(1 3)(1 6)(1 4)(1 5)$, and hence is even. – pjs36 Apr 07 '15 at 15:45
  • Put another way, parity (even/odd) is about how many $2$-cycles (involutions) are needed to write your permutation as a product of $2$-cycles. Even though inversions to concern two "objects" in a permutation, I'm not sure there's a connection to involutions. – pjs36 Apr 07 '15 at 15:48