# Understanding the definition of the sign of a permutation , $\operatorname{sgn}(\pi) = (-1)^k$ .

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 !

• I edited for proper use of \operatorname{sgn}, \operatorname{inv}, \pmod, and \mid . $\qquad$ – Michael Hardy Feb 8 '16 at 18:54
• $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)$. – TonyK Feb 8 '16 at 18:58
• 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 – Mahidevran Feb 8 '16 at 19:00
• @Mahidevran: Yes, mod 2 they are equal. – Alex M. Feb 8 '16 at 19:01
• 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)$.\ – Mahidevran Feb 8 '16 at 19:05

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

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

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.

• 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$? – Mahidevran Feb 8 '16 at 20:09
• it can be any of them, depending on the relative order of ai and aj – Med Feb 8 '16 at 21:20

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.