The signature of a permutation

Question

Let $S_n$ denote the group of permutations on $n$ symbols. For a fixed pair $1\leq l<m\leq n$ and consider the subset $$S_n(l,m)=\{\sigma\in S_n: \sigma(1)=l, \sigma(2)=m\}.$$ Then $S_n(l,m)$ can be identified with the group $S_{n-2}$ (right?).

Now if I pick an element $\sigma\in S_n(l,m)$ it will corresponds to a unique element $\tau \in S_{n-2}$. The question is how do I relate the signature of $\sigma$ with the signature of $\tau$? I was hoping that the signature of $\tau$ will depend on $l$ and $m$ (actually what I had in mind is that $\text{sgn}(\tau)=(-1)^{l+m}\text{sgn}(\sigma))$ but I'm not quite sure how to start proving this.

Answer 1

As in my comment, $S_n(l,m)$ is not a subgroup of $S_n$ when $(l,m)\neq (1,2)$.$\newcommand{\sgn}{\text{sgn}}$ The formula $\sgn(\tau)=(-1)^{l+m}\sgn(\sigma)$ is definitely wrong because if you swap $l$ and $m$, the $\sgn(\sigma)$ changes, but $\sgn(\tau)$ does not change. Try $(n,l,m)=(3,1,2)$ and $(n,l,m)=(3,2,1)$.

The most natural identification (though not necessarily a group isomorphism) from $S_n(l,m)$ to $S_{n-2}$ is simply $\sigma\mapsto \sigma|_{\{3,\dots,n\}}$. Denote this map by $\varphi$.

Denote by $N(\sigma)$ the number of inversions of $\sigma$. Denote by $M_\sigma(i)$ the number $$|\{(i,j):i< j\le n, \sigma(i)>\sigma(j)\}|.$$ For all $\sigma\in S_n(l,m)$, we have $$ N(\sigma)=M_\sigma(1)+M_\sigma(2)+N(\varphi(\sigma)). $$ Therefore, $$ \sgn(\varphi(\sigma))=(-1)^{M_{\sigma}(1)+M_{\sigma}(2)}\sgn(\sigma). $$

Answer 2

The exact signature depends on the bijection you use. Depending on the bijection you will either have $sgn(\sigma)=sgn(\tau)$ or $sgn(\sigma)=-sgn(\tau)$.

One particularly simple bijection gives: $sgn(\tau)=sgn(\sigma)(-1)^{1(l=1)+1(m=2)+1(l=2,m=1)}$

For this bijection, define a permutation $\alpha$ which swaps $1,l$ and $2,m$. Then, identifying $S_{n-2}$ as a subset of $S_n$ permuting $3,\dots,n$ gives a bijection by $\tau=\alpha \sigma$. The signature of alpha gives a transposition if $1$ is swapped with something else, another for $2$, and double counts if those two are the same when $l=2$ and $m=1$.

Answer 3

Let $M$ any finite set. The every $\phi\colon M\to M$ has a well defined signature. For instance, decompose $\phi$ into a product of disjoint cycles. Then $\operatorname{sign}(\phi)$ is $1$ or $-1$, depending whether the number of even cycles is even, or odd

$3$ E mnemonic: $\bf{E}$ven number of $\bf{E}$ven cycles is $\bf{E}$ven.

(Yes, a cycle of odd length is even and the other way around. To dispel the mystery, recall that a cycle of length $\ell$, raised to power $\ell$ is the identity. So a cycle of odd length, at an odd power is the identity. So it must be even.)

---

Now, let $M$, $N$ finite sets and $\phi\colon M \to N$. Then the signature of $\phi$ is not defined ( notice that $M$ and $N$ are not the same).

However, assume that moreover, $M$, $N$ are totally ordered sets, and $\phi$ a bijection from $M$ to $N$. Then the signature of $\phi$ can be defined. How? Well both $M$, $N$ are order isomorphic ( uniquely) to some $\{1,\ldots, m\}$. So now $\phi$ is like a bijection from $\{1, \ldots, m\}$ to itself, so it has a signature.

