4
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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*} $\endgroup$ – Hussein Eid Dec 25 '16 at 20:52
  • $\begingroup$ @HusseinEid Sorry; I was not clear enough. Please see my above edited answer. $\endgroup$ – Noble Mushtak Dec 25 '16 at 21:04
  • 1
    $\begingroup$ I think you have a different definition of inversion than @HusseinEid does $\endgroup$ – Akiva Weinberger Dec 25 '16 at 23:47
  • $\begingroup$ I think you are writing about transpositions rather than inversions. $\endgroup$ – André 3000 Dec 26 '16 at 1:30
  • $\begingroup$ @HusseinEid I have once again edited my answer because it was not clear enough even in my second revision. $\endgroup$ – Noble Mushtak Dec 26 '16 at 2:19
0
$\begingroup$

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*}

$\endgroup$
0
$\begingroup$

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.

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