0
$\begingroup$

For $n\geqslant 2$, if $\alpha\in S_n$ and $\alpha=\tau_1...\tau_k=\lambda_1...\lambda_m$ are factorizations of $\alpha$ as the product of transpositions in $S_n$, so $m$ and $k$ have the same parity, this means,$(-1)^k=(-1)^m$.

The sign of $\alpha$ is denoted $sgn(\alpha)=(-1)^k$.

Following some notes I did not understand the following proof:

If $\alpha$ is a transposition:

$\prod_{j>i}(\alpha(j)-\alpha(i))=-a$

$i,j\in\{1,...,n\}$

So if now $\alpha=\tau_1...\tau_k=\lambda_1...\lambda_m$

$\prod_{j>I}(\alpha(j)-\alpha(i))=(-1)^k\times a=(-1)^m\times a$.

Questions:

1)I think this proof is incomplete. How can I complete it?

2)How can $\prod_{j>i}(\alpha(j)-\alpha(i))$ measure the number of transpositions? As far as I understand it measuring the number of transformations that is not the number of transpositions that compose $\alpha$.

Thanks in advance!

$\endgroup$
  • $\begingroup$ 1) Why do you think it is incomplete? 2) What do you mean "number of transformations"? $\endgroup$ – Trevor Gunn Oct 1 '17 at 18:40
  • $\begingroup$ Number of transformations. Consider the permutation $(1324)\in S_4$, the number of transformations would be 1to3, 3to2, 2to4and 4to 1, that equals 4.I think it is incomplete because I doubt the notes are complete. $\endgroup$ – Pedro Gomes Oct 1 '17 at 18:45
  • $\begingroup$ "I think it is incomplete because I doubt the notes are complete." - This remark is not as informative as perhaps you'd like it to be. $\endgroup$ – Matt Oct 1 '17 at 19:02
1
$\begingroup$

Let me address your second concern first. The action of $\alpha$ on $\prod_{j > i}(j - i)$ isn't counting the number of transformations, it is counting the number of inversions. Or rather, the parity (even- or odd-ness) of this number.

Definition: An inversion of a permutation $\alpha$ is a pair $\{i,j\}$ with $i < j$ and $\alpha(i) > \alpha(j)$.

For example the permutation $(12)(34)$ has two inversions: $\{1,2\}$ and $\{3,4\}$. Notice that if $\{i,j\}$ is an inversion of $\alpha$ and $(j - i)$ is positive, then $(\alpha(j) - \alpha(i))$ is negative. The sign of a permutation can alternatively be written as $(-1)^n$ where $n$ is the number of inversions.

When we apply $(12)(34)$ to the product $$(4 - 1)(4 - 2)(4 - 3)(3 - 1)(3 - 2)(2 - 1)$$ we get

$$ (3 - 2)(3 - 1)\color{red}{(3 - 4)}(4 - 2)(4 - 1)\color{red}{(1 - 2)} $$

The red terms are where the inversions are and also where we pick up a factor of $-1$.

On the other hand, the permutation $(1324)$ has 5 inversions:

$$ \color{red}{(1 - 3)}\color{red}{(1 - 4)}\color{red}{(1 - 2)}\color{red}{(2-3)}\color{red}{(2 - 4)}(4 - 3). $$

Therefore $(12)(34)$ is an even permutation ($\operatorname{sgn}((12)(34)) = (-1)^2 = 1$) and $(1324)$ is an odd permutation ($\operatorname{sgn}((1324)) = (-1)^5 = -1$).

Caution: It is tempting to say that the number of inversions of $\sigma \pi$ is the sum of the number of inversions of $\sigma$ plus the number of inversions of $\pi$. However, this is incorrect as simply taking $\sigma = \pi = (12)$ will show you. Both $\sigma$ and $\pi$ have 1 inversion and $\sigma \pi = \iota$ has zero inversions.

Now with this in mind, we can prove that the sign of a permutation is well-defined as follows. Note that the concept of inversions is only used in the first step.

  1. Show that if $(ij)$ is a transposition, then $(ij)$ has only one inversion, namely $\{i,j\}$. Therefore $$(ij)\cdot\prod_{j > i}(j - i) = -\prod_{j > i}(j - i). $$

  2. It follows from (1) that given a product $\alpha = \tau_1 \cdots \tau_k$ of $k$ permutations then $$\alpha \cdot\prod_{j > i}(j - i) = (-1)^k \prod_{j > i}(j - i). $$

  3. Therefore if $\alpha$ is a product of $k$ transpositions and of $m$ transpositions then $(-1)^k = (-1)^m$.

$\endgroup$
  • $\begingroup$ Thank you! The answer is marvellous! $\endgroup$ – Pedro Gomes Oct 1 '17 at 19:54

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.