---

Now, we come to the most interesting part: how to get the signature of a permutation from its "pieces". What do we mean by that. Say $M$ is a finite totally ordered set ( you can think $M= \{1, \ldots, n\}$). Let $\phi \colon M \to M$ a bijection. Consider its signature. Ok, no problem. But now do this. Take $I$ a subset of $M$ ( non-void), $I'$ its complement, and let $J = \phi(I)$, $J'$ its complement. Then we have the bijections

$$\phi_{\mid I} \colon I \to \phi(I)= J \\ \phi_{\mid I'} \colon I' \to \phi(I')= J'$$

So now we have three maps $\phi$, $\phi_{\mid I}$ and $\phi_{\mid I'}$. Recall that from above, we have a well defined signature of the latter two. OK, what is the relation between them? There is a very nice formula as follows:

$$\operatorname{sign}( \phi) = \epsilon (I,J) \cdot \operatorname{sign}( \phi_{\mid I})\cdot \operatorname{sign}( \phi_{\mid I})$$

The only thing not clear above is $\epsilon (I, J)$. That involves the parity of the disturbance between $I$ and $J$, and is obtained as follows: say the ranks of the elements of $I$ ( in the ordered set $M$) are $i_1$, $\ldots$, $i_k$, and the ranks of the elements of $J$ are $j_1$, $\ldots$, $j_k$. Then

$$\epsilon(I,J) = (-1)^{\sum_{s=1}^k (i_s + j_s)}$$

---

I should add that this is exactly the ingredient in the Laplace expansion of a determinant.

---

Let's give an example. Consider the permutation

$$\phi\colon \ \ \ \left( \begin{matrix} 1&\color{red}{2}&\color{red}{3}&4&5&6&\color{red}{7}&8&9&\color{red}{10} \\ 10 &\color{red}{1}& \color{red}{8}& 5 &7 &6 &\color{red}{3}& 4 &9& \color{red}{2}\end{matrix}\right)$$

Take $I = \{2, 3, 7,10 \}$, $J=\phi(I) = \{ 1, 8, 3, 2\}$, $I' = \{ 1, 4, 5, 6, 8, 9\}$, $J'= \{ 4, 5, 6, 7, 9, 10\}$, and the permutations are

\begin{eqnarray} \phi_{\mid I}\ \ \ &\colon& \left( \begin{matrix} 2& 3& 7& 10 \\ 1& 8& 3& 2 \end{matrix} \right ) \\ \phi_{\mid I'}\ \ \ &\colon& \left ( \begin{matrix} 1&4&5&6&8&9 \\10&5&7&6&4&9 \end{matrix} \right ) \end{eqnarray}

Now, one has to "translate" $\phi_{\mid I}$,$\phi_{\mid I'}$, into permutations of $\{1,2,3,4\}$, and $\{1,2,3,4,5,6\}$ as follows:

\begin{eqnarray} \left( \begin{matrix} 1 & 2& 3& 4 \\ 1& 4 & 3 & 2 \end{matrix} \right ) , \left( \begin{matrix} 1&2&3 &4 & 5 & 6 \\ 6&2&4&3&1&5 \end{matrix} \right) \end{eqnarray}

Now the first one above is the transposition $(2,4)$, odd, the second one is $(3,4)\cdot ( 1,6,5)$, odd again.

Let us calculate $\epsilon(I, J)$. We have $2+3+7+10 + 1+2+3+8$ even, so it is $1$. According to this, the signature of $\phi$ should be $(-1) \cdot (-1) \cdot 1 = 1$. Is that correct? The cycle decomposition of $\phi$ is $(1,10,2) \cdot (3,8,4,5,7)$, $0$ Even cycles so Even. Yes!