A question regarding permutations in terms of transpositions.

66 Views Asked by At

Let $S_n$ be the symmetric group, i.e. the group of permutations of the set $<n>=\{1,2,\dots,n\}$.

Let $\sigma\in S_n$ be of the form $\sigma=\tau_{i_k}\tau_{i_{k-1}}\cdots \tau_{i_1}$ where each $\tau_{i_\ell}=(i_\ell$, $i_{\ell}+1)$ is a transposition. Let us assume that the the description of $\sigma$ is minimal in the sense that it cannot be written as composition of fewer transpositions of the form $\tau_j$ for some $j \in <n>$. We denote this number as $|\sigma|=k$.

Let $\theta \in S_n$ with $\theta=\tau_{j_\ell}\cdots \tau_{j_1}$ such that $|\theta|=\ell$. Assume that for every $s \in \{1,2,\dots,\ell\}$ we have $|\tau_{j_s}\sigma|=k+1$.

Question: Does it follow that $|\theta \circ \sigma|=k+\ell$?

What about the weaker statement $|\theta \circ \sigma|> k$?

Edit: Let us assume that $k+\ell$ is smaller than $m=\max|\rho|$, $\rho \in S_n$

1

There are 1 best solutions below

0
On

To answer the question I will take inverses.

So we have $\sigma$ with $|\sigma|=k$ and $|\theta|=\ell$ and I will show that $|\sigma \circ \theta|=\ell+k$.

Recall that for every $\sigma \in S_n$ it follows that $\operatorname{inv}(\sigma)=|\sigma|$ where $\operatorname{inv}(\sigma)$ is the number of pairs $(i,j)$ with $i<j$ such that $\sigma(i)>\sigma(j)$.

We have the following fact: Given $\hat{\sigma}=\sigma \tau_i$ we have that
$$\hat{\sigma}=\begin{cases} |\sigma|+1, \text{ if } \sigma(i)<\sigma(i+1) \\ |\sigma|+1, \text{ if } \sigma(i) > \sigma(i+1) \end{cases}$$

Our hypothesis guarantee that $\sigma(j_{s})< \sigma(j_{s}+1)$ for $s=1,\dots,\ell$.

Let $\rho=\sigma \circ (\tau_{j_1} \cdots \tau_{j_{\ell-1}})$ so that $\rho \circ \tau_{j_{\ell}}=\sigma$. We want to show that $\rho(j_{\ell}) <\rho(j_\ell +1)$.

I claim I can assume that there exists $\alpha \in \{1,\dots,\ell-1\}$ such that $\tau_{j_\alpha}(j_{\ell})\neq j_\ell$ or $\tau_{j_\alpha}(j_{\ell}+1)\neq j_{\ell}+1$. Otherwise $\rho(j_{\ell})=\sigma(j_{\ell})<\sigma(j_\ell+1)=\rho(j_\ell+1)$ and we are done. I will assume that $\alpha$ is the smallest such index.

Moreover $j_{\alpha}\neq j_{\ell}$ since otherwise $|\theta|<\ell$. This follows because $\tau_{j_\alpha}$ commutes with $\tau_{j_r}$ with $j_r > j_\alpha$ by construction.

Note that in the pair $(j_\ell, j_\ell+1)$ the action of $\tau_{j_\alpha}$ can either decrease the value of $j_{\ell}$ or increase the value of $ j_\ell+1$.

If $\alpha=1$ and $j_\alpha=j_{\ell}-1$ we see that $\rho(j_\ell)=\sigma(j_{\ell}-1)<\sigma(j_\ell)<\sigma(j_{\ell}+1)=\rho(j_\ell+1)$. That chain of inequalities follows from the hypothesis. We reach a similar conclusion if $j_\alpha=j_\ell+1$.

One keeps repeating this procedure step by step if $\alpha >1$. The only possible "weird" case that could happen is if we have to apply $\tau_{j_u}$ to $(j_u , j_{u}+1)$.

Luckly this cannot happen since this would imply that $|\theta|<\ell$