4
$\begingroup$

Suppose $m,n\ge 1$ are integers. Do row and column permutations of an $m\times n$ matrix generate the group of all permutations of the $mn$ entries of the matrix?

More formally, let $A_1$ be the matrix $$ A_1 = \left[\begin{array}{cccc} 1 & 2 & \cdots & n \\ n+1 & n+2 & \cdots & 2n \\ \vdots & \vdots & \ddots &\vdots \\ (m-1)n+1 & (m-1)n + 2 & \cdots & mn \end{array}\right] $$ and let $A_2$ be an $m\times n$ matrix such that each of the numbers $1,\ldots, mn$ appears (exactly once) as an entry in $A_2$. Is there necessarily a sequence of row and column permutations that transforms $A_1$ into $A_2$? If not, can one easily characterize which permutations are generated by row and column permutations?

$\endgroup$

3 Answers 3

6
$\begingroup$

No, each row permutation commutes with each column permutations and altogether they generate a group isomorphic to $S_m \times S_n$ which (at least when $m,n>1$) is a proper subgroup of $S_{mn}$.

$\endgroup$
2
  • $\begingroup$ Thanks for the quick reply. What does "each row permutation permutes with each column permutation[s]" mean? $\endgroup$ Jun 11, 2014 at 22:17
  • $\begingroup$ Ahhh, you mean commutes. Wow, simple! $\endgroup$ Jun 11, 2014 at 22:20
5
$\begingroup$

Here's an easy concrete way to see that not all permutations are generated: consider any two elements in the same row (e.g., $1$ and $2$ in your matrix $A_1$). Then any permutation of the columns of $A$ leaves these two elements in the same row because no element changes its row; and any permutation of the rows of $A$ also leaves these two elements in the same row, since the entire contents of a row move as one. Therefore, any matrix which has the elements in different rows is unreachable.

$\endgroup$
2
$\begingroup$

That's not true in general.

Verify that if $m$ (resp. $n$) is even, any row (resp. column) permutation is an even permutation, since it is a composition of $m$ (resp. $n$) transpositions. So, when $2\mid m, n$, we have $G \leq A_{m n}$, and $G\neq S_{m n}$.

But raises a really good question (answered by the previous answer), what is the subgroup $G$ generated by the row and column permutations in $G \leq S_{m n } $?

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .