36
$\begingroup$

I want to know if the popular Sudoku puzzle is a Cayley table for a group.

Methods I've looked at: Someone I've spoken to told me they're not because counting the number of puzzle solutions against the number of tables with certain permutations of elements, rows and columns, the solutions are bigger than the tables, but I can't see why because I don't know how to count the different tables for a group of order 9, and then permute the rows, columns and elements in different ways. Also I believe the rotations/reflections will matter in comparing these numbers too. It would also be nice if there was a way to know if the operation is associative just from the table.

$\endgroup$
  • 2
    $\begingroup$ Does a soduku have a unit element? $\endgroup$ – Mariano Suárez-Álvarez Aug 27 '16 at 16:27
  • 1
    $\begingroup$ Of course there is a way to tell from the table if the operation is associative: the table tells you everything there is to know about the multipliation. Of course, it is a somewhat laborious process! $\endgroup$ – Mariano Suárez-Álvarez Aug 27 '16 at 16:27
  • 2
    $\begingroup$ As you saying that any sudoku table has an identity element? $\endgroup$ – Mariano Suárez-Álvarez Aug 27 '16 at 16:32
  • 1
    $\begingroup$ @DanGlinski, I suggest you pick any example of a Sudoky puzzle and check if it does have an identity element or not. $\endgroup$ – Mariano Suárez-Álvarez Aug 27 '16 at 16:42
  • 1
    $\begingroup$ That is somewhat irrrelevant, really. If there is an identity element, for example, one of the columns has to be equal to the row symmetric to it. That rarely happens. $\endgroup$ – Mariano Suárez-Álvarez Aug 27 '16 at 16:51
34
$\begingroup$

A Cayley table for a group can never be a sudoku. Assume you have a $9 \times 9$ Cayley table for a group of order $9$, and say your identity element is at index $1 \le i \le 9$. Then row $i$ and column $i$ are symmetric to each other because they correspond to multiplication with the identity. In particular, if you look at the $3\times3$ sub-square containing the element of coordinates $(i,i)$, this square has duplicates (because it contains symmetric elements of row $i$ and column $i$). So the table isn't a Sudoku.

If you allow to swap the rows or columns, this is possible. Take the table of $G = \mathbb{Z}/9\mathbb{Z}$ (I wrote $0$ instead of $9$ for convenience): $$ \begin{array}{r|lllllllll} +&0&1&2&3&4&5&6&7&8\\ \hline 0&0&1&2&3&4&5&6&7&8\\ 1&1&2&3&4&5&6&7&8&0\\ 2&2&3&4&5&6&7&8&0&1\\ 3&3&4&5&6&7&8&0&1&2\\ 4&4&5&6&7&8&0&1&2&3\\ 5&5&6&7&8&0&1&2&3&4\\ 6&6&7&8&0&1&2&3&4&5\\ 7&7&8&0&1&2&3&4&5&6\\ 8&8&0&1&2&3&4&5&6&7\\ \end{array}$$

And swap the rows in order $0,3,6,1,4,7,2,5,8$, to obtain the Sudoku

$$ \begin{array}{r|lll|lll|lll} +&0&1&2&3&4&5&6&7&8\\ \hline 0&0&1&2&3&4&5&6&7&8\\ 3&3&4&5&6&7&8&0&1&2\\ 6&6&7&8&0&1&2&3&4&5\\ \hline 1&1&2&3&4&5&6&7&8&0\\ 4&4&5&6&7&8&0&1&2&3\\ 7&7&8&0&1&2&3&4&5&6\\ \hline 2&2&3&4&5&6&7&8&0&1\\ 5&5&6&7&8&0&1&2&3&4\\ 8&8&0&1&2&3&4&5&6&7\\ \end{array}$$

$\endgroup$
  • 17
    $\begingroup$ In fact, the failure is more dramatic: since every group of order 9 is abelian the whole multipication table is symmetric. $\endgroup$ – Mariano Suárez-Álvarez Aug 27 '16 at 17:36
  • 1
    $\begingroup$ But what if you allow swapping the rows and columns around? Wouldn't that destroy the symmetry in the table? $\endgroup$ – Dan Glinski Aug 27 '16 at 17:40
  • 2
    $\begingroup$ @DanGlinski, if you intend to permute rows and columns independently yes, but no one understood that in your question, as interpreting a table as a multiplication table sort of goes against that. $\endgroup$ – Mariano Suárez-Álvarez Aug 27 '16 at 17:57
  • $\begingroup$ I'm sorry I wasn't clear. What would you call the table? It does say what happens when you combine elements in the table, they're just not in any particular order. $\endgroup$ – Dan Glinski Aug 27 '16 at 18:31
10
$\begingroup$

Another approach: We are considering a group of order $9 = 3^2$ so a prime squared. It is well known that groups of order $p^2$ must be abelian. (abelian = commutative) Now a soduku can never represent an abelian group, as it is never symmetric. (Symmetric as in matrices, that means symmetric wrt. the diagonal.)

$\endgroup$
10
$\begingroup$

It is easy to construct a Sudoku that cannot be a Cayley table. Not even if you label the rows and columns independently from each other. Consider the following. $$ \begin{array}{ccc|ccc|ccc} 1&2&3&4&5&6&7&8&9\\ 4&5&6&7&8&9&1&3&2\\ 7&8&9&1&2&3&4&5&6\\ \hline 2&3&1&5&6&4&9&7&8\\ 5&6&4&8&9&7&2&1&3\\ 8&9&7&2&3&1&6&4&5\\ \hline 3&1&2&6&4&5&8&9&7\\ 6&4&5&9&7&8&3&2&1\\ 9&7&8&3&1&2&5&6&4 \end{array} $$ My argument only needs the two first rows. The rest were filled in just to leave no doubt about the fact that those two rows form a part of a complete Sudoku.

We see that we get the second row from the first by applying the permutation $\sigma=(147)(258369)$ to it. This is all we need to prove that this is not a Cayley table. If in a Cayley table the first row has $a$ as the common left factor and the second row has $b$ as the common left factor, we get the second row from the first by multiplying everything from the left by $c:=ba^{-1}$. If $n=\operatorname{ord}(c)$ then the permutation $\sigma$ bringing the first row to the second will then only have cycles of length $n$ as the cycles act transitively on right cosets $Hx$, $H=\langle c\rangle, x\in G$.

But our $\sigma$ has cycle type $(3,6)$. This already gives two obvious contradictions:

  • the lengths of the cycles vary, and
  • $\sigma$ has order six, so cannot be an element of a group of order nine.
$\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.