# The sign function is a homomorphism

We define an inversion of a permutation $\sigma\in S_k$ to be a pair $(\sigma(i), \sigma(j))$ such that $i<j$ but $\sigma(i)> \sigma(j)$. The sign of $\sigma$, written $\text{sgn}(\sigma)$, is defined by

\begin{align*} \text{sgn}(\sigma) = (-1)^{\# \text{ of inversions in }\sigma} = \begin{cases} +1 &\text{ if the number of inversions in $\sigma$ is even}\\ -1 &\text{ if the number of inversions in $\sigma$ is odd} \end{cases}. \end{align*}

I want to prove that: $\text{sgn}(\sigma \tau)= (\text{sgn }\sigma)(\text{sgn }\tau)$ for any two permutations $\sigma$ and $\tau$, using the above definition. I tired many times but i failed. If I got some equation relating the number of inversions of $\sigma$, $\tau$ and the composite $\sigma\tau$, I had done. I need your help please.

Yes, one can prove it directly by counting inversions. Starting with $i<j$, apply $\tau$ and get the pair $(i_1,j_1)$ defined by $$i_1=\tau(i)\qquad j_1=\tau(j).$$ Then apply $\sigma$ and get the pair $(i_2,j_2)$ defined by $$i_2=\sigma(i_1)=\sigma\tau(i)\qquad j_2=\sigma(j_1)=\sigma\tau(j).$$ In summary $$(i,j)\to^{\tau}(i_1,j_1)\to^\sigma(i_2,j_2)$$ After applying each permutation, an inversion either occurs or not. Let $x$ count the number of pairs $i<j$ such that $i_1>j_1$ and $i_2<j_2$. Let $y$ count the number of pairs $i<j$ such that $i_1>j_1$ and $i_2>j_2$. Let $z$ count the number of pairs $i<j$ such that $i_1<j_1$ and $i_2>j_2$.

The permutations of interest then have the following numbers of inversions: $$N(\tau)=x+y$$ $$N(\sigma)=x+z$$ $$N(\sigma\tau)=y+z$$ It follows that $$sgn(\sigma)sgn(\tau)=(-1)^{N(\sigma)}(-1)^{N(\tau)}=(-1)^{x+z}(-1)^{x+y}$$

$$=(-1)^{2x+y+z}=(-1)^{y+z}=(-1)^{N(\sigma\tau)}=sgn(\sigma\tau)$$

Another way to do this is to use the following argument, which I believe is the one Foote uses in his abstract algebra book:

define $\Delta = \prod_{1\le i<j\le n} (x_i-x_j)$, and put $\sigma(\Delta) = \prod_{1\le i<j\le n} (x_{\sigma(i)}-x_{\sigma(j)})$. Then, it's not too hard to show, that $\text{sgn}(\sigma)=\frac{\Delta}{\sigma(\Delta)}$ and that $\text{sgn}:S_n\to \left \{ -1,1 \right \}$ is a homomorphism of groups. (One starts by noting the effect of a given transposition on $\Delta$).

Let $N(\rho)$ be the number of inversions in $\rho$ for any permutation $\rho$. First, note that any permutation $\rho$ can be written as $N(\rho)$ transpositions.

This means $\sigma$ can be written with $N(\sigma)$ transpositions and $\tau$ can be written with $N(\tau)$ transpositions. Then, when we put the two together to get $\sigma\tau$, we are writing it by putting all of the transpositions together, meaning we just wrote $\sigma\tau$ with $N(\sigma)+N(\tau)$ transpositions. However, we can also write $\sigma\tau$ with $N(\sigma\tau)$ transpositions as according to our note at the beginning.

Now, there is a theorem that tells us that the numbers of inversions a certain permutation can be written as is either all even or all odd, and thus they are all $\equiv \pmod 2$. Since $\sigma\tau$ can be written both as $N(\sigma)+N(\tau)$ and $N(\sigma\tau)$ transpositions, we have: $$N(\sigma\tau) \equiv N(\sigma)+N(\tau) \pmod 2$$

Thus, we have the following: $$\text{sgn}(\sigma\tau)=(-1)^{N(\sigma\tau)}$$ Because of $N(\sigma\tau) \equiv N(\sigma)+N(\tau) \pmod 2$ and the fact that $a \equiv b \pmod 2$ implies $(-1)^a=(-1)^b$: $$=(-1)^{N(\sigma)+N(\tau)} \\=(-1)^{N(\sigma)}(-1)^{N(\tau)} \\=\text{sgn}(\sigma)\text{sgn}(\tau)$$

• How ??? This pretty equation does not hold for these two permutations \begin{align*} \sigma = \begin{pmatrix} 1 & 2 & 3 & 4 \\ 3 & 4 & 1 & 2 \end{pmatrix} \end{align*} and \begin{align*} \tau = \begin{pmatrix} 1 & 2 & 3 & 4 \\ 1 & 3 & 2 & 4 \end{pmatrix} \end{align*} – Hussein Eid Dec 25 '16 at 20:52
• @HusseinEid Sorry; I was not clear enough. Please see my above edited answer. – Noble Mushtak Dec 25 '16 at 21:04
• I think you have a different definition of inversion than @HusseinEid does – Akiva Weinberger Dec 25 '16 at 23:47
• I think you are writing about transpositions rather than inversions. – André 3000 Dec 26 '16 at 1:30
• @HusseinEid I have once again edited my answer because it was not clear enough even in my second revision. – Noble Mushtak Dec 26 '16 at 2:19

Let $$S_n$$ act on the set $$X = \{1, \dots , n\}.$$ For $$g\in S_n$$, define $$\operatorname{sgn}(g) = (-1)^{n+r(g)}$$, where $$r(g) = \#X/\langle{g\rangle}$$ denotes the number of distinct orbits of $$X$$ under the action of $$g$$. Now check that for any transposition $$\sigma = (ab)\in S_n$$, we have \begin{align*} r(g\sigma) = \begin{cases} r(g) + 1 & \text{a, b belong to the same orbit of S_n under \langle{g\rangle}}; \\ r(g) - 1 & \text{a, b belong to distinct orbits of S_n under \langle{g\rangle}}.\\ \end{cases} \end{align*}

One can define $$\epsilon_n: S_n \rightarrow \{1,-1\}$$ inductively by letting $$\varepsilon_1$$ be the trivial homomorphism and for $$n \geq 1$$ $$\varepsilon_{n+1}(\sigma)= \begin{cases} \varepsilon_n(\sigma) \text{ if } \sigma \in S_n \\ -\varepsilon_n((n+1 \text{ } \sigma(n+1)) \sigma) \text{ if } \sigma \notin S_n \end{cases}.$$ One now proves, with some case distinction and induction, that we have, for all $$1 \leq i < j \leq n$$, $$\varepsilon_n((i \text{ } j) \sigma)=-\varepsilon_n(\sigma)$$ and $$\varepsilon_n(\text{id})=1$$ from which it will follow that $$\varepsilon_n$$ is indeed the sign function from your question, which now is automatically well-defined since $$\varepsilon_n$$ is well-defined.