# 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

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.