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

#### Solutions Collecting From Web of "Sorting numbers in a matrix by moving an empty entry through other entries is not always possible ."

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.