2
$\begingroup$

I am trying to understand the definition of the sign of a permutation $\pi$.

My textbook only mentions that $\operatorname{sgn}(\pi) = (-1)^k$ , where $k$ is the number of transpositions .

But I have also found online that $\operatorname{sgn}(\pi) = (-1)^{\operatorname{inv}(\pi)}$, where $\operatorname{inv}(\pi)$ is the number of inversions on a permutation.

Does this mean $ k = \operatorname{inv} (\pi)$ in general ?

I am trying to show if $\pi$ is a product of $k$ transpositions , then $k \equiv \operatorname{inv}(\pi)\pmod2$

In general, the $\operatorname{sgn}(\pi) = 1$ if $\pi$ is a product of even number of transpositions.

And $\operatorname{sgn}(\pi) = -1$ if $\pi$ is a product of odd number of transpositions.

So I was thinking that if $k$ is even, then $\operatorname{inv}(\pi)$ is even and so $2\mid\operatorname{inv}(\pi) - k $ and similarly if $k $ is odd, then $\operatorname{inv}(\pi)$ is odd, so $2\mid\operatorname{inv}(\pi) - k$ . So $k \equiv \operatorname{inv}(\pi) \pmod 2$)

Can someone please verify this? Any better approach or feedback would help! Would I have to prove this part of the definition? Thank you !

$\endgroup$
  • $\begingroup$ I edited for proper use of \operatorname{sgn}, \operatorname{inv}, \pmod, and \mid . $\qquad$ $\endgroup$ – Michael Hardy Feb 8 '16 at 18:54
  • $\begingroup$ $k$ does not equal $\operatorname{inv}(\pi)$ in general. For instance, the permutation $(1,4)(2)(3)$ has one transposition but five inversions: $(1,2),(1,3),(1,4),(2,4),(3,4)$. $\endgroup$ – TonyK Feb 8 '16 at 18:58
  • $\begingroup$ in mod 2 they are both equal? How could I relate both the inversion and sign together? I am not sure then, how to approach my problem $\endgroup$ – Mahidevran Feb 8 '16 at 19:00
  • 1
    $\begingroup$ @Mahidevran: Yes, mod 2 they are equal. $\endgroup$ – Alex M. Feb 8 '16 at 19:01
  • $\begingroup$ I am confuse about how to prove $k \equiv inv(\pi)$mod$2$ , because my book does not mention any definition about inversion. It only mentions it's a permutation such that the pair of indices $i < j$ and $\pi(i) > \pi(j)$.\ $\endgroup$ – Mahidevran Feb 8 '16 at 19:05
4
$\begingroup$

To see why they are both the same, first prove the following lemma:

Lemma 1 $$\mbox{sgn}(\sigma) =\prod_{1 \leq i < j \leq n} \frac{\sigma(j)-\sigma(i)}{ j-i}$$

To prove it, first note the the RHS must have absolute value 1, as every pair $(k,l)$ appears once at the bottom and once at the top. Therefore the RHS is $\pm 1$, and all you need to do is track the sign. Finally for the RHS you get a minus for each inversion.

Next, use this to get:

Lemma 2 $$\mbox{sgn}(\sigma \circ \tau) =\mbox{sgn}(\sigma)\mbox{sgn}( \tau)$$

Idea of proof: By Lemma 1: $$ \mbox{sgn}(\sigma \circ \tau)=\prod_{1 \leq i < j \leq n} \frac{\sigma \circ \tau (j)-\sigma \circ \tau(i)}{ j-i} \\ =\prod_{1 \leq i < j \leq n} \frac{\sigma \circ \tau (j)-\sigma \circ \tau(i)}{ \tau (j)- \tau(i)} \cdot \prod_{1 \leq i < j \leq n} \frac{ \tau (j)- \tau(i)}{ j-i}=\mbox{sgn}(\sigma)\mbox{sgn}( \tau) $$ by a similar computation to Lemma 1.

Lemma 3 If $\tau$ is a transposition $(i,j)$ then $$\mbox{sgn}(\tau)=-1$$

Proof Just count the inversions.

Combining Lemma 3 and Lemma 2, you finally get:

