Combinatorial Designs and Latin Squares: Balanced Arrangements

We define Latin squares and prove their existence, introduce mutually orthogonal Latin squares (MOLS), develop the theory of balanced incomplete block designs (BIBDs), prove Fisher's inequality, and discuss the connection with finite projective planes.

Folio Official

March 1, 2026

1 Latin Squares

Definition 1 (Latin square).

A Latin square of order

n

is an

n \times n

array filled with

n

different symbols, each occurring exactly once in every row and exactly once in every column.

Example 2.

A Latin square of order

3

123231312

Theorem 3.

For every positive integer

n

, a Latin square of order

n

exists.

Proof.

Define

L_{ij} = (i + j - 2) mod n + 1

for

1 \leq i, j \leq n

. Each row and each column contains every element of

{1, 2, \dots, n}

exactly once. This construction is nothing other than the Cayley table of the additive group

Z / n Z

. □

2 Orthogonal Latin Squares

Definition 4 (Orthogonal Latin squares).

Two Latin squares

L_{1}, L_{2}

of order

n

are orthogonal if, when superimposed, the

n^{2}

ordered pairs

((L_{1})_{ij}, (L_{2})_{ij})

are all distinct — that is, every one of the

n^{2}

possible ordered pairs appears exactly once.

Definition 5 (MOLS).

A set of Latin squares of order

n

that are pairwise orthogonal is called a set of mutually orthogonal Latin squares (MOLS). The maximum number of MOLS of order

n

is denoted

N (n)

Theorem 6.

N (n) \leq n - 1

Proof.

Suppose there exist

k

mutually orthogonal Latin squares

L_{1}, \dots, L_{k}

of order

n

. We may normalize so that the first row of each

L_{i}

(1, 2, \dots, n)

. By the orthogonality of

L_{i}

and

L_{j}

(

i \neq = j

), we must have

(L_{i})_{2, 1} \neq = (L_{j})_{2, 1}

. (If they were equal, say both equal to

c

, the pair

(1, c)

would appear in both position

(1, 1)

and position

(2, 1)

, contradicting orthogonality.) Since

(L_{i})_{2, 1} \in {2, 3, \dots, n}

and these values are distinct across different

L_{i}

, we conclude

k \leq n - 1

. □

Theorem 7.

q

is a prime power, then

N (q) = q - 1

Proof.

Let

F_{q}

be the finite field of order

q

. For each

a \in F_{q}^{*}

, define

L_{a}

(L_{a})_{ij} = ai + j

(

i, j \in F_{q}

). Each

L_{a}

is a Latin square, and for

a \neq = b

the squares

L_{a}

and

L_{b}

are orthogonal. Since

∣ F_{q}^{*} ∣ = q - 1

, we have

N (q) \geq q - 1

. Combined with the upper bound,

N (q) = q - 1

. □

3 Balanced Incomplete Block Designs

Definition 8 (BIBD).

A balanced incomplete block design (BIBD) on a

v

-element set

V

is a collection

B

k

-element subsets of

V

(called blocks) satisfying:

$2 \leq k < v$ ;
every pair of distinct elements $x, y \in V$ appears together in exactly $λ$ blocks.

Such a design is called a

(v, k, λ)

-BIBD. Let

b

denote the total number of blocks and

r

the number of blocks containing any given element.

Theorem 9 (Fundamental identities for BIBDs).

For a

(v, k, λ)

-BIBD:

$bk = v r$
$r (k - 1) = λ (v - 1)$

Proof.

(1) Count the pairs

(x, B)

with

x \in V

B \in B

, and

x \in B

. Fixing

x

gives

r

such pairs; fixing

B

gives

k

. Hence

v r = bk

(2) Fix an element

x

. In the

r

blocks containing

x

, there are

r (k - 1)

incidences of

x

with other elements (counting with multiplicity). On the other hand, each of the

v - 1

other elements appears together with

x

in exactly

λ

blocks, giving

λ (v - 1)

incidences. □

4 Fisher's Inequality

Theorem 10 (Fisher's inequality).

For a

(v, k, λ)

-BIBD, the number of blocks satisfies

b \geq v

Proof.

Consider the

v \times b

incidence matrix

N

defined by

N_{ij} = 1

x_{i} \in B_{j}

and

0

otherwise. One verifies that

N N^{T} = (r - λ) I + λ J

, where

I

is the identity matrix and

J

is the all-ones matrix. This matrix has eigenvalues

r + (v - 1) λ

(with multiplicity

1

) and

r - λ

(with multiplicity

v - 1

). Since

k < v

implies

r > λ

, all eigenvalues are positive, so

N N^{T}

is nonsingular. Therefore

rank (N) = v

, which forces

b \geq v

. □

5 Finite Projective Planes

Definition 11 (Finite projective plane).

A finite projective plane of order $n$ is an

(n^{2} + n + 1, n + 1, 1)

-BIBD. In other words,

v = b = n^{2} + n + 1

k = r = n + 1

, and

λ = 1

Theorem 12.

If a finite projective plane of order

n

exists, then there exist

N (n) = n - 1

mutually orthogonal Latin squares of order

n

Proof.

From the structure of a finite projective plane, one can construct

n - 1

MOLS. Conversely,

n - 1

MOLS can be used to construct a finite projective plane of order

n

. The two objects are thus equivalent. □

Remark 13.

When

n

is a prime power, the projective plane

PG (2, q)

over

F_{q}

provides an explicit construction. When

n = 6

, the question is related to Euler's problem of the 36 officers; Tarry showed in 1901 that

N (6) = 1

. When

n = 10

, an exhaustive computer search completed in 1989 proved that no finite projective plane of order

10

exists.

Combinatorics Discrete Mathematics Textbook Latin Squares Combinatorial Designs

Folio Official

Mathematics "between the lines" — exploring the intuition textbooks leave out, written in LaTeX on Folio.

1 フォロワー·105 記事

Combinatorial Designs and Latin Squares: Balanced Arrangements

1 Latin Squares

2 Orthogonal Latin Squares

3 Balanced Incomplete Block Designs

4 Fisher's Inequality

5 Finite Projective Planes

あなたの専門知識を世界に発信しよう

Folio Officialの他の記事

Monetizing Your Articles — How to Earn Revenue Safely with Stripe Connect

Mastering Theorem Environments — theorem, definition, proof, and Friends

Burnside's Lemma and P\'olya Enumeration: Counting Under Symmetry

Recurrence Relations and Counting: Solving Linear Recurrences