Sign of a permutation when two elements are removed

Question

Suppose I have a totally ordered set $\{a_{1},\bar{a}_{1},a_{2},\bar{a}_{2},...,a_{n},\bar{a}_{n}\}$ and a permutation $\pi$ which orders this set from biggest to smallest. This permutation has sign $\operatorname{sign}\pi$.

Take the element $a_{1}$ and some barred element, say, $\bar{a}_{j}$, with some $j=1,2,...,n$. Remove both these elements from our original set, so to obtain $\{a_{2},\bar{a}_{1},...,\hat{\bar{a}}_{j},...,a_{n}\}$ where the hat on $\bar{a}_{j}$ means to omit this element. Let $\pi'$ be a new permutation which orders this new set, as before, from biggest to smallest, but now with these two absent elements.

I am having a really hard time trying to obtain the $\operatorname{sign}\pi'$ with respect to $\operatorname{sign}\pi$. I need (and would expect) that $\operatorname{sign}\pi'$ would depend on $1$ and $j$ alone, which are the indices of the omitted elements. However, I don't get this dependence. Because the $j$-th element occupies the $2j$ position originally on $\{a_{1},\bar{a}_{1},a_{2},\bar{a}_{2},...,a_{n},\bar{a}_{n}\}$, it seems that this index contributes with a $(-1)^{2j} = 1$, that is, it does not contribute at all in the sign of $\pi'$. Should'nt I get something different?

Answer 1

Since the sign of a permutation is $-1$ raised to the power of the number of inversions, to compare the sign of $\pi$ and $\pi'$, we just need to count the number of inversions we've lost. This is the sum of

• $n_1$: the number of elements among $\{\bar a_1, a_2, \bar a_2, \dots, a_n, \bar a_n\}$ that are less than $a_1$,
• $n_2$: the number of elements among $\{\bar a_1, a_2, \bar a_2, \dots, a_{j-1}, \bar a_{j-1}\}$ that are greater than $a_j$, and
• $n_3$: the number of elements among $\{\bar a_j, a_{j+1}, \bar a_{j+1}, \dots, a_n, \bar a_n\}$ that are less than $a_j$.

In other words, $\operatorname{sign}(\pi') = (-1)^{n_1 + n_2 + n_3} \operatorname{sign}(\pi)$.