# does this set of permutations form a group? And more

Consider the group of $mn\times mn$ permutation matrices $\mathfrak{S}_{mn}$ and partition each such matrix $P$ into $n^2$ blocks of $m\times m$ matrices $Q_{i,j}$. Now, transpose each $Q_{i,j}$ (independently) to form a new $mn\times mn$ matrix denoted $P^t$ (with an abuse of notation). Let's construct the set $U_{mn}:=\{P^t\in\mathfrak{S}_{mn}:\, P\in\mathfrak{S}_{m,n}\}$.

It's clear that if $m=1$ then $U_{mn}=\mathfrak{S}_{mn}$; the same if $n=1$.

Question 1. For which $m$ and $n$, does $U_{mn}$ form a group?

UPDATE. Negative answer shown below.

A cute note: $\frac{\#\mathfrak{S}_{2n}}{\# U_{2n}}=C_n$ is the Catalan number. Is $\# U_{2n}$ a subgroup? Answer. No. See below. Another counterexample to the converse of Lagrange's theorem: $\# U_{2n}$ divides $\#\mathfrak{S}_{2n}$ but $U_{2n}$ is not a subgroup of $\mathfrak{S}_{2n}$.

Question 2. View $P\in U_{2n}$ as $P\leftrightarrow\sigma$ as a $1$-line permutation $\sigma=(\sigma_1,\dots,\sigma_{2n})$. In this way, what is an equivalent (to the above "transpose") characterization of $P$ in the language of $\sigma$?

UPDTE. I am Still waiting for an answer.

If you're interested in enumeration then visit here.

• It seems to me that $U_{mn}$ contains the full stabilizer $G$ in $S_{mn}$ of a partition of $[mn]$ into $n$ parts of size $m$. As $G$ is a maximal proper subgroup of $S_{mn}$ when $m,n>1$, we see that if $U_{mn}$ is a subgroup, then it is $G$ or $S_{mn}$. It should not be hard to show that neither $U_{mn}=G$ nor $U_{mn}=S_{mn}$ holds when $m,n>1$. – John Shareshian Jan 3 '17 at 19:40
• Do you have any examples for $m, n \neq 1$? It's not a group for $m = n = 2$. – user44191 Jan 3 '17 at 20:28
• I think it's very confusing if you edit your question changing just two words. Wouldn't it be more appropriate to set a bounty? – Martin Rubey Mar 5 '17 at 9:14

## 1 Answer

For $m, n > 1$ it's never a group.

Let $\sigma \in \mathfrak{S}_n$, $\sigma$ switches $1, m + 1$, and in fact $\sigma = \sigma^t$. Clearly, $\sigma \in U_{mn}$. Similarly, let $\tau$ switch $1, 2$; similarly, $\tau = \tau^t$. Then $\sigma \tau \sigma$ switches $2, m+1$. This clearly is not in $U_{mn}$.

• Thanks. It's a pity outcome though. – T. Amdeberhan Jan 3 '17 at 21:43