0
$\begingroup$

Consider Latin squares of even order that is not of form $2^x$, where every cell is involved in a $2\times 2$ sub square. Here is one such square for order 6:

          0 1 2 3 4 5
          1 0 3 4 5 2 
          2 4 0 5 1 3
          3 5 1 2 0 4
          4 2 5 1 3 0
          5 3 4 0 2 1

Notice that rows correspond to each other in pairings. Cells in the first row make sub squares with cells in the third row, cells in the second row make sub squares with cells in the fourth, and the fifth and sixth rows make sub squares with each other. These are not the only existent subsquares, but there is a definitive correspondence between pairs of rows for subsquares.

The question- what does a latin square of order 10 with all cells involved in a $2\times 2$ subsquare, and with rows presumably paired like in the order 6 square satisfying the same conditions, look like? And once we can see that square, is there any visible relationship between such squares of even but not power-of-two order and the group tables for $\mathbb{Z}/2^n$, which also satisfy the all-cells-involved-in-two-by-two-subsquares condition? Is there any generalizable pattern for this sort of square at all?

But I suppose my main question is with regards to finding $10\times 10, 12\times 12$ etc examples- especially $10\times 10$. I have not been able to find an example using the pairing rows method- maybe I am just being disorganized.

$\endgroup$
4
$\begingroup$

In the Cayley table of $\mathbb{Z}_n \times \mathbb{Z}_2$, every entry belongs to a $2 \times 2$ subsquare for all even orders -- this resolves the existence question. In fact, a much more general statement is true:

Lemma: If $G$ is a group and $H$ is a subgroup of $G$, then the Cayley table of $G$ partitions into $|H| \times |H|$ subsquares induced by the double-cosets of $H$.

So, for example, $S_4$ is a group of order $24$, and every entry in its Cayley table (a Latin square of order $24$) belongs to some $2 \times 2$ subsquare, some $3 \times 3$ subsquare, some $4 \times 4$ subsquare, and so on for the other subgroup sizes.

Non-group examples can be formed by a direct product construction. Take a Latin square of order $n$, and replace each entry by a $2 \times 2$ subsquare as indicated below:

1 2 3      1 2  3 4  5 6
2 3 1  ->  2 1  4 3  6 5
3 1 2      3 4  5 6  1 2
           4 3  6 5  2 1
           5 6  1 2  3 4
           6 5  2 1  4 3

and then we can "turn" the subsquares using the switching operation:

1 2  ->  2 1
2 1      1 2

As usual, we can permute the rows/columns/symbols arbitrarily and preserve this property (along with taking "matrix transpose" and "replacing each row by its inverse", and combinations of these).

For odd $n$, the question was resolved by:

  • P. Danziger and E. Mendelsohn, Intercalates everywhere, London Math. Soc. Lecture Note Ser. 245 (1997). [Thanks to Ian Wanless for pointing me to this paper.]

Hence, we have the following:

Theorem: For all $n \geq 1$ except $n \in \{1,3,5,7\}$ there is a Latin square of order $n$ in which each entry belongs to some $2 \times 2$ subsquare.

Going the other direction, i.e. finding a general description of Latin squares whose entries belong to $2 \times 2$ subsquares, I suspect, is more-or-less impossible. For small orders (orders $\leq 9$ or maybe $10$), it would be possible to exhaustively find a main class representative in each case -- I would expect this to be a particularly long calculation, and likely, not particularly satisfying.

It would also be possible to find related results using in the following (and their references):

  • B. D. McKay and I. M. Wanless, Most Latin Squares Have Many Subsquares, Journal of Combinatorial Theory, Series A 86, 323 347 (1999).

  • J. Browning, D. S. Stones and I. M. Wanless, Bounds on the number of autotopisms and subsquares of a Latin square, Combinatorica, to appear.

$\endgroup$
  • $\begingroup$ I happen to be working on a proof that it is not possible for odd order. $\endgroup$ – Xuan Huang Aug 3 '12 at 1:49
1
$\begingroup$

$$\matrix{0&1&2&3&4&5&6&7&8&9\cr1&0&3&2&5&4&7&6&9&8\cr2&3&4&5&6&7&8&9&0&1\cr3&2&5&4&7&6&9&8&1&0\cr4&5&6&7&8&9&0&1&2&3\cr5&4&7&6&9&8&1&0&3&2\cr6&7&8&9&0&1&2&3&4&5\cr7&6&9&8&1&0&3&2&5&4\cr8&9&0&1&2&3&4&5&6&7\cr9&8&1&0&3&2&5&4&7&6\cr}$$ 1st row paired with 2nd, 3rd with 4th, 5th with 6th, etc.

$\endgroup$
  • $\begingroup$ I feel like an idiot. Are any different Latin squares possible? $\endgroup$ – Xuan Huang Aug 3 '12 at 1:03
  • $\begingroup$ Perhaps more like the six by six I showed? $\endgroup$ – Xuan Huang Aug 3 '12 at 1:05
  • $\begingroup$ Or is my square just a row column permutation of your sort of circulant? $\endgroup$ – Xuan Huang Aug 3 '12 at 1:11

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.