# Parity and Inverse of Permutations (Odd and Even)

I want an explanation on knowing how to know whether a permutation is odd or even. For example, I have a few permutations of [9] that I need explained for parity, inverse, and number of inversions if possible.

1. 987654321
2. 135792468
3. 259148637

I need to know how to get there. (You can add more examples if needed, I just choose these since they are part of a text)

-
Which definition of the parity of a permutation are you using? – Chris Eagle Nov 1 '11 at 11:00

Parity and number of inversions go together: if the number of inversions is even, so is the parity, and if the number of inversions is odd, so is the parity. Thus, both of these boil down to counting inversions. Every time a larger number precedes a smaller number in a permutation, you have an inversion.

Let’s look at your third example, $259148637$. The $2$ precedes $5,9,1,4,8,6,3$, and $7$; the only one of these that is smaller than $2$ is $1$, so the pair $(2,1)$ is the only inversion involving the $2$. Go on to the $5$: it precedes $9,1,4,8,6,3$, and $7$; of these, $1,4$, and $3$ are smaller than $5$, so we get another three inversions: $(5,1),(5,4)$, and $(5,3)$. Continue in the same way: the $9$ is larger than all six of the numbers that follow it, so it contributes six inversions; the $1$ isn’t larger than any of the later numbers, so it contributes none. And so on: the $4$ contributes one, $(4,3)$; the $8$ contributes three, since it’s larger than all three of the later numbers; the $6$ contributes one, $(6,3)$; and that’s it, since the $3$ and $7$ contribute none.. The grand total is therefore $$1+3+6+0+1+3+1+0+0= 15\;,$$ if I’ve not miscounted. We conclude that the permutation $259148637$ has $15$ inversions, and since $15$ is odd, it’s an odd permutation.

Finding the inverse is another matter altogether. For this it’s easiest to write out the permutation in two-line notation, like this: $$\matrix{1&2&3&4&5&6&7&8&9\\2&5&9&1&4&8&6&3&7}\tag{1}$$ This is basically just a tabular display of the permutation as a function, one that takes each number in the top row to the number below it. If I call the permutation $\pi$, I can think of it as the function such that $\pi(1)=2,\pi(2)=5,\pi(3)=9,\dots,\pi(9)=7$. The inverse function just reverses all of these pairs: $\pi^{-1}(2)=1,\pi^{-1}(5)=2,\pi^{-1}(9)=3,\dots,\pi^{-1}(7)=9$. In tabular form this is just turning $(1)$ upside-down: $$\matrix{2&5&9&1&4&8&6&3&7\\1&2&3&4&5&6&7&8&9}\tag{2}$$

Now $(2)$ is a bit hard to use, because the top (or ‘input’) row is out of order. To fix this, just reorder the columns so that the top row is in numerical order: $$\matrix{1&2&3&4&5&6&7&8&9\\4&1&8&5&2&7&9&6&3}\tag{3}$$ To get $(3)$ from $(2)$ I just moved the columns as units: the fourth column of $(2)$ becomes the first column of $(3)$, the first column of $(2)$ becomes the second column of $(3)$, the eighth column of $(2)$ becomes the third column of $(3)$, and so on, all the way down to the third column of $(2)$, which $-$ since it has the $9$ in the top row $-$ becomes the last column of $(3)$.

Now just read off the bottom row of $(3)$: $418527963$ is the inverse of the original permutation. Try this procedure on the others, and see whether you have any questions.

-

One way is to write the permutation as a product of disjoint cycles (if you don't know how to do this, ask, and someone will answer). It's even if there are an even number of $n$-cycles with $n$ even; else, it's odd.

-