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.

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|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
add comment

1 Answer

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|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: migo.sixbit.org/puzzles/fifteen –  user59671 Jan 30 '13 at 15:15
1  
I have mentioned 2 and 3 in the proof, thereby implicitly assuming $n > 1$. –  Andreas Caranti Jan 30 '13 at 15:59
add comment

Your Answer

 
discard

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