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

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

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

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.