2
$\begingroup$

Consider a Latin square puzzle played not necessarily in a $10\times 10$ grid, but in some $n\times n$ grid of the following form:

         1 2 3 ... n          2 1          3   1          .    .          .     .          .      .          n         1 

such that all cells in the first row are participating in a "subsquare"- ie an arrangement where the digits in $(p,q)$ and $(a,b)$ contain the same digit, and $(p,b) and (a,q)$ contain the same digit. In this construction the $1$ in the top left corner participates in all the $2 \times 2$ subsquares in specific question. For $n=4$, here is one such arrangement:

     1 2 3 4      2 1 4 3      3 4 1 2      4 3 2 1 

For $n=5$ here is one such square:

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

For $n=6$ here is one such arrangement:

     1 2 3 4 5 6      2 1 4 3 6 5      3 5 1 6 4 2      4 6 5 1 2 3      5 3 6 2 1 4      6 4 2 5 3 1 

For $n=7$ here is one such arrangement:

      1 2 3 4 5 6 7       2 1 4 5 6 7 3       3 7 1 2 4 5 6       4 6 7 1 2 3 5       5 3 6 7 1 2 4       6 4 5 3 7 1 2       7 5 2 6 3 4 1 

For $n=8$ here is one such arrangement:

       1 2 3 4 5 6 7 8        2 1 4 3 6 5 8 7        3 7 1 8 4 2 5 6        4 8 7 1 2 3 6 5        5 6 8 2 1 7 3 4        6 5 2 7 8 1 4 3        7 2 5 6 3 8 1 2        8 4 6 5 7 4 2 1 

For $n=9$ here is one such arrangement:

      1 2 3 4 5 6 7 8 9       2 1 4 8 6 5 3 9 7       3 7 1 2 4 8 9 5 6       4 6 7 1 9 2 8 3 5       5 9 8 6 1 3 2 7 1       6 4 9 3 7 1 5 2 8       7 8 5 9 2 4 1 6 3       8 5 6 7 3 9 4 1 2       9 3 2 5 8 7 6 4 1 
  • 0
    But for us those subsquares are irrelevant.2012-07-26

2 Answers 2

2

I don't understand the question. If all you want is a Latin square with all entries on the upper-left to lower-right diagonal equal, a construction is given in Section 3 of A J W Hilton, On double diagonal and cross latin squares, J London Math Soc 6 (1973) 679-689, which is on the web here. In fact, Hilton does much more: if $n$ is even, he gets the upper-right to lower-left diagonal to be constant as well, and if $n$ is odd, he gets that other diagonal to be constant with two exceptions.

EDIT: Here's an explicit construction for the case $n$ even. Find a 1-factorization of $K_n$. If $(a,b),(c,d),\dots,(m,n)$ is one of the 1-factors, then put the same symbol into the squares $(a,b),(c,d),\dots,(m,n)$ and also the squares $(b,a),(d,c),\dots,(n,m)$ (since after all as an edge in $K_n$, $(a,b)$ is the same as $(b,a)$. That leaves the diagonal free for the remaining symbol.

For example, let's do $n=6$. A 1-factorization is given by 12, 36, 45; 13, 24, 56; 14, 26, 35; 15, 23, 46; 16, 25, 34. (A 1-factor is just a list of edges that uses each vertex exactly once; a 1-factorization is a list of 1-factors that includes every edge in the graph exactly once; there is a simple construction that finds a 1-factorization of $K_n$ for $n$ even). So I'll put 2 at locations $(1,2),(3,6),(4,5)$ and $(2,1),(6,3),(5,4)$; I'll put 3 at $(1,3),(2,4),(5,6)$ and $(3,1),(4,2),(6,5)$; and so on; then finish it off with 1 down the diagonal.

  • 0
    Danielle, you're doing advanced mathematics; you're expected to be able to put some of these things together on your own, or, at the very least, to be able to ask a more focussed question than asking for "an explanation of a 1-factorization in relation to $K_n$". Please read through the definition I gave and the example I gave, and try to work through them, and if you get stuck someplace, indicate exactly how far you got and exactly what it is that's unclear. I'm happy to try to answer focussed questions, but I'm not going to write a textbook on graph theory.2012-07-26
0

The adjectives to describe these Latin squares are: reduced (meaning the first row and column are in order) and unipotent (meaning the main diagonal is fixed).

We will show that reduced unipotent Latin squares of order $n$ are equivalent to Latin squares of order $n-1$ that admit a special type of "transversal" along the main diagonal. A transversal of a Latin square is a collection of $n$ symbols containing one entry from each row, each column and each possible symbol.

Through a process, known as prolongation, from a Latin square of order $n$ with main diagonal $1,2,\ldots,n$ we can generate a Latin square of order $n+1$ with a transversal along the main diagonal. We delete the main diagonal, replace it with a new fixed symbol, after which there is a unique completion to $(n+1) \times (n+1)$ Latin square. This equivalence is illustrated (in reverse) below:

  1 2 3 4 5       . . . . .   2 1 4 5 3       . 1 4 5 3       2 4 5 3   3 5 1 2 4  <->  . 5 1 2 4  <->  5 3 2 4   4 3 5 1 2       . 3 5 1 2       3 5 4 2   5 4 2 3 1       . 4 2 3 1       4 2 3 5 

(We can relabel the symbols as desired.) Moreover, and importantly, this process is reversible.

Given any Latin square with a transversal, we can permute the rows and symbols to construct a Latin square with $1,2,\ldots,n$ along the main diagonal. Hence, we have the following.

Theorem: A reduced unipotent Latin square of order $n$ exists if and only if there exists a Latin square of order $n-1$ with a transversal.

Thus, the asked question is exactly equivalent to:

Question: For which orders $n$, does there exist a Latin square of order $n-1$ that has a transversal?

There's probably a zillion ways to answer the above question. One way I find particularly quick, is to note that orthogonal Latin squares exist for all orders except $2$ and $6$. Any fixed symbol in one Latin square corresponds to a transversal in any orthogonal mate. We can use the OP's example for order $7$ to find a Latin square with a transversal of order $6$. There is only one Latin square of order $2$ (up to row/column/symbol permutations), and it doesn't have a transversal (which is why you didn't find a reduced unipotent Latin square of order $3$).

Hence, we have the following theorems.

Theorem: There exists a Latin square of order $n$ with a transversal for all orders $n \geq 1$ except $n=2$.

Theorem: There exists a reduced unipotent Latin square of order $n$ for all orders $n \geq 1$ except $n=3$.

A(nother) proof was given by McKay, McLeod, Wanless for $n \geq 5$ (among many other relevant results). We will give a constructive proof below:

Proof: If two Latin squares (of orders $n$ and $m$) have transversals along the main diagonal, then so does their direct product (which will have order $nm$).

For odd $n$, the Cayley table of $\mathbb{Z}_n$ has a transversal along the main diagonal. Examples of orders $2^2$ and $2^3$ are given by the OP. Combining these results, we can construct a Latin square of order $n$ with a transversal whenever $n \not\equiv 2 \pmod 4$.

Next, we will complete the proof by finding a transversal in a Latin square of order $2n$ for odd $n$ formed from switches in the Cayley table of $\mathbb{Z}_2 \times \mathbb{Z}_n$ for odd $n$. (Note that the Cayley table of $\mathbb{Z}_2 \times \mathbb{Z}_n \cong \mathbb{Z}_{2n}$ does not have transversals, so some switching is necessary.)

This will be largely a "proof by example", since it would be considerable effort to cross all the t's and dot all the lowercase j's.

Step 1: Using two transversals in the Cayley table of $\mathbb{Z}_n$, we generate a selection of $2n$ entries in the Cayley table of $\mathbb{Z}_2 \times \mathbb{Z}_n$ as follows:

$ \begin{array}{c} \begin{array}{|ccccc|} \hline \mathbf{\large 1} & 2 & 3 & 4 & 5 \\ 2 & 3 & \mathbf{\large 4} & 5 & 1 \\ 3 & 4 & 5 & 1 & \mathbf{\large 2} \\ 4 & \mathbf{\large 5} & 1 & 2 & 3 \\ 5 & 1 & 2 & \mathbf{\large 3} & 4 \\ \hline \end{array} \\ \begin{array}{|ccccc|} \hline 1 & \mathbf{\large 2} & 3 & 4 & 5 \\ 2 & 3 & 4 & \mathbf{\large 5} & 1 \\ \mathbf{\large 3} & 4 & 5 & 1 & 2 \\ 4 & 5 & \mathbf{\large 1} & 2 & 3 \\ 5 & 1 & 2 & 3 & \mathbf{\large 4} \\ \hline \end{array} \end{array} \rightarrow\begin{array}{|ccccc|ccccc|} \hline \mathbf{\large 1} & 2 & 3 & 4 & 5 & 1' & 2' & 3' & 4' & 5' \\ 2 & 3 & \mathbf{\large 4} & 5 & 1 & 2' & 3' & 4' & 5' & 1' \\ 3 & 4 & 5 & 1 & \mathbf{\large 2} & 3' & 4' & 5' & 1' & 2' \\ 4 & 5 & 1 & 2 & 3 & 4' & \mathbf{\large 5'} & 1' & 2' & 3' \\ 5 & 1 & 2 & 3 & 4 & 5' & 1' & 2' & \mathbf{\large 3'} & 4' \\ \hline 1' & \mathbf{\large 2'} & 3' & 4' & 5' & 1 & 2 & 3 & 4 & 5 \\ 2' & 3' & 4' & \mathbf{\large 5'} & 1' & 2 & 3 & 4 & 5 & 1 \\ 3' & 4' & 5' & 1' & 2' & \mathbf{\large 3} & 4 & 5 & 1 & 2 \\ 4' & 5' & 1' & 2' & 3' & 4 & 5 & \mathbf{\large 1} & 2 & 3 \\ 5' & 1' & 2' & 3' & 4' & 5 & 1 & 2 & 3 & \mathbf{\large 4} \\ \hline \end{array}. $

