Proof of Sign of a Product of Adjacent Transpositions

We prove the statement by induction on $N$. If $N=0$, then $\sigma$ is the identity permutation, so $\operatorname{sgn}(\sigma)=1=(-1)^0$.

Assume the statement holds for products of $N-1$ adjacent transpositions, and suppose

$$\sigma=\tau_{r_1}\circ\cdots\circ\tau_{r_N}.$$

Set

$$\rho=\tau_{r_1}\circ\cdots\circ\tau_{r_{N-1}},$$

so that $\sigma=\rho\circ\tau_{r_N}$. By the induction hypothesis,

$$\operatorname{sgn}(\rho)=(-1)^{N-1}.$$

It is therefore enough to prove that for every adjacent transposition $\tau_r$ one has

$$\operatorname{sgn}(\rho\circ\tau_r)=-\operatorname{sgn}(\rho).$$

Fix $r\in\{1,\dots,n-1\}$ and write

$$a=\rho(r),\qquad b=\rho(r+1).$$

Then $a\neq b$, and the permutation $\rho\circ\tau_r$ is obtained from $\rho$ by swapping the values $a$ and $b$ in positions $r$ and $r+1$.

We compare the inversion numbers of $\rho$ and $\rho\circ\tau_r$. Any inversion pair $(i,j)$ with $\{i,j\}\cap\{r,r+1\}=\varnothing$ has the same status for both permutations, because the values at all positions other than $r$ and $r+1$ are unchanged.

Now consider the pair $(r,r+1)$. In $\rho$, this pair is an inversion exactly when $a>b$. In $\rho\circ\tau_r$, this pair is an inversion exactly when $b>a$. Thus the inversion status of $(r,r+1)$ flips.

Next let $j<r$. We compare the two pairs $(j,r)$ and $(j,r+1)$. In $\rho$, these involve the values $\rho(j),a,b$, while in $\rho\circ\tau_r$ the roles of $a$ and $b$ are interchanged. There are three possibilities:

$$\rho(j)<\min\{a,b\},\qquad \rho(j)>\max\{a,b\},\qquad \min\{a,b\}<\rho(j)<\max\{a,b\}.$$

In the first two cases, either both pairs are inversions or neither is an inversion, both before and after the swap. In the third case, exactly one of the two pairs is an inversion before the swap and exactly one is an inversion after the swap. Hence the total number of inversions contributed by the two pairs $(j,r)$ and $(j,r+1)$ changes by an even integer, in fact by $0$.

The same argument applies for each $j>r+1$, now comparing the pairs $(r,j)$ and $(r+1,j)$. Again, their total contribution to the inversion count changes by an even integer, in fact by $0$.

Therefore every affected pair except $(r,r+1)$ changes the inversion count by an even amount, while the pair $(r,r+1)$ changes it by exactly $1$ modulo $2$. It follows that

$$N(\rho\circ\tau_r)\equiv N(\rho)+1 \pmod 2.$$

By the definition Sign of a Permutation of sign in terms of inversion parity, this gives

$$\operatorname{sgn}(\rho\circ\tau_r)=-\operatorname{sgn}(\rho).$$

Applying this with $r=r_N$, we obtain

$$\operatorname{sgn}(\sigma)=\operatorname{sgn}(\rho\circ\tau_{r_N})=-\operatorname{sgn}(\rho)=-(-1)^{N-1}=(-1)^N.$$

This completes the induction.