Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
add comment

3 Answers 3

up vote 5 down vote accepted

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

share|improve this answer
    
Thanks for the quick reply. What does "each row permutation permutes with each column permutation[s]" mean? –  Will Nelson Jun 11 at 22:17
    
Ahhh, you mean commutes. Wow, simple! –  Will Nelson Jun 11 at 22:20
add comment

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.

share|improve this answer
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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