Theorem Let $\sigma=\tau_1 \cdot ...\cdot \tau_k$ where $\tau_j$ are all transposition. Then $$\mbox{sgn}(\sigma)=(-1)^k$$

$\endgroup$
  • $\begingroup$ Very nice.${}{}$ $\endgroup$ – TonyK Feb 8 '16 at 19:27
  • $\begingroup$ Does lemma 3 imply sgn is well defined, and independent of the particular decomposition of $\pi$ into transpositions? $\endgroup$ – Mahidevran Feb 8 '16 at 19:36
  • $\begingroup$ @Mahidevran Lemma 2 and Lemma 3 together imply that. $\endgroup$ – N. S. Feb 8 '16 at 19:41
  • $\begingroup$ Just to understand , $$\mbox{sgn}(\sigma \circ \tau)$$ is a composition of a transposition $\tau$? $\endgroup$ – Mahidevran Feb 8 '16 at 19:44
  • $\begingroup$ @Mahidevran Yes. Composition (or product) or permutations. $\endgroup$ – N. S. Feb 8 '16 at 19:45
1
$\begingroup$

Let's assume we have an arbitrary order of n numbers and we want to swap the elements at the "i"th and "j"th position ($a_i$ and $a_j$). When they are swapped, their order regarding to elements from $a_1$ to $a_{i-1}$ and from $a_{j+1}$ to $a_n$ does not change. Therefore, we should concentrate on the elements between them ($a_{i+1}$ to $a_{j-1}$). If there are $m$ elements between $a_i$ and $a_j$, by moving $a_i$ to $a_j$'s place, either we add an inversion or we delete an inversion (consider the elements between them one at a time). Let's assume we add $x_1$ inversions and delete $y_1$ inversions. Note that $x_1 + y_1 = m$. Same is true when we move $a_j$ to $a_i$'s place (it adds $x_2$ and deletes $y_2$ inversions and $x_2 + y_2 = m$). After considering $a_i$ and $a_j$ themselves, which either adds or deletes an inversion, we have added a total of $x_1+x_2-y_1-y_2\pm1$ inversions. As $m=x_1+y_1$ has the same parity as $x_1-y_1$, the total parity is definitely an odd number. So, each operation of swapping adds or removes an odd number of inversions. Just like transpositions.

$\endgroup$
  • $\begingroup$ Does $x_1+x_2-y_1-y_2\pm1$ , mean $x_1+x_2-y_1-y_2 + 1 $ or $x_1+x_2-y_1-y_2 - 1 $? $\endgroup$ – Mahidevran Feb 8 '16 at 20:09
  • $\begingroup$ it can be any of them, depending on the relative order of ai and aj $\endgroup$ – Med Feb 8 '16 at 21:20
1
$\begingroup$

Here is a geometric definition. Perhaps it might appeal to you.

An $n$-simplex is an $n$-dimensional generalization of a triangle. In small dimensions, we have:

A $0$-simplex is a point. A $1$-simplex is a line segment. A $2$-simplex is a triangle. A $3$-simplex is a tetrahedron.

In general, an n-simplex consists of points $(x_1, x_2, x_3, ..., x_{n+1})$ in $\mathbb{R}^{n+1}$ such that $x_i \ge 0$ for each $x_i$ and such that $\sum_i x_i = 1$.

(Try graphing this definition for $n=1$ and see that it does, in fact, produce the line segment from $(1, 0)$ to $(0, 1)$ on the plane).

Simplices are the bread and butter of algebraic topology. Many times we like to triangulate a space by approximating it with $n$-simplices.

Anyway, back to permutations.

The symmetric group of order $n$ forms the group of isometries of the $n$-simplex. Visualizing this in the case of the triangle or tetrahedron, we see that we can generate any element of the symmetric group by a series of rotations of the triangle/tetrahedron or reflections.

The sign of a permutation is really, then, an indicator telling you if a given transformation can be obtained using only rotations. Put another way, when $\text{sgn}(\pi) = 1$, the tetrahedron will merely be rotated, but when $\text{sgn}(\pi) = -1$, the simplex will be turned inside-out.

This question of whether a simplex will be turned inside out leads to the notion of orientation.

$\endgroup$

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.