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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

let $\mathbf{A}$ be the set of all $n\times n$ matrices on $\mathbb{N}_{n^2}=\{1,2,...,n^2\}$ with distinct entries.

let $T$ be the set of all permutations of $\mathbf{A}$ which swap the entry 1 with one of its adjacent entries. adjacent means one is above/below/right/left of the other (and both are neighbors).

Let $S$ be the permutation subgroup generated by $T$.

Show that $S$ acts intransitively on $\mathbf{A}$.

I'm a.s. it's correct for even $n$.

share|cite|improve this question
You mean each matrix has distinct entries, that is, all number from 1 to $n^2$ appear in each matrix? Or are repetitions allowed? – Andreas Caranti Jan 30 '13 at 11:55
up vote 2 down vote accepted

This appears to be a generalization of the famous 15-puzzle. The proof that it is not transitive is the same. To each matrix, associate the number given by \begin{equation} \text{(block distance of 1 from upper left corner)} + \text{(parity of underlying permutation of $\mathbb{N}_{n^2}$)}. \end{equation} The parity of this number is an invariant under the allowed moves, that is, it does not change when you make a swap. So if you start with the numbers neatly ordered row by row, you will never get the matrix with 2 and 3 exchanged.

share|cite|improve this answer
@CutieKrait thanks! – Andreas Caranti Jan 30 '13 at 12:26
It seems that really the full permutation group generated is only the symmetric group $S_3$ on the three entries at upper left, to the right of that, and below it. – coffeemath Jan 30 '13 at 13:28
how about even $n$? for odd $n$ it may be transitive at least for $n=1$ it is. – user59671 Jan 30 '13 at 15:09
see this: – user59671 Jan 30 '13 at 15:15
I have mentioned 2 and 3 in the proof, thereby implicitly assuming $n > 1$. – Andreas Caranti Jan 30 '13 at 15:59

Your Answer


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