A topic in the Open Knowledge Graph — a free, open map of 15,290 topics and the order to learn them in.
A Latin square of order n is an n×n array filled with n symbols such that each symbol appears exactly once in each row and column. Two Latin squares are orthogonal if, when superimposed, each ordered pair appears exactly once. Latin squares have applications in experimental design, error-correcting codes, and combinatorial puzzles.
You've already studied permutations, so you have the right foundation here. Think of a Latin square as a generalization of a permutation: a permutation arranges n symbols in a single row with no repeats; a Latin square arranges n symbols in n rows, with each row being a permutation, subject to the additional constraint that each symbol also appears exactly once in every column. The classic everyday example is Sudoku: a 9×9 Latin square (with extra regional constraints) using symbols 1 through 9. A simple 3×3 example with symbols {A, B, C}: row 1 = (A B C), row 2 = (B C A), row 3 = (C A B) — each symbol appears once per row and once per column.
Every Latin square of order n can be viewed as the Cayley table of a quasigroup: a set with a binary operation where each element appears exactly once in every row and column of the multiplication table. This connects Latin squares to abstract algebra. Constructing Latin squares is straightforward for prime orders (use the addition table of ℤₙ) but can be surprisingly constrained for other orders. For example, no 2×2 Latin square exists other than trivial permutations, and the number of distinct Latin squares grows extremely rapidly with n.
The deeper structure emerges with orthogonal Latin squares (OLS). Two Latin squares L₁ and L₂ of order n are orthogonal if, when you overlay them cell by cell, every ordered pair (symbol from L₁, symbol from L₂) appears exactly once across the n² cells. This is a powerful balance property: no combination of choices from the two squares is privileged. The existence of OLS is deeply connected to finite projective planes — a complete set of n−1 mutually orthogonal Latin squares of order n exists if and only if there is a projective plane of order n. Such complete sets exist when n is a prime power. Famously, no pair of OLS of order 6 exists (Euler's conjecture about "36 officers problem," proved by Tarry in 1901), and the question for n=10 required computer search.
Applications are pervasive. In statistics, Latin square designs eliminate two sources of variation simultaneously: rows represent one blocking factor (e.g., time periods), columns represent another (e.g., locations), and the symbols are treatments — each treatment appears exactly once in each row and column, so comparisons are unconfounded by either nuisance variable. In coding theory, OLS pairs generate orthogonal arrays, which are equivalent to error-detecting codes. In cryptography, Latin squares serve as substitution boxes (S-boxes) in block ciphers. Sudoku puzzles are constrained Latin squares whose solution spaces have been enumerated: there are exactly 6,670,903,752,021,072,936,960 valid 9×9 Sudoku grids, reduced to 5,472,730,538 essentially different ones under symmetry.