6.2 Graeco-Latin squares
Definition 6.2.1. Two Latin squares of the same order are orthogonal if, when one is superimposed on the other, each of the \(p^2\) ordered pairs of symbols occurs exactly once. The superimposed pair, with the second square written in Greek letters, is a Graeco-Latin square.
For \(p = 4\), for example,
| \(A\alpha \) | \(B\beta \) | \(C\gamma \) | \(D\delta \) |
| \(B\delta \) | \(A\gamma \) | \(D\beta \) | \(C\alpha \) |
| \(C\beta \) | \(D\alpha \) | \(A\delta \) | \(B\gamma \) |
| \(D\gamma \) | \(C\delta \) | \(B\alpha \) | \(A\beta \) |
Each Latin letter appears once with each Greek letter. A design based on a Graeco-Latin square accommodates three nuisance factors (rows, columns and Greek letters) and one treatment factor (Latin letters), each at \(p\) levels, in \(p^2\) runs. The analysis adds a Greek-letter sum of squares to the Latin square table, and the error degrees of freedom fall to \((p - 1)(p - 3)\), so the design is useful only for \(p \ge 4\), and better for \(p \ge 5\).
Theorem 6.2.2. Let \(p\) be prime and, for \(k = 1, \dots , p - 1\), let \(L_k\) be the \(p \times p\) array with entry \[ L_k(i, j) = ki + j \pmod p , \qquad i, j = 0, 1, \dots , p - 1 . \] Each \(L_k\) is a Latin square, and any two of them are orthogonal. There are therefore \(p - 1\) mutually orthogonal Latin squares of order \(p\).
Proof. In row \(i\), the map \(j \mapsto ki + j\) is a bijection of \(\{0, \dots , p - 1\}\), so each symbol occurs once. In column \(j\), the map \(i \mapsto ki + j\) is a bijection because \(k\) has an inverse modulo the prime \(p\). For orthogonality of \(L_k\) and \(L_m\) with \(k \ne m\), suppose the pair of symbols \((a, b)\) occurs in cell \((i, j)\): \(ki + j \equiv a\) and \(mi + j \equiv b\). Subtracting, \((k - m)i \equiv a - b\), which determines \(i\) uniquely since \(k - m\) is invertible, and then \(j \equiv a - ki\). So each pair occurs in exactly one cell. □
The same construction works for any prime power, using the arithmetic of the finite field of that order. For \(p = 6\) no pair of orthogonal Latin squares exists, a fact conjectured by Euler and proved by Tarry in 1900. Euler conjectured more generally that none exists when \(p \equiv 2 \pmod 4\), but Bose, Shrikhande and Parker showed in 1959 that \(6\) is the only exception beyond \(2\).
Questions on this section
Stuck on something here? Ask below and it stays attached to this topic.