1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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...

$\endgroup$
2
$\begingroup$

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.)

Post-comment addition:

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}

$\endgroup$
  • $\begingroup$ Maybe there is more simple reasoning without matrices? $\endgroup$ – A.Ward.2016 May 1 '16 at 13:36
  • $\begingroup$ Perhaps so...but this is the reasoning that I know, so it's what I wrote. :) $\endgroup$ – John Hughes May 1 '16 at 13:37
  • $\begingroup$ Where did you use that sign of permutations is number of inversions? $\endgroup$ – A.Ward.2016 May 1 '16 at 13:55
  • $\begingroup$ See post-comment additions. I used the sign-of-perms=number-of-inversions in the (hidden) proof that sign of a perm corresponds to det of the associated matrix. $\endgroup$ – John Hughes May 1 '16 at 14:06

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.