2
$\begingroup$

Let $\sigma $ be a permutation of the set $\{1,\ldots,n\}$ that is written as the product of $k$ transpositions. Let $\rm{inv}(\sigma)$ be the number of inversions of $\sigma$ - that is the number of pairs $(x,y)$ such that $x < y$ but $\sigma(x) > \sigma(y).$

How can I show that $\rm{sgn}(\sigma) \equiv k \pmod{2}$?

$\endgroup$
3
$\begingroup$

Let $\pi=\langle p_1,p_2,\ldots,p_n\rangle$ be a permutation of $[n]=\{1,\ldots,n\}$. If $\pi$ has no inversions, it’s the identity permutation, which is even, so assume that $\pi$ has at least one inversion. Suppose that $1\le j<k\le n$, and $p_j>p_k$. Let $\rho=(p_j,p_k)\pi$ (where I apply the transposition first and then $\pi$); if $\rho=\langle r_1,\ldots,r_n\rangle$, then $r_j=p_k$, $r_k=p_j$, and $r_i=p_i$ if $i\in[n]\setminus\{j,k\}$. This swap obviously gets rid of the $\langle j,k\rangle$ inversion.

The only other inversions affected by this swap are those that involve position $j$ or $k$ and a position between $j$ and $k$. Suppose that $j<i<k$ and $\langle j,i\rangle$ is an inversion in $\pi$, i.e., $p_j>p_i$. Either $p_k>p_i$, in which case $\langle j,i\rangle$ is still an inversion in $\rho$, or $p_i>p_k$, in which case the swap gets rid of a $\langle j,i\rangle$ and an $\langle i,k\rangle$ inversion. Similarly, if the swap gets rid of an $\langle i,k\rangle$ inversion (instead of replacing it with a new one), it also gets rid of a $\langle j,i\rangle$ inversion. In all cases the number of inversions other than $\langle j,k\rangle$ that are affected by the swap is even. Thus, the total number of inversions affected by the swap is odd. Note also that the number of inversions is reduced by at least one.

Can you see how to finish it from here? I’ve left the conclusion of the argument in the spoiler-protected block below.

Start with any non-identity permutation $\pi$. Repeatedly multiply by transpositions to remove inversions until no inversions remain. Say you multiplied by $m$ transpositions. Then $\pi$ has the same parity as $m$, and since each multiplication by a transposition removed an odd number of inversions, the number of inversions also has the same parity as $m$.

$\endgroup$
  • $\begingroup$ Hm.. In the first sentence of the second paragraph - given the permutation $\pi = (3 4 5 1 2)$ we have that $(2,4)$ and $(2,5)$ are its inversions. However, if we swap 2 and 4, $(2,5)$ is not an inversion anymore. Yet your argument says we need only consider inversions involving $p_j,p_k$ and an element in between. Am I missing something here? $\endgroup$ – Jernej Nov 15 '13 at 20:18
  • $\begingroup$ @Jernej: $5$ is between $2$ and $4$. That’s exactly one of the cases that I talked about in the answer. $\endgroup$ – Brian M. Scott Nov 15 '13 at 20:19
  • $\begingroup$ Hm! Maybe my notation is confusing I meant the permutation $\begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 3 & 4 & 5 & 1 & 2\end{pmatrix}$ $\endgroup$ – Jernej Nov 15 '13 at 20:22
  • $\begingroup$ @Jernej: So did I. $\endgroup$ – Brian M. Scott Nov 15 '13 at 20:24
  • $\begingroup$ Hm.. Maybe I don't understand the proof then. If I apply the argument of the proof $j = 2, k = 4$ and the positions in between are $2,3,4.$ This should imply that the transposition of $(1,4)$ only possible inversions affect these positions, but affects only inversions at these positions, yet $(2,5)$ was a inversion before and after applying the transposition its not anymore $\endgroup$ – Jernej Nov 15 '13 at 20:30

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.