4.4: Latin Squares
( \newcommand{\kernel}{\mathrm{null}\,}\)
A Latin square of order n is an n×n grid filled with n symbols so that each symbol appears once in each row and column.
Here is a Latin square of order 4:
♥ | ♣ | ♠ | ♦ |
♣ | ♠ | ♦ | ♥ |
♠ | ♦ | ♥ | ♣ |
♦ | ♥ | ♣ | ♠ |
Usually we use the integers 1…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…n (in order) and the first column is likewise 1…n.
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.
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.
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.
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 |
Here is another way to potentially generate many Latin squares. Start with first row 1,…,n. Consider the sets Ai=[n]∖{i}. From Exercise 4.E.1.1 in Section 4.E we know that this set system has many sdrs; if x1,x2,…,xn is an sdr, we may use it for row two. In general, after we have chosen rows 1,…,j, we let Ai 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.
Suppose A and B are two Latin squares of order n, with entries Ai,j and Bi,j in row i and column j. Form the matrix M with entries Mi,j=(Ai,j,Bi,j); we will denote this operation as M=A∪B. We say that A and B are orthogonal if M contains all n2 ordered pairs (a,b), 1≤a≤n, 1≤b≤n, that is, all elements of {0,1,…,n−1}×{0,1,…,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.
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 ⋯ j ⋯ n−1 0 0 ⋯ j ⋯ n−1 ⋮ i i ⋯ i+j ⋯ n+i−1 ⋮ n−1 n−1 ⋯ n+j−1 ⋯ n−2 We claim first that this (without the first row and column, of course) is a Latin square with symbols 0,1,…,n−1. Consider two entries in row i, say i+j and i+k. If i+j≡i+j(modn), then j≡k, so j=k. Thus, all entries of row i are distinct, so each of 0,1,…,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 Bi,j=A2i,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≡2k(modn), 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≥k. If 2i≡2k(modn) then n|2(i−k). Since n is odd, n|(i−k). Since i and k are in 0,1,…,n−1, 0≤i−k≤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∪B contains all n2 elements of {0,1,…,n−1}×{0,1,…,n−1}, it suffices to show that no two elements of A∪B are the same. Suppose that (i1+j1,2i1+j1)=(i2+j2,2i2+j2) (arithmetic is mod n). Then by subtracting equations, i1=i2; with the first equation this implies j1=j2.
When n=3,
[012120201]∪[012201120]=[(0,0)(1,1)(2,2)(1,2)(2,0)(0,1)(2,1)(0,2)(1,0)].
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,…,m, and B one of order n with symbols 1,…,n. Let ci,j, 1≤i≤m, 1≤j≤n, be mn new symbols. Form an mn×mn grid by replacing each entry of B with a copy of A. Then replace each entry i in this copy of A with ci,j, where j is the entry of B that was replaced. We denote this new Latin square A×B. Here is an example, combining a 4×4 Latin square with a 3×3 Latin square to form a 12×12 Latin square: }
1234234134124123×123231312=c1,1c2,1c3,1c4,1c1,2c2,2c3,2c4,2c1,3c2,3c3,3c4,3c2,1c3,1c4,1c1,1c2,2c3,2c4,2c1,2c2,3c3,3c4,3c1,3c3,1c4,1c1,1c2,1c3,2c4,2c1,2c2,2c3,3c4,3c1,3c2,3c4,1c1,1c2,1c3,1c4,2c1,2c2,2c3,2c4,3c1,3c2,3c3,3c1,2c2,2c3,2c4,2c1,3c2,3c3,3c4,3c1,1c2,1c3,1c4,1c2,2c3,2c4,2c1,2c2,3c3,3c4,3c1,3c2,1c3,1c4,1c1,1c3,2c4,2c1,2c2,2c3,3c4,3c1,3c2,3c3,1c4,1c1,1c2,1c4,2c1,2c2,2c3,2c4,3c1,3c2,3c3,3c4,1c1,1c2,1c3,1c1,3c2,3c3,3c4,3c1,1c2,1c3,1c4,1c1,2c2,2c3,2c4,2c2,3c3,3c4,3c1,3c2,1c3,1c4,1c1,1c2,2c3,2c4,2c1,2c3,3c4,3c1,3c2,3c3,1c4,1c1,1c2,1c3,2c4,2c1,2c2,2c4,3c1,3c2,3c3,3c4,1c1,1c2,1c3,1c4,2c1,2c2,2c3,2
If A and B are Latin squares, so is A×B.
- Proof
-
Consider two symbols ci,j and ck,l in the same row. If the positions containing these symbols are in the same copy of A, then i≠k, since A is a Latin square, and so the symbols ci,j and ck,l are distinct. Otherwise, j≠l, since B is a Latin square. The argument is the same for columns.
Remarkably, this operation preserves orthogonality:
If A1 and A2 are Latin squares of order m, B1 and B2 are Latin squares of order n, A1 and A2 are orthogonal, and B1 and B2 are orthogonal, then A1×B1 is orthogonal to A1×B2.
- Proof
-
We denote the contents of Ai×Bi by Ci(w,x,y,z), meaning the entry in row w and column x of the copy of Ai that replaced the entry in row y and column z of Bi, which we denote Bi(y,z). We use Ai(w,x) to denote the entry in row w and column x of Ai.
Suppose that (C1(w,x,y,z),C2(w,x,y,z))=(C1(w′,x′,y′,z′),C2(w′,x′,y′,z′)), where (w,x,y,z)≠(w′,x′,y′,z′). Either (w,x)≠(w′,x′) or (y,z)≠(y′,z′). If the latter, then (B1(y,z),B2(y,z))=(B1(y′,z′),B2(y′,z′)), a contradiction, since B1 is orthogonal to B2. Hence (y,z)=(y′,z′) and (w,x)≠(w′,x′). But this implies that (A1(w,x),A2(w,x))=(A1(w′,x′),A2(w′,x′)), a contradiction. Hence A1×B1 is orthogonal to A1×B2.
We want to construct orthogonal Latin squares of order 4k. Write 4k=2m⋅n, where n is odd and m≥2. We know there are orthogonal Latin squares of order n, by Theorem 4.4.1. If there are orthogonal Latin squares of order 2m, then by Theorem 4.4.3 we can construct orthogonal Latin squares of order 4k=2m⋅n.
To get a Latin square of order 2m, we also use Theorem 4.4.3. It suffices to find two orthogonal Latin squares of order 4=22 and two of order 8=23. Then repeated application of Theorem 4.4.3 allows us to build orthogonal Latin squares of order 2m, m≥2.
Two orthogonal Latin squares of order 4:
[1234214334124321][1234341243212143],
and two of order 8:
[1345678252718463643812577854213687265314258376413162487546173528][1456782382653147283764153624875141735286571846326381257475421368].