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$
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$
  • $\begingroup$ Thanks for the quick reply. What does "each row permutation permutes with each column permutation[s]" mean? $\endgroup$ – Will Nelson Jun 11 '14 at 22:17
  • $\begingroup$ Ahhh, you mean commutes. Wow, simple! $\endgroup$ – Will Nelson Jun 11 '14 at 22:20
4
$\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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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