graeco

Graeco-Latin square

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.

This concept was introduced by Leonhard Euler, who took the two sets 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.

History

In the 1780s 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 for any oddly even number 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. However, Euler's conjecture resisted solution for a very long time. In 1959, R.C. Bose and S. S. Shrikhande found some counterexamples; then Parker found a counterexample of order 10. In 1960, Parker, Bose, and Shrikhande showed Euler's conjecture to be false for all Thus, Graeco-Latin squares exist for all orders n ≥ 3 except

The French writer Georges Perec used the 10×10 square for the structure of constraints underlying his 1978 novel Life: A User's Manual.