The number of permutations that can be written in two ways as a product of row and column permutations of a Young tableau

permutationssymmetric-groupsyoung-tableaux

My question is related to an issue in the book "Young tableaux" by W.Fulton. Consider a Young tableau $T$ of a given fixed shape filled with integers $1,\ldots,n$. A permutation $\sigma$ in the permutation group of $n$ elements $S_n$ maps the tableau $T$ to a new tableaux $\sigma T$ in which the entries $i$ are replaced by $\sigma (i)$. Let $R(T)$ and $C(T)$ be the groups of row and columns permutations that respectively map rows to rows and columns to columns. We consider a special set of permutations $\sigma$ that can be written in two ways as a product of a row and column permutation:
$$
\sigma = \varkappa \, \varrho = \rho^\prime \varkappa^\prime
$$

where $\varrho, \varrho^\prime \in R(T)$ and $\varkappa, \varkappa^\prime \in C(T)$. We then can divide all permutations that can be written this way in two sets which I call $S_+$ and $S_-$ and which are defined as
$$
S_+ = \{ \sigma \in S_n | \,\exists \,\varrho, \varrho^\prime \in R(T), \varkappa, \varkappa^\prime \in C(T) :\sigma = \varkappa \, \varrho = \varrho^\prime \varkappa^\prime \, \wedge \text{sgn} (\varkappa)= \text{sgn} (\varkappa^\prime) \, \}
$$

and
$$
S_- = \{ \sigma \in S_n | \,\exists \,\varrho, \varrho^\prime \in R(T), \varkappa, \varkappa^\prime \in C(T) :\sigma = \varkappa \, \varrho = \varrho^\prime \varkappa^\prime \, \wedge \text{sgn} (\varkappa)= -\text{sgn} (\varkappa^\prime) \, \}
$$

They are the sets of all permutations that can be decomposed in two ways in a product of row and column permutations using column permutations of equal sign (set $S_+$) or using column permutations of opposite sign (set $S_-$). In Lemma 5 of section 7.4 of the book of Fulton only the first set $S_+$ is considered where it is also shown that the number of its elements $|S_+|$ only depends on the shape of $T$ (the same applies to $S_-$ using the same argument of Fulton). In the proof of Lemma 5 I do not exactly understand why the set $S_-$ is discarded as it seems to be needed for the proof (perhaps someone can enlighten me) but at least I can see that the proof works if
the number of elements $|S_-|$ is different from that of $|S_+|$.

My question is then: is there an easy way to see that for any tableau $|S_-| \neq |S_+|$ or even $|S_+| > |S_-|$
(which I believe to be the case) ?

There are some easy limiting cases: for the tableau of shape $(n)$ all permutations are row permutations and for the tableau of shape $(1^n)$ all permutations are column permutations. In both these trivial cases $|S_+|=n!$ and $|S_-|=0$. I doubt that, in general, there is any easy formula for the sizes $|S_+|$ and $|S_-|$ but it would be interesting if there was one.

To show some examples of permutations from both sets I have displayed two cases in a figure. It turns out to be more convenient to define
$$
\varrho_\varkappa = \varkappa \varrho \varkappa^{-1} \in R (\varkappa T ) \quad \quad \text{and}
\quad \quad \varkappa_\varrho^\prime = \varrho^\prime \varkappa^\prime \varrho^{\prime -1}
\in C (\varrho^\prime T)
$$

which are simply the row permutations on the column permuted tableau $\varkappa T$ and the column permutations on the row permuted tableau $\varrho^\prime T$. Then we can write
$$
\varrho_\varkappa \varkappa = (\varkappa \varrho \varkappa^{-1} ) \varkappa =
\varkappa \,\varrho = \sigma = \varrho^\prime \varkappa^\prime = (\varrho^\prime \varkappa^\prime \varrho^{\prime -1} ) \,\varrho^\prime = \varkappa_\varrho^\prime \,
\varrho^\prime
$$

So the permuted tableau $\sigma T$ is obtained by first performing a column permutation on $T$and then a row permutation on the permuted tableau $\varkappa T$ and at the same time obtained by first performing a row permutation on $T$ and a subsequent column permutation on the permuted tableau $\varrho^\prime T$. This is illustrated in the following figure:enter image description here

In the example on the left we have the permutation $\sigma = (12476539)$ for a Young tableau of shape $(3,3,3)$ where we have the permutations
\begin{align}
&\varkappa = (147)(396)
&\varkappa_\varrho^\prime = (19) (34) (67) \nonumber \\
&\varrho^\prime = (123) (465)
&\varrho_\varkappa = (24) (35) (16)
\end{align}

and we see that $\text{sgn} (\varkappa)= -\text{sgn} (\varkappa_\varrho^\prime)=1$
and therefore $\sigma \in S_-$.
In the example on the right we have $\sigma =(2847536)$ for a Young tableau of shape $(3,3,2)$
with permutations
\begin{align}
&\varkappa =(285) (36) (47)
&\varkappa_\varrho^\prime = (384) (26) (57) \nonumber \\
&\varrho^\prime = (23) (45)
&\varrho_\varkappa = (23) (45)
\end{align}

and $\text{sgn} (\varkappa)= \text{sgn} (\varkappa_\varrho^\prime)=1$ and we see that $\sigma \in S_+$.

Best Answer

If we let $$ P(T)=\sum_{p\in R(T)}p $$ and $$ N(T)=\sum_{p\in C(T)}{\rm sgn}(q)\ q\ , $$ then the coefficient of the identity permutation in $P(T)N(T)P(T)N(T)$ is $$ \left.P(T)N(T)P(T)N(T)\right|_{\rm Id}=\sum_{p_1,p_2\in R(T)}\sum_{q_1,q_2\in C(T)} {\rm sgn}(q_1)\ {\rm sgn}(q_2)\ \mathbf{1}\{p_1q_1p_2q_2={\rm Id}\} $$ where $\mathbf{1}\{\cdots\}$ is the indicator function of the logical statement between braces.

Now $$ \left.P(T)N(T)P(T)N(T)\right|_{\rm Id} =|S_+|-|S_-| $$ because given a $\sigma$, the $\varrho,\varrho',\varkappa,\varkappa'$ are unique as follows from the key fact of the theory $R(T)\cap C(T)=\{{\rm Id}\}$.

However, $P(T)N(T)P(T)N(T)=H_{T}P(T)N(T)$ where $H_{T}$ is the product of hook lengths of the shape of $T$. Moreover, the coefficient of the identity in $P(T)N(T)$ is $1$ again by the key fact above.

In sum, we have $$ |S_+|-|S_-|=H_{T}>0\ . $$

Related Question