# Sorting numbers in a matrix by moving an empty entry through other entries is not always possible .

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

-
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

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 $$\text{(block distance of 1 from upper left corner)} + \text{(parity of underlying permutation of \mathbb{N}_{n^2})}.$$ 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.
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
I have mentioned 2 and 3 in the proof, thereby implicitly assuming $n > 1$. – Andreas Caranti Jan 30 '13 at 15:59