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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.