Graeco-Latin square
|
|
A Graeco-Latin 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.
| Missing image GraecoLatinSquare-Order3.png Image:GraecoLatinSquare-Order3.png |
Missing image GraecoLatinSquare-Order4.png Image:GraecoLatinSquare-Order4.png |
Missing image GraecoLatinSquare-Order5.png Image:GraecoLatinSquare-Order5.png |
| 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 multiplicative magic squares.
History
In the 1780s, Leonard 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, 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, 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.
See also
External links
- Java Tool for Constructing Orthogonal Latin Squares (http://www.cut-the-knot.org/Curriculum/Algebra/OrthoLatin.shtml)