Graeco-Latin square
From Wikipedia, the free encyclopedia
A Graeco-Latin square or Euler square of order n over two sets S and T, each consisting of n symbols, is an n×n arrangement of cells, each cell containing an ordered pair (s,t), where s ∈ S and a t ∈ T, such that
- every row and every column contains exactly one s ∈ S and exactly one t ∈ T, and
- no two cells contain the same ordered pair of symbols.
The two sets are commonly taken to be S = {A, B, C, …}, the first n upper-case letters from the Latin alphabet, and T = {α , β, γ, …}, the first n lower-case letters from the Greek alphabet—hence the name Graeco-Latin square. Several examples are given below.
 |
 |
 |
| Order 3 | Order 4 | Order 5 |
The arrangement of the Latin characters alone and of the Greek characters alone each forms a Latin square. A Graeco-Latin square can therefore be decomposed into two orthogonal Latin squares. Orthogonality here means that every pair (s, t) from the Cartesian product S×T occurs exactly once.
Graeco-Latin squares have applications in the design of experiments, and can be used in the construction of magic squares.
[edit] History
In the 1780s, Leonhard Euler demonstrated methods for constructing Graeco-Latin squares where n is odd or a multiple of 4. Observing that no order-2 square exists and unable to construct an order-6 square (see thirty-six officers problem), he conjectured that none exist when n ≡ 2 (mod 4). Indeed, the non-existence of order-6 squares was definitely confirmed in 1901 by Gaston Tarry through exhaustive enumeration of all possible arrangements of symbols. In 1959, Bose and Shrikhande found some counterexamples to Euler's conjecture, then Parker found a counterexample of order 10. In 1960, Parker, Raj Chandra Bose and Shrikhande showed Euler's conjecture to be false for all n ≥ 10. Thus, Graeco-Latin squares exist for all orders n ≥ 3 except n = 6.
The French writer Georges Perec used the 10×10 square for the structure of constraints underlying his 1978 novel Life: A User's Manual.
