# Sign of composition of transpositions

Let $\sigma \in S_n$.

Definition: Suppose that $\text{sign}\sigma=(-1)^N$, where $N$ - number of inversions in permutation $\sigma$.

Suppose that $\tau_1$ and $\tau_2$ transpositions. How to prove that $\text {sign}(\tau_1\circ \tau_2)=\text {sign}\tau_1\cdot \text {sign}\tau_2?$

I tried to prove it but any results.

Can anyone show the rigorous proof please.

During a long drive this evening I realized my other answer, involving determinants, was just a long trip around Robin Hood's Barn. Here's the short proof.

Suppose that $\tau_1$ is a composition of $k$ transpositions $X_1, \ldots, X_k$, $$\tau_1 = X_k X_{k-1} \cdots X_2 X_1,$$ and that $\tau_2$ is a composition of $p$ transpositions $Y_1, \ldots, Y_p$. Then $\text{sign}(\tau_1) = (-1)^k$, and similarly $\text{sign}(\tau_2) = (-1)^p$.

To compute the sign of $\tau_2 \circ \tau_1$, observe that $\tau_2 \circ \tau_1$ can be written as $$\tau_2 \circ \tau_1 = Y_p Y_{p-1} \cdots Y_2 Y_1 X_k X_{k-1} \cdots X_2 X_1,$$ so that its sign is $(-1)^{p+k}$. And since $$(-1)^{p+k} = (-1)^p (-1)^k$$ we get the desired conclusion.

There's an important question here: why can a single permutation not be written as a product of $k$ permutations and of $b$ permutations, where exactly one of $b$ and $k$ is odd? I.e., why is the sign well-defined in the first place? I'm assuming that question has already been covered in your text...

Every permutation can be described by a matrix with exactly one "1" in each row and column. ($m_{ij} = 1$ if the permutation sends the $j$th item to the $i$th one).

The sign of the permutation is then the determinant of this associated matrix, and the composition of permutations corresponds to product of matrices. Hence, since the determinant of the product is the product of the determinants, the result is clear.

(Why is the sign of the permutation the det of the associated matrix? Because for a transposition (in which $m_{kk} = 1$ for $k \ne i, j$, and $m_{ij} = m_{ji} = 1$), the determinant is $-1$, and then the product-of-determinants rule takes care of things.)

To spell things out: suppose that $M_\tau$ is the matrix associated to the permutation $\tau$. Then \begin{align} \text{sign}(\tau_1 \circ \tau_1) & = \det(M_{\tau_1 \circ \tau_1}) & \text{bcs sign corresponds to det} \\ & = \det(M_{\tau_2} M_{\tau_1}) & \text{matrix of composed perms is product of matrices}\\ & = \det(M_{\tau_2}) \det( M_{\tau_1}) & \text{det-of-a-product rule}\\ &= \text{sign}(\tau_1)\text{sign}(\tau_2) & \text{bcs sign corresponds to det} \end{align}