Prove $sgn(π) = sgn(π^{-1})$?

347 Views Asked by At

I'm pretty sure the inversion count of $π$ should be the opposite of the inversion count of $π^{-1}$. By this I mean if $π$ looks like this: $1 \to 1$, $2\to 2, \ldots, 10 \to 10$ and therefore the inversion count is $0$, $π^{-1}$ should have an inversion count of $10$. So each inversion count would have the same sign. Though I'm not really sure about this working for every case... I was also thinking about somehow finding $sgn(π^{-1})$ in the cases where $sgn(π) = 1$ and $sgn(π) = -1$, since those are the only two possibilities.

1

There are 1 best solutions below

0
On

The sign $\sigma(\pi)$ of a permutation $\pi$ is also given by $$\sigma(\pi) = \prod_{c\in\pi} (-1)^{|c|-1}$$ where the product is over the cycles of the disjoint cycle composition of $\pi.$

Now the inverse of $\pi$ has the same cycle lengths as the original with all cycles oriented the opposite direction from $\pi.$ Hence the sign is the same.

Remark. To do this using the inversion formula for the sign where $\sigma(\pi) = (-1)^{N(\pi)}$ where $N(\pi)$ is the number of inversions observe that an inversion in $\pi$ is a pair $(i,j)$ so that $\pi_i \gt \pi_j.$ In the inverse permutation we have $(\pi_j, \pi_i)$ mapped to $(j, i)$ so we get another inversion. Hence the inverse of $\pi$ has the same number of inversions and we are done. (A non-inversion has $(i, j)$ mapped to $(\pi_i, \pi_j)$ where $\pi_i \lt \pi_j.$ The same pair in the inverse is in order as well, so there is a bjection between the inversions of $\pi$ and its inverse here.)