12
$\begingroup$

There is a $3\times3$ matrix filled by numbers 1~9 that might look like this

$$\begin{bmatrix}3 & 8 & 2 \\ 4 & 1 & 6 \\ 7 & 5 & 9\end{bmatrix}$$

All its rows and columns can be "rolled forwards and backwards" (like permutation acting on a single row/column)

Roll the second column upwards:

$$\begin{bmatrix}3 & 1 & 2 \\ 4 & 5 & 6 \\ 7 & 8 & 9\end{bmatrix}$$

And roll the first row to the left, we get

$$A=\begin{bmatrix}1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 9\end{bmatrix}$$

Now, if given an arbitrary matrix like this, how can I tell if it can be restored back to $A$? If it always could, why?

$\endgroup$
2
  • $\begingroup$ Just from attempting to solve from any position, I conjecture that half of positions are solvable and the other half will have the wrong parity on the last row/column solved. $\endgroup$
    – rschwieb
    Apr 11, 2014 at 15:58
  • $\begingroup$ And I didn't notice any trick faster than simply solving it (which can be done pretty rapidly) to determine "at first glance" if the solution was possible. $\endgroup$
    – rschwieb
    Apr 11, 2014 at 16:15

1 Answer 1

11
$\begingroup$

If we start with a matrix

$$\begin{bmatrix}a & b & c \\ d & e & f \\ g & h & i\end{bmatrix}$$

then the map $1 \mapsto a$, $2 \mapsto b$, etc, defines a permutation $\sigma$ of $\{1, 2, ..., 9\}$, i.e. an element of $S_9$. The valid "moves" consist of composing this permutation with one of the elements $(123), (456), (789), (147), (258), (369)$ or their inverses.

So the question becomes: what is the subgroup $G$ of $S_9$ generated by $\{(123), (456), (789), (147), (258), (369)\}$? For starters, these are all even permutations, so we're in fact looking for a subgroup of $A_9$.

Next we notice that we can get from $A$ to

$$\begin{bmatrix}2 & 3 & 1 \\ 5 & 6 & 4 \\ 8 & 9 & 7\end{bmatrix}$$

and then to

$$\begin{bmatrix}2 & 3 & 4 \\ 5 & 6 & 7 \\ 8 & 9 & 1\end{bmatrix}$$

so $(123456789) \in G$. And $(123456789)$ and $(123)$ together generate $A_9$, so $G = A_9$.

So the answer to the first question: you can get from a matrix to $A$ if and only if the permutation $\sigma$ defined above is an even permutation.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .