Definition 4.3.1 A Latin square of order $n$ is an $n\times n$ grid filled with $n$ symbols so that each symbol appears once in each row and column. $\square$
Example 4.3.2 Here is a Latin square of order 4:
| ♥ | ♣ | ♠ | ♦ |
| ♣ | ♠ | ♦ | ♥ |
| ♠ | ♦ | ♥ | ♣ |
| ♦ | ♥ | ♣ | ♠ |
Usually we use the integers $1\ldots n$ for the symbols. There are many, many Latin squares of order $n$, so it pays to limit the number by agreeing not to count Latin squares that are "really the same'' as different. The simplest way to do this is to consider reduced Latin squares. A reduced Latin square is one in which the first row is $1\ldots n$ (in order) and the first column is likewise $1\ldots n$.
Example 4.3.3 Consider this Latin square:
| 4 | 2 | 3 | 1 |
| 2 | 4 | 1 | 3 |
| 1 | 3 | 4 | 2 |
| 3 | 1 | 2 | 4 |
| 1 | 2 | 3 | 4 |
| 3 | 4 | 1 | 2 |
| 2 | 3 | 4 | 1 |
| 4 | 1 | 2 | 3 |
| 1 | 2 | 3 | 4 |
| 2 | 3 | 4 | 1 |
| 3 | 4 | 1 | 2 |
| 4 | 1 | 2 | 3 |
Another simple way to change the appearance of a Latin square without changing its essential structure is to interchange the symbols.
Example 4.3.4 Starting with the same Latin square as before:
| 4 | 2 | 3 | 1 |
| 2 | 4 | 1 | 3 |
| 1 | 3 | 4 | 2 |
| 3 | 1 | 2 | 4 |
| 1 | 2 | 3 | 4 |
| 2 | 1 | 4 | 3 |
| 4 | 3 | 1 | 2 |
| 3 | 4 | 2 | 1 |
| 1 | 2 | 3 | 4 |
| 2 | 1 | 4 | 3 |
| 3 | 4 | 2 | 1 |
| 4 | 3 | 1 | 2 |
Definition 4.3.5 Two Latin squares are isotopic if each can be turned into the other by permuting the rows, columns, and symbols. This isotopy relation is an equivalence relation; the equivalence classes are the isotopy classes. $\square$
Latin squares are apparently quite difficult to count without substantial computing power. According to Wikipedia, the number of Latin squares is known only up to $n=11$. Here are the first few values for all Latin squares, reduced Latin squares, and non-isotopic Latin squares (that is, the number of isotopy classes):
| $n$ | All | Reduced | Non-isotopic |
|---|---|---|---|
| 1 | 1 | 1 | 1 |
| 2 | 2 | 1 | 1 |
| 3 | 12 | 1 | 1 |
| 4 | 576 | 4 | 2 |
| 5 | 161280 | 56 | 2 |
How can we produce a Latin square? If you know what a group is, you should know that the multiplication table of any finite group is a Latin square. (Also, any Latin square is the multiplication table of a quasigroup.) Even if you have not encountered groups by that name, you may know of some. For example, considering the integers modulo $n$ under addition, the addition table is a Latin square.
Example 4.3.6 Here is the addition table for the integers modulo 6:
| 0 | 1 | 2 | 3 | 4 | 5 |
| 1 | 2 | 3 | 4 | 5 | 0 |
| 2 | 3 | 4 | 5 | 0 | 1 |
| 3 | 4 | 5 | 0 | 1 | 2 |
| 4 | 5 | 0 | 1 | 2 | 3 |
| 5 | 0 | 1 | 2 | 3 | 4 |
Example 4.3.7 Here is another way to potentially generate many Latin squares. Start with first row $1,\ldots, n$. Consider the sets $A_i=[n]\backslash\{i\}$. From exercise 1 in section 4.1 we know that this set system has many sdrs; if $x_1,x_2,\ldots,x_n$ is an sdr, we may use it for row two. In general, after we have chosen rows $1,\ldots,j$, we let $A_i$ be the set of integers that have not yet been chosen for column $i$. This set system has an sdr, which we use for row $j+1$. $\square$
Definition 4.3.8 Suppose $A$ and $B$ are two Latin squares of order $n$, with entries $A_{i,j}$ and $B_{i,j}$ in row $i$ and column $j$. Form the matrix $M$ with entries $M_{i,j}=(A_{i,j},B_{i,j})$; we will denote this operation as $M=A\cup B$. We say that $A$ and $B$ are orthogonal if $M$ contains all $n^2$ ordered pairs $(a,b)$, $1\le a\le n$, $1\le b\le n$, that is, all elements of $\{0,1,\ldots,n-1\}\times\{0,1,\ldots,n-1\}$. $\square$
As we will see, it is easy to find orthogonal Latin squares of order $n$ if $n$ is odd; not too hard to find orthogonal Latin squares of order $4k$, and difficult but possible to find orthogonal Latin squares of order $4k+2$, with the exception of orders $2$ and $6$. In the 1700s, Euler showed that there are orthogonal Latin squares of all orders except of order $4k+2$, and he conjectured that there are no orthogonal Latin squares of of order $6$. In 1901, the amateur mathematician Gaston Tarry showed that indeed there are none of order $6$, by showing that all possibilities for such Latin squares failed to be orthogonal. In 1959 it was finally shown that there are orthogonal Latin squares of all other orders.
Proof. This proof can be shortened by using ideas of group theory, but we will present a self-contained version. Consider the addition table for addition mod $n$:
| 0 | $\cdots$ | $j$ | $\cdots$ | $n-1$ | |
| 0 | 0 | $\cdots$ | $j$ | $\cdots$ | $n-1$ |
| $\vdots$ | |||||
| $i$ | $i$ | $\cdots$ | $i+j$ | $\cdots$ | $n+i-1$ |
| $\vdots$ | |||||
| $n-1$ | $n-1$ | $\cdots$ | $n+j-1$ | $\cdots$ | $n-2$ |
We claim first that this (without the first row and column, of course) is a Latin square with symbols $0,1,\ldots,n-1$. Consider two entries in row $i$, say $i+j$ and $i+k$. If $i+j\equiv i+j \pmod{n}$, then $j\equiv k$, so $j=k$. Thus, all entries of row $i$ are distinct, so each of $0,1,\ldots,n-1$ appears exactly once in row $i$. The proof that each appears once in any column is similar. Call this Latin square $A$. (Note that so far everything is true whether $n$ is odd or even.)
Now form a new square $B$ with entries $B_{i,j}=A_{2i,j}=2i+j$, where by $2i$ and $2i+j$ we mean those values mod $n$. Thus row $i$ of $B$ is the same as row $2i$ of $A$. Now we claim that in fact the rows of $B$ are exactly the rows of $A$, in a different order. To do this, it suffices to show that if $2i\equiv 2k\pmod{n}$, then $i=k$. This implies that all the rows of $B$ are distinct, and hence must be all the rows of $A$.
Suppose without loss of generality that $i\ge k$. If $2i\equiv 2k\pmod{n}$ then $n\divides 2(i-k)$. Since $n$ is odd, $n\divides (i-k)$. Since $i$ and $k$ are in $0,1,\ldots,n-1$, $0\le i-k\le n-1$. Of these values, only $0$ is divisible by $n$, so $i-k=0$. Thus $B$ is also a Latin square.
To show that $A\cup B$ contains all $n^2$ elements of $\{0,1,\ldots,n-1\}\times\{0,1,\ldots,n-1\}$, it suffices to show that no two elements of $A\cup B$ are the same. Suppose that $(i_1+j_1,2i_1+j_1)=(i_2+j_2,2i_2+j_2)$ (arithmetic is mod $n$). Then by subtracting equations, $i_1=i_2$; with the first equation this implies $j_1=j_2$. $\qed$
Example 4.3.10 When $n=3$, $$\left[\matrix{ 0&1&2\cr 1&2&0\cr 2&0&1\cr}\right]\cup \left[\matrix{ 0&1&2\cr 2&0&1\cr 1&2&0\cr}\right]= \left[\matrix{ (0,0)&(1,1)&(2,2)\cr (1,2)&(2,0)&(0,1)\cr (2,1)&(0,2)&(1,0)\cr}\right]. $$ $\square$
One obvious approach to constructing Latin squares, and pairs of orthogonal Latin squares, is to start with smaller Latin squares and use them to produce larger ones. We will produce a Latin square of order $mn$ from a Latin square of order $m$ and one of order $n$.
Let $A$ be a Latin square of order $m$ with symbols $1,\ldots,m$, and $B$ one of order $n$ with symbols $1,\ldots,n$. Let $c_{i,j}$, $1\le i\le m$, $1\le j\le n$, be $mn$ new symbols. Form an $mn\times mn$ grid by replacing each entry of $B$ with a copy of $A$. Then replace each entry $i$ in this copy of $A$ with $c_{i,j}$, where $j$ is the entry of $B$ that was replaced. We denote this new Latin square $A\times B$. Here is an example, combining a $4\times 4$ Latin square with a $3\times 3$ Latin square to form a $12\times 12$ Latin square: }
| $\times$ |
| $=$ |
|
Theorem 4.3.11 If $A$ and $B$ are Latin squares, so is $A\times B$.
Proof. Consider two symbols $c_{i,j}$ and $c_{k,l}$ in the same row. If the positions containing these symbols are in the same copy of $A$, then $i\not=k$, since $A$ is a Latin square, and so the symbols $c_{i,j}$ and $c_{k,l}$ are distinct. Otherwise, $j\not=l$, since $B$ is a Latin square. The argument is the same for columns. $\qed$
Remarkably, this operation preserves orthogonality:
Theorem 4.3.12 If $A_1$ and $A_2$ are Latin squares of order $m$, $B_1$ and $B_2$ are Latin squares of order $n$, $A_1$ and $A_2$ are orthogonal, and $B_1$ and $B_2$ are orthogonal, then $A_1\times B_1$ is orthogonal to $A_1\times B_2$.
Proof. We denote the contents of $A_i\times B_i$ by $C_i(w,x,y,z)$, meaning the entry in row $w$ and column $x$ of the copy of $A_i$ that replaced the entry in row $y$ and column $z$ of $B_i$, which we denote $B_i(y,z)$. We use $A_i(w,x)$ to denote the entry in row $w$ and column $x$ of $A_i$.
Suppose that $(C_1(w,x,y,z),C_2(w,x,y,z))=(C_1(w',x',y',z'),C_2(w',x',y',z'))$, where $(w,x,y,z)\not=(w',x',y',z')$. Either $(w,x)\not=(w',x')$ or $(y,z)\not=(y',z')$. If the latter, then $(B_1(y,z),B_2(y,z))= (B_1(y',z'),B_2(y',z'))$, a contradiction, since $B_1$ is orthogonal to $B_2$. Hence $(y,z)=(y',z')$ and $(w,x)\not=(w',x')$. But this implies that $(A_1(w,x),A_2(w,x))=(A_1(w',x'),A_2(w',x'))$, a contradiction. Hence $A_1\times B_1$ is orthogonal to $A_1\times B_2$. $\qed$
We want to construct orthogonal Latin squares of order $4k$. Write $4k=2^m\cdot n$, where $n$ is odd and $m\ge 2$. We know there are orthogonal Latin squares of order $n$, by theorem 4.3.9. If there are orthogonal Latin squares of order $2^m$, then by theorem 4.3.12 we can construct orthogonal Latin squares of order $4k=2^m\cdot n$.
To get a Latin square of order $2^m$, we also use theorem 4.3.12. It suffices to find two orthogonal Latin squares of order $4=2^2$ and two of order $8=2^3$. Then repeated application of theorem 4.3.12 allows us to build orthogonal Latin squares of order $2^m$, $m\ge 2$.
Two orthogonal Latin squares of order 4: $$\left[\matrix{ 1&2&3&4\cr 2&1&4&3\cr 3&4&1&2\cr 4&3&2&1\cr}\right] \left[\matrix{ 1&2&3&4\cr 3&4&1&2\cr 4&3&2&1\cr 2&1&4&3\cr }\right], $$ and two of order 8: $$ \left[\matrix{ 1&3&4&5&6&7&8&2\cr 5&2&7&1&8&4&6&3\cr 6&4&3&8&1&2&5&7\cr 7&8&5&4&2&1&3&6\cr 8&7&2&6&5&3&1&4\cr 2&5&8&3&7&6&4&1\cr 3&1&6&2&4&8&7&5\cr 4&6&1&7&3&5&2&8\cr }\right] \left[\matrix{ 1&4&5&6&7&8&2&3\cr 8&2&6&5&3&1&4&7\cr 2&8&3&7&6&4&1&5\cr 3&6&2&4&8&7&5&1\cr 4&1&7&3&5&2&8&6\cr 5&7&1&8&4&6&3&2\cr 6&3&8&1&2&5&7&4\cr 7&5&4&2&1&3&6&8\cr }\right]. $$
Exercises 4.3
Ex 4.3.1 Show that there is only one reduced Latin square of order 3.
Ex 4.3.2 Verify that the isotopy relation is an equivalence relation.
Ex 4.3.3 Find all 4 reduced Latin squares of order 4. Show that there are at most 2 isotopy classes for order 4.
Ex 4.3.4 Show that the second set system defined in example 4.3.7 has an sdr as claimed.
Ex 4.3.5 Show that there are no orthogonal Latin squares of order 2.
Ex 4.3.6 Find the two orthogonal Latin squares of order $5$ as described in theorem 4.3.9. Show your answer as in example 4.3.10.
Ex 4.3.7 Prove that to construct orthogonal Latin squares of order $2^m$, $m\ge2$, it suffices to find two orthogonal Latin squares of order $4=2^2$ and two of order $8=2^3$.
Ex 4.3.8 An $n\times n$ Latin square $A$ is symmetric if it is symmetric around the main diagonal, that is, $A_{i,j}=A_{j,i}$ for all $i$ and $j$. It is easy to find symmetric Latin squares: every addition table modulo $n$ is an example, as in example 4.3.6. A Latin square is idempotent if every symbol appears on the main diagonal. Show that if $A$ is both symmetric and idempotent, then $n$ is odd. Find a $5\times 5$ symmetric, idempotent Latin square.
Ex 4.3.9 The transpose $A^\top$ of a Latin square $A$ is the reflection of $A$ across the main diagonal, so that $A_{i,j}^\top=A_{j,i}$. A Latin square is self-orthogonal if $A$ is orthogonal to $A^\top$. Show that there is no self-orthogonal Latin square of order 3. Find one of order 4.