This gives a $2p \times 2p$ Latin square with a selection of $2p$ entries with one representative from each row and column, but more than one copy of some symbols. But, importantly, exactly two symbol representatives from each set $\{i,i'\}$, which is why the next step works.

Step 2: We then "break" the symbol repeats by performing intercalate switches in the Latin square as follows:

$ \rightarrow \begin{array}{|ccccc|ccccc|} \hline \mathbf{\large 1'} & 2 & 3 & 4 & 5 & 1 & 2' & 3' & 4' & 5' \\ 2 & 3 & \mathbf{\large 4} & 5 & 1 & 2' & 3' & 4' & 5' & 1' \\ 3 & 4 & 5 & 1 & \mathbf{\large 2} & 3' & 4' & 5' & 1' & 2' \\ 4 & 5 & 1 & 2 & 3 & 4' & \mathbf{\large 5'} & 1' & 2' & 3' \\ 5 & 1 & 2 & 3 & 4 & 5' & 1' & 2' & \mathbf{\large 3'} & 4' \\ \hline 1 & \mathbf{\large 2'} & 3' & 4' & 5' & 1' & 2 & 3 & 4 & 5 \\ 2' & 3' & 4' & \mathbf{\large 5'} & 1' & 2 & 3 & 4 & 5 & 1 \\ 3' & 4' & 5' & 1' & 2' & \mathbf{\large 3} & 4 & 5 & 1 & 2 \\ 4' & 5' & 1' & 2' & 3' & 4 & 5 & \mathbf{\large 1} & 2 & 3 \\ 5' & 1' & 2' & 3' & 4' & 5 & 1 & 2 & 3 & \mathbf{\large 4} \\ \hline \end{array}. $

In the above example, we switched

1  1'  ->  1' 1 1' 1       1  1' 

in rows $1$ and $6$ and columns $1$ and $6$. We keep switching until we run out of symbol repeats. Importantly, we perform switches in which (a) symbols $i$ are switched with $i'$, and (b) exactly one cell in the $2n$ entries is affected.

$ \rightarrow \begin{array}{|ccccc|ccccc|} \hline \mathbf{\large 1'} & 2 & 3 & 4 & 5 & 1 & 2' & 3' & 4' & 5' \\ 2 & 3 & \mathbf{\large 4'} & 5 & 1 & 2' & 3' & 4 & 5' & 1' \\ 3 & 4 & 5 & 1 & \mathbf{\large 2} & 3' & 4' & 5' & 1' & 2' \\ 4 & 5' & 1 & 2 & 3 & 4' & \mathbf{\large 5} & 1' & 2' & 3' \\ 5 & 1 & 2 & 3 & 4 & 5' & 1' & 2' & \mathbf{\large 3'} & 4' \\ \hline 1 & \mathbf{\large 2'} & 3' & 4' & 5' & 1' & 2 & 3 & 4 & 5 \\ 2' & 3' & 4 & \mathbf{\large 5'} & 1' & 2 & 3 & 4' & 5 & 1 \\ 3' & 4' & 5' & 1' & 2' & \mathbf{\large 3} & 4 & 5 & 1 & 2 \\ 4' & 5 & 1' & 2' & 3' & 4 & 5' & \mathbf{\large 1} & 2 & 3 \\ 5' & 1' & 2' & 3' & 4' & 5 & 1 & 2 & 3 & \mathbf{\large 4} \\ \hline \end{array} $

Step 3: Permute the rows of the Latin square so that a transversal appears on the main diagonal.

Step 4: Prolong the Latin square, then permute the symbols to taste. End proof.