6
$\begingroup$

Q: Does every $9 \times 9$ Latin square on the symbol set $\{1,2,\ldots,9\}$ contain a $3 \times 3$ submatrix containing each symbol in $\{1,2,\ldots,9\}$?

This one has $1728$ such submatrices, which is as low as I've gotten: $$ \begin{bmatrix} 6 & 7 & 8 & 9 & 1 & 4 & 2 & 3 & 5 \\ 5 & 6 & 1 & 7 & 2 & 8 & 3 & 4 & 9 \\ 9 & 1 & 6 & 2 & 4 & 3 & 7 & 5 & 8 \\ 4 & 5 & 3 & 6 & 8 & 7 & 1 & 9 & 2 \\ 1 & 2 & 4 & 8 & 3 & 5 & 9 & 6 & 7 \\ 2 & 3 & 7 & 4 & 9 & 6 & 5 & 8 & 1 \\ 8 & 9 & 2 & 3 & 5 & 1 & 6 & 7 & 4 \\ 7 & 8 & 5 & 1 & 6 & 9 & 4 & 2 & 3 \\ 3 & 4 & 9 & 5 & 7 & 2 & 8 & 1 & 6 \\ \end{bmatrix}$$

It doesn't seem likely that random Latin squares will help much; they average in the thousands of such submatrices. The one above is the best random Latin square I've found so far (although, I haven't busted a gut doing this; it seems like it won't work anyway).

The groups of order $9$ have lots ($C_9$ has $5832$ and $C_3 \times C_3$ has $19440$).


This question was motivated by answering this math.SE question which asks if any $9 \times 9$ Latin square can have its rows and columns permuted to give a sudoku square.

One way to find an explicit counterexample would be to find a $9 \times 9$ Latin square with no $3 \times 3$ submatrix containing each symbol in $\{1,2,\ldots,9\}$. But this attempt didn't work since I couldn't find one. Hence my question.

$\endgroup$
7
$\begingroup$

How about this one?

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

I discovered it by modifying a Latin Square solver to add the restriction that no 3x3 submatrix can contain 9 different values. It found this in about 1 hour.

$\endgroup$
3
0
$\begingroup$

We might consider the general concept of a saturated sub-matrix, or $SSM$, being an $M \times K$ sub-matrix within a Latin square of of rank $N = M \times K$, that contains all $N$ values.

We are looking for Latin squares that are completely void of $SSM$s, so they might well be called poly-unsaturated!

For example $6 = 3 \times 2$. Of the 9408 reduced forms, just 6 are poly-unsaturated. Here is one of them:

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

The counter is still running for $9 = 3 \times 3$, but these are definitely scarce objects.

I have also confirmed existence for $8 = 4 \times 2$. One is tempted to conjecture that for all $M,K \gt 1$, whenever $M \neq N$ they will be found to exist.

For $M = K$, well we now know that $N=9$ has poly-unsaturated forms, and $N=4$ does not. I don't know enough about cyclic groups to predict the result for $N=16$.

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