4.3: Latin Squares
- Page ID
- 7162
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)
Definition: Latin square
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.
Example \(\PageIndex{1}\)
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 \(\PageIndex{2}\)
Consider this Latin square:
| 4 | 2 | 3 | 1 |
| 2 | 4 | 1 | 3 |
| 1 | 3 | 4 | 2 |
| 3 | 1 | 2 | 4 |
The order of the rows and columns is not really important to the idea of a Latin square. If we reorder the rows and columns, we can consider the result to be in essence the same Latin square. By reordering the columns, we can turn the square above into this:
| 1 | 2 | 3 | 4 |
| 3 | 4 | 1 | 2 |
| 2 | 3 | 4 | 1 |
| 4 | 1 | 2 | 3 |
Then we can swap rows two and three:
| 1 | 2 | 3 | 4 |
| 2 | 3 | 4 | 1 |
| 3 | 4 | 1 | 2 |
| 4 | 1 | 2 | 3 |
This Latin square is in reduced form, and is essentially the same as the original.
Another simple way to change the appearance of a Latin square without changing its essential structure is to interchange the symbols.
Example \(\PageIndex{3}\)
Starting with the same Latin square as before:
| 4 | 2 | 3 | 1 |
| 2 | 4 | 1 | 3 |
| 1 | 3 | 4 | 2 |
| 3 | 1 | 2 | 4 |
we can interchange the symbols 1 and 4 to get:
| 1 | 2 | 3 | 4 |
| 2 | 1 | 4 | 3 |
| 4 | 3 | 1 | 2 |
| 3 | 4 | 2 | 1 |
Now if we swap rows three and four we get:
| 1 | 2 | 3 | 4 |
| 2 | 1 | 4 | 3 |
| 3 | 4 | 2 | 1 |
| 4 | 3 | 1 | 2 |
Notice that this Latin square is in reduced form, but it is not the same as the reduced form from the previous example, even though we started with the same Latin square. Thus, we may want to consider some reduced Latin squares to be the same as each other.
Definition: isotopic and Isotopy Classes
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.
Latin squares are apparently quite difficult to count without substantial computing power. 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 \(\PageIndex{4}\)
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\).
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\}\).
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.
Theorem 4.3.9
There are pairs of orthogonal Latin squares of order \(n\) when \(n\) is odd.
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\).
\(\square\)
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]. $$
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
f \(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.
\(\square\)
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\).
\(\square\)
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]. $$