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

  • $\begingroup$ Do you want your permutation to look like $\begin{pmatrix}5&2&4&3&6&1\\4&1&3&2&6&5\end{pmatrix}$, so that, for example, $5 \mapsto 4$ and $2 \mapsto 1$? $\endgroup$ – pjs36 Apr 6 '15 at 22:54
  • $\begingroup$ Yes exactly. Thanks $\endgroup$ – marquis Apr 6 '15 at 22:55

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.

  • $\begingroup$ 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. $\endgroup$ – marquis Apr 7 '15 at 14:50
  • $\begingroup$ 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? $\endgroup$ – marquis Apr 7 '15 at 14:57
  • $\begingroup$ 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. $\endgroup$ – pjs36 Apr 7 '15 at 15:45
  • $\begingroup$ 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. $\endgroup$ – pjs36 Apr 7 '15 at 15:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.