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.

Background:

I am interested in the group of permutations of the entries of a general $m\times n$ matrix. In particular, I am interested in (1) interesting sets of simple generators for this group that might be used in a puzzle or game and (2) algorithms for computing the smallest sequence of generators that produce a given permutation. This question focuses on one candidate set of generators.

Question:

Suppose $m,n\ge 1$ are integers. Consider the set of permutations of a general $m\times n$ matrix containing all single-row cyclic permutations and all single-column cyclic permutations. Is every possible permutation of matrix entries generated by this set?

More formally, for all integers $r>0$, let $\sigma_r$ be the permutation of $1,\ldots,r$ defined by $1\mapsto 2\mapsto 3\mapsto \cdots \mapsto r \mapsto 1$. For each $k=1,\ldots,m$, let $r_k:\mathbb{R}^{m\times n}\to\mathbb{R}^{m\times n}$ be defined by $$ (r_k A)_{ij} = \begin{cases} A_{ij} &\text{if } i\ne k \\ A_{i\sigma_n(j)} &\text{if }i=k. \end{cases} $$ Similarly, for each $l=1,\ldots,n$, let $c_l:\mathbb{R}^{m\times n}\to\mathbb{R}^{m\times n}$ be defined by $$ (c_l A)_{ij} = \begin{cases} A_{ij} &\text{if } j\ne l \\ A_{\sigma_m(i) j} &\text{if }j=l. \end{cases} $$

Clearly, each $r_k$ and $c_l$ is a permutation of the entries of an $m\times n$ matrix. Are all such permutations generated by $\{r_1,\ldots,r_m,c_1,\ldots,c_n\}$ ? If not, is there any easy characterization of the generated group?

EDIT:

As @Omnomnomnom pointed out in his answer, a parity argument can be used to show all odd permutations of entries cannot be generated if both $m$ and $n$ are odd, because all the generators then have even parity. But that is (obviously) not a full characterization of the permutation group generated by these cycles.

share|improve this question

2 Answers 2

up vote 6 down vote accepted

Assuming that $m,n > 1$, the group $G_{mn}$ generated is $A_{mn}$ when $m,n$ are both odd and $S_{mn}$ otherwise.

This can be proved using results of Jordan from the 1870s. They are in Section 3.3 of the book on Permutation groups by Dixon and Mortimer.

It is easy to see that the generators of $G_{mn}$ that fix $(1,1)$ generate a group that acts transitively on the remaining points, so $G_{mn}$ is 2-transitive, and hence primitive.

Now, by results of Jordan, if $G_{mn}$ contains a $2$-cycle or a $3$-cycle, then it contains $A_{mn}$. Also, if a 2-transitive group has an element with support of size $t \ge 4$, then either it contains the alternating group, or its degree is at most $1+(t-1)^2$. Since $G_{mn}$ has elements with support of size $\min(m,n)$, and $mn > 1 + (\min(m,n)-1)^2$, we conclude that $A_{mn} \le G$.

share|improve this answer
    
Fabulous answer. Thank you. –  Will Nelson Jun 12 at 9:17

It is clear that this will not generally generate the set of all permutations. As an example, note that it is impossible to, within your constraints, put the matrix $$ \pmatrix{2&1&3\\4&5&6\\7&8&9} $$ in the correct order since all row and column permutations are of even parity (a similar trick will work for any matrix of odd dimensions). It remains to be seen whether, in this case and for general matrices of odd dimension, it is possible to generate the alternating group of permutations.

share|improve this answer
    
Yes, I agree. Good so far, thanks... –  Will Nelson Jun 12 at 5:27

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.