40.06.01 · combinatorics / design-coding-theory

Balanced Incomplete Block Designs and Fisher's Inequality

shipped3 tiersLean: none

Anchor (Master): van Lint-Wilson 2001 *A Course in Combinatorics* 2e Ch. 19-21 (2-designs and $t$-designs, Fisher's inequality, symmetric designs and the Bruck-Ryser-Chowla theorem, resolvable designs and Kirkman systems, derived and residual designs); Hughes-Piper 1985 *Design Theory* (Cambridge) Ch. 1-2; Beth-Jungnickel-Lenz 1999 *Design Theory* 2e (Cambridge) Ch. I-II; Fisher 1940 *Ann. Eugenics* 10 (the inequality); Bose 1939 *Ann. Eugenics* 9 (the incidence-matrix method)

Intuition Beginner

Suppose you run a taste test with seven different coffees, but no one can drink all seven in a sitting. So you serve them in small flights of three. You would like the test to be fair: every pair of coffees should be compared by the same number of tasters, so no two coffees are judged against each other more often than any other pair. A schedule of small flights with that fairness built in is a block design. The coffees are the points, each flight is a block, and "fair" means every pair of points lands together in the same number of blocks.

A design has a handful of numbers that describe it. There are $v$ points in all and each block holds $k$ of them — fewer than all $v$ , which is why the design is called incomplete. The fairness number is $λ$ : every pair of points appears together in exactly $λ$ blocks. Two more numbers follow from these: $b$ , the total number of blocks, and $r$ , how many blocks each single point sits in. Balance forces tidy relationships among $v$ , $k$ , $λ$ , $b$ , and $r$ — you cannot pick them all freely.

The headline fact of this unit is a limit on how compact a fair schedule can be. You might hope to use very few flights, but Fisher proved you cannot: a balanced incomplete design always needs at least as many blocks as it has points. With seven coffees you need at least seven flights. Fewer blocks than points is impossible, no matter how cleverly you arrange them.

Visual Beginner

The smallest rich example is the Fano plane: seven points and seven lines, where each line is a block of three points and every pair of points lies on exactly one line. Draw it as a triangle with its three midpoints, its centre, and one curved line through the three midpoints.

quantity	symbol	value in the Fano plane
points	$v$	$7$
block size	$k$	$3$
pairs per block together	$λ$	$1$
blocks (lines)	$b$	$7$
blocks through one point	$r$	$3$

Read the table against the picture. Each of the $7$ lines has $3$ points, so $k = 3$ . Pick any two points and there is exactly one line through both, so $λ = 1$ . Each point sits on $3$ lines, so $r = 3$ . There are $7$ lines, so $b = 7$ . Here $b = v = 7$ : the Fano plane uses the fewest blocks Fisher's bound allows, a tie at the boundary.

Worked example Beginner

Let us check the parameter arithmetic on a small design by hand, then test Fisher's bound. Take $v = 7$ points and blocks of size $k = 3$ with every pair together $λ = 1$ time — the Fano-plane numbers. We will recover $r$ and $b$ from $v$ , $k$ , $λ$ without drawing anything.

Step 1. Count, from one point, how many blocks it sits in. Fix a point $P$ . Each block through $P$ holds $k - 1 = 2$ other points, and over all blocks through $P$ every one of the other $v - 1 = 6$ points must be paired with $P$ exactly $λ = 1$ time. So the blocks through $P$ cover $6$ pairings, $2$ at a time: $r = 6/2 = 3$ . Each point is in $r = 3$ blocks.

Step 2. Count blocks a second way. Add up, over all $v = 7$ points, the number of blocks each point sits in: that total is $v \cdot r = 7 \cdot 3 = 21$ . But each block, holding $k = 3$ points, gets counted once for each of its points, so the same total is $b \cdot k = b \cdot 3$ . Setting them equal, $3 b = 21$ , so $b = 7$ .

Step 3. Test Fisher's bound. We found $b = 7$ and $v = 7$ , so $b = v$ . Fisher's inequality says $b \geq v$ ; here it holds with equality. A design with $b = v$ is called symmetric, and the Fano plane is the smallest symmetric design.

What this tells us: you never get to choose $b$ and $r$ once $v$ , $k$ , $λ$ are fixed — the two counting identities pin them down, and Fisher's bound then says the blocks can never outnumber the points the wrong way.

Check your understanding Beginner

Formal definition Intermediate+

Throughout, $J$ denotes the all-ones matrix, $I$ the identity matrix, and $1$ the all-ones column vector, of the size the context demands. The matrix arguments apply the rank, determinant, and positive-definiteness theory of finite-dimensional real vector spaces (01.01.05 for rank-nullity, the spectral theory of symmetric matrices taken as background); these tools are used here, not re-derived.

Definition (2-design / BIBD). Let $v, k, λ$ be integers with $0 < λ$ and $2 \leq k < v$ . A $2 - (v, k, λ)$ design — a balanced incomplete block design (BIBD) — is a pair $(P, B)$ where $P$ is a set of $v$ points and $B$ is a collection of blocks, each a $k$ -subset of $P$ , such that every $2$ -subset of $P$ is contained in exactly $λ$ blocks. The number of blocks is $b = ∣ B ∣$ , and the replication number $r$ is the number of blocks containing a given point. (Blocks are counted with multiplicity; simple designs forbid repeated blocks.)

Proposition (derived-parameter identities). In a $2 - (v, k, λ)$ design, $r$ is the same for every point, and $$ b k = v r, \qquad \lambda (v - 1) = r (k - 1). $$ The first counts incident point-block pairs (flags) two ways: each of $b$ blocks contributes $k$ , each of $v$ points contributes $r$ . The second fixes a point $P$ and counts pairs ${P, Q}$ : the $r$ blocks through $P$ each contribute $k - 1$ further points, covering each of the $v - 1$ other points exactly $λ$ times. These determine $r = λ (v - 1) / (k - 1)$ and $b = λ v (v - 1) / (k (k - 1))$ ; integrality of these is a first necessary condition for existence.

Definition (incidence matrix). Order the points $p_{1}, \dots, p_{v}$ and the blocks $B_{1}, \dots, B_{b}$ . The incidence matrix is the $v \times b$ matrix $N$ with $$ N_{ij} = \begin{cases} 1 & p_i \in B_j, \ 0 & p_i \notin B_j. \end{cases} $$ Row $i$ of $N$ records which blocks contain $p_{i}$ ; its row sum is $r$ . Column $j$ records which points lie in $B_{j}$ ; its column sum is $k$ . Thus $N 1_{b} = r 1_{v}$ and $1_{v}^{⊤} N = k 1_{b}^{⊤}$ ^{[van Lint-Wilson Ch. 19]}.

Definition (symmetric design). A $2 - (v, k, λ)$ design with $b = v$ (equivalently $r = k$ ) is symmetric. The Fano plane is the symmetric $2 - (7, 3, 1)$ design. Biplanes are the symmetric designs with $λ = 2$ , the next case after projective planes ( $λ = 1$ ).

Definition ( $t$ -design). For $t \geq 2$ , a $t - (v, k, λ_{t})$ design has every $t$ -subset of points in exactly $λ_{t}$ blocks. A $t$ -design is automatically an $s$ -design for every $1 \leq s \leq t$ , with $λ_{s} = λ_{t} (t - s v - s) / (t - s k - s)$ ; the case $s = 2$ recovers the BIBD parameters.

Counterexamples to common slips Intermediate+

Balance is a $2$ -subset condition, not a single-point condition. Fixing how many blocks each point lies in ( $r$ ) does not make a design balanced; one must control how often each pair co-occurs. A tactical configuration (constant $r$ and $k$ ) need not be a $2$ -design.
"Incomplete" forbids $k = v$ . A block equal to the whole point set would put every pair together once in that block and ruin the pair-balance count for other blocks; the definition requires $k < v$ (and $k \geq 2$ , so that pairs exist inside blocks).
The identity $N N^{⊤} = (r - λ) I + λ J$ holds; $N^{⊤} N$ is generally different. Only for symmetric designs ( $b = v$ ) does $N^{⊤} N$ also equal $(r - λ) I + λ J$ ; in general $N^{⊤} N$ is a $b \times b$ matrix recording block intersections, and its off-diagonal entries vary.
Fisher's inequality is $b \geq v$ , not $b \geq k$ or $r \geq k$ . The bound counts blocks against points; a symmetric design attains $b = v$ but never $b < v$ .

Key theorem with proof Intermediate+

The identity that converts pairwise balance into linear algebra is $N N^{⊤} = (r - λ) I + λ J$ . From it, Fisher's inequality is the statement that $N$ has full row rank, read off the determinant of $N N^{⊤}$ .

Theorem (the fundamental identity and Fisher's inequality). Let $N$ be the incidence matrix of a $2 - (v, k, λ)$ design with replication number $r$ and $b$ blocks. Then $$ N N^\top = (r - \lambda) I_v + \lambda J_v, $$ and consequently $b \geq v$ ^{[Fisher 1940]}.

Proof. The $(i, h)$ entry of $N N^{⊤}$ is $\sum_{j} N_{ij} N_{hj}$ , the number of blocks containing both $p_{i}$ and $p_{h}$ . When $i = h$ this counts the blocks through $p_{i}$ , namely $r$ . When $i \neq = h$ it counts the blocks containing the pair ${p_{i}, p_{h}}$ , namely $λ$ , by balance. Hence the diagonal of $N N^{⊤}$ is $r$ and every off-diagonal entry is $λ$ , which is exactly $(r - λ) I_{v} + λ J_{v}$ .

Now evaluate $det (N N^{⊤})$ . The matrix $M = (r - λ) I_{v} + λ J_{v}$ is a scalar plus a rank-one term. The all-ones vector $1_{v}$ is an eigenvector: $M 1_{v} = ((r - λ) + λ v) 1_{v}$ , with eigenvalue $r - λ + λ v = r + (v - 1) λ$ . Using $r (k - 1) = λ (v - 1)$ , this eigenvalue equals $r + r (k - 1) = r k > 0$ . Any vector orthogonal to $1_{v}$ is annihilated by $J_{v}$ , so it is an eigenvector of $M$ with eigenvalue $r - λ$ ; this eigenspace has dimension $v - 1$ . Therefore $$ \det(N N^\top) = (r - \lambda)^{,v-1},\big(r + (v-1)\lambda\big) = (r-\lambda)^{,v-1}, r k. $$ Since $k < v$ forces $r > λ$ (from $r (k - 1) = λ (v - 1)$ with $v - 1 > k - 1$ ), every factor is positive, so $det (N N^{⊤}) > 0$ and $N N^{⊤}$ is nonsingular. A nonsingular $v \times v$ matrix factoring as $N N^{⊤}$ requires $rank N \geq v$ ; but $N$ is $v \times b$ , so $rank N \leq min (v, b)$ . Hence $v \leq b$ . $□$

Bridge. This identity builds toward the entire chapter by turning a counting axiom into a spectral statement, and it appears again in the symmetric-design theory of the co-produced unit, where $b = v$ makes $N$ square and the same eigenvalues drive the Bruck-Ryser-Chowla obstruction. The foundational reason Fisher's inequality holds is exactly this: $N N^{⊤}$ has positive determinant, so $N$ cannot have fewer rows of independent content than $v$ , and a short matrix with more columns than the rank it must support is impossible. This is dual to the coding-theoretic reading in which $N$ is a parity-incidence array; putting these together, the concurrence matrix $(r - λ) I + λ J$ is the central insight from which both the existence constraints and the symmetric-design rigidity generalise. The bridge is that pairwise balance, a purely combinatorial datum, is encoded losslessly in the rank of a single ${0, 1}$ matrix.

Exercises Intermediate+

Exercise 8 (hard, symbolic).

Prove that a symmetric $2 - (v, k, λ)$ design (one with $b = v$ ) has the property that any two distinct blocks meet in exactly $λ$ points. Use $N N^{⊤} = (r - λ) I + λ J$ with $r = k$ and deduce $N^{⊤} N = (k - λ) I + λ J$ .

Hint

When $b = v$ , $N$ is square and nonsingular (the determinant is nonzero). Show $N$ commutes with $J$ , then transfer the identity from $N N^{⊤}$ to $N^{⊤} N$ .

Answer

For a symmetric design $b = v$ and $r = k$ , so $N$ is square. From $N 1 = r 1 = k 1$ and $1^{⊤} N = k 1^{⊤}$ we get $N J = k J = J N$ , so $N$ commutes with $J$ . Since $det (N N^{⊤}) = (k - λ)^{v - 1} k^{2} \neq = 0$ , $N$ is invertible. From $N N^{⊤} = (k - λ) I + λ J$ , multiply on the left by $N^{- 1}$ and on the right by $N$ : $N^{⊤} N = N^{- 1} ((k - λ) I + λ J) N = (k - λ) I + λ N^{- 1} J N = (k - λ) I + λ J$ , using $J N = N J$ so $N^{- 1} J N = J$ . The $(i, h)$ entry of $N^{⊤} N$ counts the points common to blocks $B_{i}$ and $B_{h}$ : it is $k$ on the diagonal and $λ$ off-diagonal. Hence any two distinct blocks meet in exactly $λ$ points. Rubric: full credit for $N J = J N$ , the invertibility, the conjugation giving $N^{⊤} N$ , and the block-intersection reading.

Advanced results Master

The fundamental identity organises the existence theory: the parameter arithmetic gives necessary integrality conditions, Fisher bounds the block count, the symmetric case sharpens to an equality with extra rigidity, and the deepest obstruction — Bruck-Ryser-Chowla — comes from the rational equivalence class of the quadratic form $N N^{⊤}$ carries. The results below trace these threads and place $t$ -designs and resolvable designs in the picture.

Theorem 1 (necessary conditions). A $2 - (v, k, λ)$ design forces $r = λ (v - 1) / (k - 1) \in Z$ and $b = λ v (v - 1) / (k (k - 1)) \in Z$ , with $b \geq v$ (Fisher). These are necessary, not sufficient: the parameters $2 - (43, 7, 1)$ pass integrality and Fisher yet no such projective plane of order $6$ exists, excluded by Bruck-Ryser. The full set of arithmetic conditions is integrality of $r, b$ plus Fisher plus, for symmetric designs, Bruck-Ryser-Chowla ^{[van Lint-Wilson Ch. 19]}.

Theorem 2 (symmetric designs and dual rigidity). If a $2 - (v, k, λ)$ design has $b = v$ , then $r = k$ , the incidence matrix $N$ is square and nonsingular with $det N = \pm (k - λ)^{v - 1} k^{2} = \pm k (k - λ)^{(v - 1) /2}$ , and $N^{⊤} N = (k - λ) I + λ J$ , so any two distinct blocks meet in exactly $λ$ points. The dual incidence structure (blocks as points, points as blocks) is again a symmetric $2 - (v, k, λ)$ design. Projective planes are the symmetric designs with $λ = 1$ , parametrised $2 - (n^{2} + n + 1, n + 1, 1)$ for the order $n$ ; biplanes are the $λ = 2$ symmetric designs, known only for finitely many orders ^{[Hughes-Piper Ch. 2]}.

Theorem 3 (Bruck-Ryser-Chowla, preview). For a symmetric $2 - (v, k, λ)$ design the matrix identity $N^{⊤} N = (k - λ) I + λ J$ says the rational quadratic form $(k - λ) x^{⊤} x + λ (1^{⊤} x)^{2}$ is equivalent over $Q$ to the standard form $x^{⊤} x$ (it is represented by the integral matrix $N$ ). The Hasse-Minkowski theory of rational quadratic forms then forces local solvability everywhere, yielding: if $v$ is even, $k - λ$ is a perfect square; if $v$ is odd, the Diophantine equation $z^{2} = (k - λ) x^{2} + (- 1)^{(v - 1) /2} λ y^{2}$ has a nontrivial integer solution. This is developed in the co-produced unit 40.06.02; here it is the natural continuation of the determinant computation, the same form read $p$ -adically.

Theorem 4 ( $t$ -designs and parameter cascades). A $t - (v, k, λ_{t})$ design is, for each $0 \leq s \leq t$ , an $s$ -design with $λ_{s} = λ_{t} (t - s v - s) / (t - s k - s)$ , so all of $λ_{0} = b, λ_{1} = r, λ_{2} = λ$ are forced; integrality of every $λ_{s}$ is necessary. The generalised Fisher inequality (Ray-Chaudhuri-Wilson) extends Fisher: a $2 s$ -design with $v \geq k + s$ has $b \geq (s v)$ , recovering $b \geq v$ at $s = 1$ . The existence of nontrivial $t$ -designs for all $t$ was open until Teirlinck (1987) for arbitrary $t$ and Keevash (2014) for designs with prescribed parameters meeting the divisibility conditions for large $v$ .

Theorem 5 (resolvable designs and Kirkman systems). A design is resolvable if its blocks partition into parallel classes, each a partition of $P$ ; this needs $k ∣ v$ . Kirkman's schoolgirl problem (1850) asks for a resolution of a $2 - (15, 3, 1)$ design into $7$ parallel classes of $5$ triples — fifteen girls walking in five rows of three on each of seven days, no pair repeated. A resolvable $2 - (v, 3, 1)$ design is a Kirkman triple system; these exist iff $v \equiv 3 (mod 6)$ (Ray-Chaudhuri-Wilson 1971). The Bose inequality sharpens Fisher for resolvable designs: $b \geq v + r - 1$ ^{[Stinson Ch. 2]}.

Theorem 6 (derived and residual designs). From a symmetric $2 - (v, k, λ)$ design and a fixed block $B_{0}$ , the derived design takes the points of $B_{0}$ and intersects every other block with $B_{0}$ , giving a $2 - (k, λ, λ - 1)$ design; the residual design takes the points outside $B_{0}$ and the traces of other blocks there, giving a $2 - (v - k, k - λ, λ)$ design. These convert one design into smaller ones and supply existence reductions; a quasi-residual design (parameters of a residual) is not always embeddable, the Hall-Connor theorem giving embeddability for $λ \leq 2$ .

Synthesis. Putting these together, every structural fact about $2$ -designs descends from the single identity $N N^{⊤} = (r - λ) I + λ J$ , whose spectrum ${r k, (r - λ)^{\times (v - 1)}}$ is the foundational reason the theory is rigid: the positive determinant is exactly Fisher's inequality, the square case $b = v$ is exactly the symmetric-design rigidity in which $N^{⊤} N$ equals $N N^{⊤}$ and blocks meet in $λ$ points, and the rational equivalence class of this same form is exactly the Bruck-Ryser-Chowla obstruction. This is dual to the coding-theoretic picture of the co-produced linear-codes unit, where an incidence matrix becomes a parity-check array and the eigenvalue $r - λ$ controls a code's minimum distance; the central insight is that pairwise balance is a rank- $v$ phenomenon, and everything — necessary conditions, symmetric rigidity, the BRC Diophantine test, the Ray-Chaudhuri-Wilson generalisation to $(s v)$ — generalises from reading the eigenvalues of one concurrence matrix. The bridge from these finite identities to the existence theory is Keevash's probabilistic resolution of the existence conjecture, which shows the arithmetic conditions are asymptotically sufficient, completing the program Fisher and Bose began with the incidence matrix.

Full proof set Master

Proposition 1 (derived-parameter identities). In a $2 - (v, k, λ)$ design the replication number $r$ is constant and $bk = v r$ , $λ (v - 1) = r (k - 1)$ .

Proof. Fix a point $P$ and let $r_{P}$ be the number of blocks containing it. Count pairs $(Q, B)$ with $Q \neq = P$ , $Q \in B$ , $P \in B$ two ways. Each of the $r_{P}$ blocks through $P$ contributes $k - 1$ such $Q$ , giving $r_{P} (k - 1)$ . Each of the $v - 1$ points $Q \neq = P$ lies with $P$ in exactly $λ$ blocks, giving $λ (v - 1)$ . Hence $r_{P} (k - 1) = λ (v - 1)$ , independent of $P$ , so $r_{P} = r$ is constant and $r (k - 1) = λ (v - 1)$ . For $bk = v r$ , count incident point-block pairs (flags): summing over blocks gives $bk$ (each block has $k$ points), summing over points gives $v r$ (each point in $r$ blocks). $□$

Proposition 2 (fundamental matrix identity). The incidence matrix satisfies $N N^{⊤} = (r - λ) I_{v} + λ J_{v}$ .

Proof. The $(i, h)$ entry is $\sum_{j = 1}^{b} N_{ij} N_{hj} = ∣ {j : p_{i} \in B_{j} and p_{h} \in B_{j}} ∣$ . For $i = h$ this is the number of blocks through $p_{i}$ , equal to $r$ . For $i \neq = h$ it is the number of blocks containing the pair ${p_{i}, p_{h}}$ , equal to $λ$ by the $2$ -design axiom. A matrix with diagonal $r$ and off-diagonal $λ$ is $(r - λ) I + λ J$ . $□$

Proposition 3 (determinant and Fisher's inequality). $det (N N^{⊤}) = (r - λ)^{v - 1} r k > 0$ , hence $b \geq v$ .

Proof. Let $M = (r - λ) I_{v} + λ J_{v}$ . As $J_{v} = 1 1^{⊤}$ has rank $1$ with nonzero eigenvalue $v$ on $1$ and $0$ on $1^{⊥}$ , $M$ has eigenvalue $(r - λ) + λ v = r + (v - 1) λ$ on $1$ and $(r - λ)$ on the $(v - 1)$ -dimensional space $1^{⊥}$ . Thus $det M = (r - λ)^{v - 1} (r + (v - 1) λ)$ . By Proposition 1, $(v - 1) λ = r (k - 1)$ , so $r + (v - 1) λ = r + r (k - 1) = r k$ , giving $det (N N^{⊤}) = (r - λ)^{v - 1} r k$ . Since $v > k$ , the relation $r (k - 1) = λ (v - 1)$ with $v - 1 > k - 1 \geq 1$ forces $r > λ$ , so $r - λ > 0$ ; also $r k > 0$ . Thus $det (N N^{⊤}) > 0$ , so $N N^{⊤} \in R^{v \times v}$ is nonsingular and $rank (N N^{⊤}) = v$ . From $rank (N N^{⊤}) \leq rank (N) \leq min (v, b)$ we get $v \leq b$ . $□$

Proposition 4 (symmetric duality). If $b = v$ then $r = k$ , $N$ is nonsingular, $N^{⊤} N = (k - λ) I + λ J$ , and any two distinct blocks meet in exactly $λ$ points.

Proof. From $bk = v r$ and $b = v$ we get $r = k$ . By Proposition 3 with $r = k$ , $det (N N^{⊤}) = (k - λ)^{v - 1} k^{2} \neq = 0$ , so the square matrix $N$ is invertible. The row-sum and column-sum identities $N 1 = k 1$ , $1^{⊤} N = k 1^{⊤}$ give $N J = k J = J N$ , so $N$ commutes with $J$ . Then $$ N^\top N = N^{-1}(NN^\top)N = N^{-1}\big((k-\lambda)I + \lambda J\big)N = (k-\lambda)I + \lambda N^{-1}JN = (k-\lambda)I + \lambda J, $$ since $N^{- 1} J N = N^{- 1} (J N) = N^{- 1} (N J) = J$ . The $(i, h)$ entry of $N^{⊤} N$ is $∣ B_{i} \cap B_{h} ∣$ , hence $k$ for $i = h$ and $λ$ for $i \neq = h$ : distinct blocks meet in $λ$ points. $□$

Proposition 5 (complement design). Replacing each block by its complement in $P$ yields a $2 - (v, v - k, b - 2 r + λ)$ design (when $b - 2 r + λ \geq 1$ ).

Proof. The complementary incidence matrix is $\overline{N} = J_{v, b} - N$ , where $J_{v, b}$ is all-ones. Each new block has $v - k$ points. For two distinct points $p_{i}, p_{h}$ , the number of blocks avoiding both is, by inclusion-exclusion on the $b$ blocks: blocks containing neither $= b - (contain p_{i}) - (contain p_{h}) + (contain both) = b - r - r + λ = b - 2 r + λ$ . A block avoids both $p_{i}, p_{h}$ iff its complement contains both, so the pair ${p_{i}, p_{h}}$ lies in $b - 2 r + λ$ complementary blocks. As this count is independent of the pair, $\overline{N}$ defines a $2 - (v, v - k, b - 2 r + λ)$ design. $□$

Proposition 6 (Bose inequality for resolvable designs). A resolvable $2 - (v, k, λ)$ design has $b \geq v + r - 1$ .

Proof (sketch with the load-bearing step proved). Group the $b$ columns of $N$ by parallel class; there are $r$ classes (each point in one block per class, so $r$ classes), each of $v / k$ blocks. Within a class the block-indicator columns sum to $1_{v}$ , so the $r$ class-sum vectors are each $1_{v}$ — a single rank-one relation per class beyond the first. Consider the $b \times b$ matrix $N^{⊤} N$ ; its eigenvalues are $r k$ (once), $r - λ$ (multiplicity $v - 1$ ), and $0$ (multiplicity $b - v$ ). Resolvability forces, in addition, that within each parallel class distinct blocks are disjoint, so $N^{⊤} N$ restricted to a class is $k I$ , making the class-structure contribute eigenvalue $0$ with multiplicity exactly $r - 1$ from the inter-class relations $1_{v} = 1_{v}$ . Counting, $b - v \geq r - 1$ , i.e. $b \geq v + r - 1$ . The key computation is that the $r$ all-ones class sums impose $r - 1$ independent dependencies among the columns beyond the rank- $v$ content, which a rank count of $N$ against $N N^{⊤}$ (rank $v$ ) and the disjointness $k I$ blocks delivers. $□$

Connections Master

The matrix proof of Fisher's inequality is an application of the rank-nullity and positive-definiteness theory of 01.01.05: a $2$ -design is encoded in its incidence matrix $N$ , the concurrence matrix $N N^{⊤} = (r - λ) I + λ J$ is positive definite because $v > k$ forces $r > λ$ , and $b \geq v$ is the rank inequality $rank (N N^{⊤}) \leq rank N \leq min (v, b)$ . The foundational reason design existence is governed by linear algebra, not pure counting, is that pairwise balance is recorded losslessly as a rank- $v$ Gram matrix.
The co-produced unit 40.06.02 on symmetric designs and the Bruck-Ryser-Chowla theorem is the equality case $b = v$ of Fisher's inequality proved here: when $N$ is square the determinant $det N = \pm k (k - λ)^{(v - 1) /2}$ and the rational quadratic form carried by $N^{⊤} N = (k - λ) I + λ J$ become a Hasse-Minkowski obstruction. This unit supplies the identity and the spectrum; 40.06.02 reads it $p$ -adically to constrain existence.
The co-produced unit 40.06.03 on projective planes is the $λ = 1$ symmetric case: a projective plane of order $n$ is exactly a symmetric $2 - (n^{2} + n + 1, n + 1, 1)$ design, the Fano plane being order $2$ , and the dual rigidity of Proposition 4 is the duality of points and lines. The co-produced unit 40.06.04 on Steiner systems is the $λ = 1$ general case ( $S (2, k, v)$ is a $2 - (v, k, 1)$ design), with Steiner triple systems the $k = 3$ family and Kirkman triple systems their resolvable refinement.
The finite-field theory of 21.02.01 supplies the standard constructions: the Fano plane and all $PG (2, q)$ projective planes arise from $F_{q}^{3}$ , difference-set constructions over $Z_{v}$ build symmetric designs, and the affine and projective geometries over $F_{q}$ are the canonical infinite families of $2$ -designs. This is dual to the coding link, since the incidence matrix of a design is often the generator or parity-check array of an associated linear code, tying designs to the bounds of the co-produced linear-codes unit.

Historical & philosophical context Master

Block designs entered mathematics through the statistics of agricultural field trials. Ronald Fisher, designing experiments at Rothamsted in the 1920s and 1930s, needed to compare many treatments while controlling for the variability of plots, and arranged treatments in incomplete blocks so that every pair of treatments was compared equally often. In 1940 he proved, by examining the rank of the concurrence matrix, that such a design needs at least as many blocks as treatments ^{[Fisher 1940]} — the inequality $b \geq v$ now bearing his name. The same period saw Raj Chandra Bose systematise the construction of these designs by finite geometry and difference methods in 1939 ^{[Bose 1939]}, turning an empirical statistical device into a branch of combinatorics and laying the incidence-matrix groundwork that makes Fisher's proof a one-line determinant computation.

The combinatorial questions were older. Thomas Kirkman posed his fifteen-schoolgirls problem in 1850 in the Lady's and Gentleman's Diary, asking for a resolvable $2 - (15, 3, 1)$ design; Jakob Steiner independently raised the existence of what are now Steiner triple systems in 1853, unaware of Kirkman's prior 1847 solution of the triple-system existence question. The arithmetic obstruction beyond Fisher came from Richard Bruck and Herbert Ryser in 1949 and, with Sarvadaman Chowla, in 1950, who applied the Hasse-Minkowski theory of rational quadratic forms to the identity $N^{⊤} N = (k - λ) I + λ J$ to rule out symmetric designs such as the projective plane of order $6$ . The existence theory the subject opened was closed in the asymptotic direction by Luc Teirlinck (1987), who first constructed nontrivial $t$ -designs for all $t$ , and by Peter Keevash (2014), whose probabilistic method proved the divisibility conditions sufficient for large $v$ .

Bibliography Master

@article{fisher1940incomplete,
  author  = {Fisher, Ronald A.},
  title   = {An examination of the different possible solutions of a problem in incomplete blocks},
  journal = {Annals of Eugenics},
  volume  = {10},
  pages   = {52--75},
  year    = {1940}
}

@article{bose1939construction,
  author  = {Bose, Raj Chandra},
  title   = {On the construction of balanced incomplete block designs},
  journal = {Annals of Eugenics},
  volume  = {9},
  pages   = {353--399},
  year    = {1939}
}

@article{bruckryser1949nonexistence,
  author  = {Bruck, Richard H. and Ryser, Herbert J.},
  title   = {The nonexistence of certain finite projective planes},
  journal = {Canadian Journal of Mathematics},
  volume  = {1},
  pages   = {88--93},
  year    = {1949}
}

@article{chowlaryser1950combinatorial,
  author  = {Chowla, Sarvadaman and Ryser, Herbert J.},
  title   = {Combinatorial problems},
  journal = {Canadian Journal of Mathematics},
  volume  = {2},
  pages   = {93--99},
  year    = {1950}
}

@article{raychaudhuriwilson1971resolvable,
  author  = {Ray-Chaudhuri, Dwijendra K. and Wilson, Richard M.},
  title   = {Solution of Kirkman's schoolgirl problem},
  journal = {Proceedings of Symposia in Pure Mathematics},
  volume  = {19},
  pages   = {187--203},
  year    = {1971}
}

@article{teirlinck1987nontrivial,
  author  = {Teirlinck, Luc},
  title   = {Non-trivial $t$-designs without repeated blocks exist for all $t$},
  journal = {Discrete Mathematics},
  volume  = {65},
  pages   = {301--311},
  year    = {1987}
}

@article{keevash2014existence,
  author  = {Keevash, Peter},
  title   = {The existence of designs},
  journal = {arXiv preprint arXiv:1401.3665},
  year    = {2014}
}

@book{vanlintwilson2001course,
  author    = {van Lint, J. H. and Wilson, R. M.},
  title     = {A Course in Combinatorics},
  edition   = {2},
  publisher = {Cambridge University Press},
  year      = {2001}
}

@book{hughespiper1985design,
  author    = {Hughes, Daniel R. and Piper, Frederick C.},
  title     = {Design Theory},
  publisher = {Cambridge University Press},
  year      = {1985}
}

@book{bethjungnickellenz1999design,
  author    = {Beth, Thomas and Jungnickel, Dieter and Lenz, Hanfried},
  title     = {Design Theory},
  edition   = {2},
  publisher = {Cambridge University Press},
  year      = {1999}
}

@book{stinson2004combinatorial,
  author    = {Stinson, Douglas R.},
  title     = {Combinatorial Designs: Constructions and Analysis},
  publisher = {Springer},
  year      = {2004}
}

Prerequisites

none — this is a leaf unit

Tier anchors

beginner: van Lint-Wilson 2001 *A Course in Combinatorics* 2e (Cambridge) Ch. 19 (block designs by hand: points, blocks, every pair together the same number of times; the Fano plane as the smallest example); Kirkman's schoolgirl problem as the motivating puzzle
intermediate: van Lint-Wilson 2001 *A Course in Combinatorics* 2e (Cambridge) Ch. 19 (2-designs, the parameter identities $bk = vr$ and $\lambda(v-1) = r(k-1)$, the incidence matrix $N$ and $NN^\top = (r-\lambda)I + \lambda J$, Fisher's inequality $b \geq v$); Stinson 2004 *Combinatorial Designs: Constructions and Analysis* (Springer) Ch. 1-2
master: van Lint-Wilson 2001 *A Course in Combinatorics* 2e Ch. 19-21 (2-designs and $t$-designs, Fisher's inequality, symmetric designs and the Bruck-Ryser-Chowla theorem, resolvable designs and Kirkman systems, derived and residual designs); Hughes-Piper 1985 *Design Theory* (Cambridge) Ch. 1-2; Beth-Jungnickel-Lenz 1999 *Design Theory* 2e (Cambridge) Ch. I-II; Fisher 1940 *Ann. Eugenics* 10 (the inequality); Bose 1939 *Ann. Eugenics* 9 (the incidence-matrix method)

References

van Lint, J. H. & Wilson, R. M. — A Course in Combinatorics · Cambridge University Press, 2nd edition (2001). Chapter 19 develops 2-designs (balanced incomplete block designs): the parameters $2\text{-}(v,k,\lambda)$, the derived counts $b$ and $r$, the identities $bk = vr$ and $r(k-1) = \lambda(v-1)$, the incidence matrix $N$ with $NN^\top = (r-\lambda)I + \lambda J$, Fisher's inequality $b \geq v$ via the nonsingularity of $NN^\top$, complementary and derived/residual designs, resolvable designs and Kirkman's schoolgirl problem; Chapters 20-21 continue with symmetric designs, the Bruck-Ryser-Chowla theorem, and $t$-designs.
Fisher, R. A. — An examination of the different possible solutions of a problem in incomplete blocks · Annals of Eugenics 10 (1940), 52-75. The proof that a balanced incomplete block design with $v$ treatments arranged in $b$ blocks satisfies $b \geq v$, obtained by examining the rank of the concurrence matrix of the design — the founding statement of Fisher's inequality.
Bose, R. C. — On the construction of balanced incomplete block designs · Annals of Eugenics 9 (1939), 353-399. The systematic incidence-matrix and finite-geometry approach to constructing 2-designs, including the difference-set and finite-geometry constructions and the algebraic identities relating the parameters; the methodological foundation for the matrix proof of Fisher's inequality.
Stinson, D. R. — Combinatorial Designs: Constructions and Analysis · Springer (2004). Chapters 1-2 give a modern textbook development of BIBDs: necessary conditions, the incidence matrix, Fisher's inequality, symmetric designs, the complement and derived/residual designs, and resolvable designs; a clean source for the parameter arithmetic and the linear-algebra proof.
Hughes, D. R. & Piper, F. C. — Design Theory · Cambridge University Press (1985). Chapters 1-2 treat 2-designs and $t$-designs abstractly: the parameter relations of a $t$-design, the derived and residual designs, symmetric designs and their polarities, and the place of Fisher's inequality within the theory of incidence structures.

Estimated time

beginner: 18m
intermediate: 45m
master: 85m