TITLE: Equal parity of inversions and transpositions
QUESTION [5 upvotes]: 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}$?

REPLY [5 votes]: 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$.
{"set_name": "stack_exchange", "score": 5, "question_id": 562727}