40.06.02 · combinatorics / design-coding-theory

Symmetric Designs and the Bruck-Ryser-Chowla Theorem

shipped3 tiersLean: none

Anchor (Master): van Lint-Wilson 2001 *A Course in Combinatorics* 2e Ch. 19-20 (symmetric designs, the rational congruence of $NN^\top$, the Hasse-Minkowski reduction, the BRC Diophantine condition, biplanes, Hadamard designs); Lam-Thiel-Swiercz 1989 *Canad. J. Math.* 41 (the computer nonexistence of the projective plane of order 10); Bruck-Ryser 1949 *Canad. J. Math.* 1; Chowla-Ryser 1950 *Canad. J. Math.* 2; Hughes-Piper 1985 *Design Theory* (Cambridge) Ch. 2; Lam 1991 *Amer. Math. Monthly* 98 (the order-10 survey)

Intuition Beginner

A block design becomes especially rigid when it has exactly as many blocks as points. Picture a small town with seven clubs and seven residents, where each club has the same number of members, each resident belongs to the same number of clubs, and any two residents share membership in exactly the same number of clubs. When the count of clubs equals the count of residents, a surprising thing happens: any two clubs overlap in exactly the same number of members too. The balance you built into the points reflects back onto the blocks. A design with this matched count is called symmetric.

The most famous symmetric designs are the projective planes. A projective plane is a collection of points and lines where any two points lie on exactly one common line, any two lines meet in exactly one common point, and there is no special direction in which lines run parallel. The smallest one, the Fano plane, has seven points and seven lines. The next sizes are nine plus one, sixteen plus one, and so on — but not every size works.

Here is the headline. You might guess that for every reasonable size a symmetric design exists. It does not. There is a numerical test, found by Bruck, Ryser, and Chowla, that some sizes simply fail. The cleanest casualty is a projective plane with six points on every line: the test forbids it, and so no such plane exists, no matter how cleverly you try to build one.

Visual Beginner

The Fano plane is the smallest symmetric design: seven points, seven lines, every line carrying three points, every pair of points on exactly one line. Because it is symmetric, any two lines also meet in exactly one point. Read the table against the picture.

quantity	symbol	Fano plane	order-6 plane (forbidden)
points	$v$	$7$	$43$
points on a line	$k$	$3$	$7$
lines through a pair of points	$λ$	$1$	$1$
lines (blocks)	$b$	$7$	$43$
order	$n = k - λ$	$2$	$6$

The order $n$ is the single most informative number. For the Fano plane $n = 2$ , a power of a prime, and the plane exists. For the hoped-for plane of order $6$ , the size $v = 43$ passes every easy counting check, yet the Bruck-Ryser-Chowla test fails because $6$ is not a sum of two squares. No order-6 plane exists.

Worked example Beginner

Let us run the existence test on the projective plane of order $6$ and watch it fail. A projective plane of order $n$ has $v = n^{2} + n + 1$ points, each line holds $k = n + 1$ points, and any two points share $λ = 1$ line. For $n = 6$ : $v = 36 + 6 + 1 = 43$ , $k = 7$ , $λ = 1$ .

Step 1. Check the easy counting. The number of lines through one point is $r = (v - 1) / (k - 1) = 42/6 = 7$ . The number of lines is $b = v = 43$ . Both are whole numbers, so the simple arithmetic raises no objection.

Step 2. Find the order. The order is $n = k - λ = 7 - 1 = 6$ . Here $v = 43$ is odd, so the test we need says the equation $z^{2} = n x^{2} + λ y^{2} = 6 x^{2} + y^{2}$ must have a whole-number solution with the numbers not all zero. (The sign in front of $λ$ is $+ 1$ because of how $43$ sits relative to $4$ .)

Step 3. Apply the two-squares fact. For odd $v$ the condition reduces to: the order $n$ must be a sum of two integer squares. Check $6$ . The sums of two squares near $6$ are $4 = 2^{2} + 0^{2}$ , $5 = 2^{2} + 1^{2}$ , $8 = 2^{2} + 2^{2}$ . There is no way to write $6 = a^{2} + c^{2}$ with whole numbers. So $6$ is not a sum of two squares.

What this tells us: the test is violated, so a projective plane of order $6$ cannot exist. This matches a much older puzzle — Euler's thirty-six officers — which has the same impossibility at its heart.

Check your understanding Beginner

Formal definition Intermediate+

Throughout, $J$ denotes the all-ones matrix, $I$ the identity, and $1$ the all-ones column vector, of the size context demands. The linear algebra used here — rank, determinant, invertibility, and the spectral picture of $(k - λ) I + λ J$ — is the apparatus of 40.06.01, applied rather than re-derived. The number-theoretic input — quadratic forms over $Q$ , the Hasse-Minkowski principle, and Lagrange's four-square identity — is treated as background and cited where used.

Definition (symmetric design). A symmetric $2 - (v, k, λ)$ design is a $2 - (v, k, λ)$ design (40.06.01) whose number of blocks equals its number of points, $b = v$ . From $bk = v r$ this is equivalent to $r = k$ . The order of the design is $n = k - λ$ . A projective plane of order $n$ is the symmetric $2 - (n^{2} + n + 1, n + 1, 1)$ design; a biplane is a symmetric design with $λ = 2$ .

Proposition (block-intersection number). In a symmetric design the incidence matrix $N$ is square ( $v \times v$ ) and nonsingular, and $$ N N^\top = N^\top N = (k - \lambda) I_v + \lambda J_v. $$ Consequently any two distinct blocks meet in exactly $λ$ points. The first equality is the concurrence identity from the BIBD theory with $r = k$ ; the second is its transpose-conjugate, available because $N$ is invertible. The off-diagonal entries of $N^{⊤} N$ count $∣ B_{i} \cap B_{j} ∣$ , so the identity reads "any two blocks share $λ$ points," dual to "any two points share $λ$ blocks."

Definition (dual design). The dual of an incidence structure interchanges the roles of points and blocks, replacing $N$ by $N^{⊤}$ . For a symmetric design the dual is again a symmetric $2 - (v, k, λ)$ design with the same parameters, because $N^{⊤} (N^{⊤})^{⊤} = N^{⊤} N = (k - λ) I + λ J$ . Symmetric designs are thus exactly the $2$ -designs closed under duality with unchanged parameters.

Definition (order and the determinant). With $n = k - λ$ , the determinant of $N$ satisfies $det (N)^{2} = det (N N^{⊤}) = (k - λ)^{v - 1} k^{2} = n^{v - 1} k^{2}$ , so $$ \det N = \pm, k, n^{(v-1)/2}. $$ For $v$ even this forces $n^{(v - 1) /2}$ to make $det N$ an integer with a half-integer exponent absorbed: the parity of $v$ controls the shape of the existence obstruction, the theme of the next section.

Counterexamples to common slips Intermediate+

Symmetric does not mean self-dual as a labelled structure. It means the dual has the same parameters $(v, k, λ)$ . A specific symmetric design may or may not be isomorphic to its dual; a polarity is precisely such an isomorphism, and not every symmetric design admits one.
The block-intersection number is $λ$ , not $k - λ$ . The order $n = k - λ$ is an eigenvalue of the concurrence matrix and governs the determinant; the number of points two blocks share is the off-diagonal entry $λ$ .
Bruck-Ryser-Chowla is necessary, not sufficient. A parameter set passing BRC may still fail to be realised: the projective plane of order $10$ ( $n = 10 = 1^{2} + 3^{2}$ ) passes BRC yet does not exist, as a computer search later established.
The order need not be a prime power. All known projective planes have prime-power order, but BRC does not assert this; it only constrains $n$ through sums of squares. Whether non-prime-power orders occur is open.

Key theorem with proof Intermediate+

The signature result of this unit is the Bruck-Ryser-Chowla theorem: a Diophantine necessary condition for a symmetric design to exist, extracted from the rational equivalence class of the form carried by $N$ . The case $λ = 1$ is the projective-plane theorem of Bruck and Ryser.

Theorem (Bruck-Ryser-Chowla). Suppose a symmetric $2 - (v, k, λ)$ design exists, with order $n = k - λ$ . Then:

(i) if $v$ is even, $n$ is a perfect square;

(ii) if $v$ is odd, the equation $$ z^2 = n, x^2 + (-1)^{(v-1)/2}, \lambda, y^2 $$ has a nonzero integer solution $(x, y, z)$ ^{[Chowla-Ryser 1950]}.

Proof. Part (i): $det (N)^{2} = n^{v - 1} k^{2}$ . For $v$ even, $v - 1$ is odd, so $n^{v - 1} = (det N / k)^{2} /1$ has an odd power of $n$ equal to a perfect square divided by $k^{2}$ ; writing $det N = \pm k n^{(v - 1) /2}$ , the exponent $(v - 1) /2$ is a half-integer unless $n$ is itself a square. Since $det N$ is an integer and $k ∣ det N$ , the quantity $n^{(v - 1) /2}$ is an integer, forcing $n$ to be a perfect square.

Part (ii): assume $v$ odd. The incidence identity $N N^{⊤} = n I + λ J$ exhibits the rational symmetric matrix $A = n I + λ J$ as $N N^{⊤}$ , so $A$ is congruent over $Q$ to the identity matrix $I_{v}$ (via the rational matrix $N$ ): for all rational vectors, the quadratic form $ξ^{⊤} A ξ$ equals $∥ N^{⊤} ξ ∥^{2}$ , the standard form in the coordinates $η = N^{⊤} ξ$ . Two rational symmetric matrices that are congruent represent the same rational numbers as quadratic forms. The form of $A = n I + λ J$ in coordinates $x_{1}, \dots, x_{v}$ is $$ A(x) = n\big(x_1^2 + \dots + x_v^2\big) + \lambda\big(x_1 + \dots + x_v\big)^2, $$ and $A$ is congruent over $Q$ to $I_{v}$ .

Now reduce the rank. Lagrange's four-square theorem writes $n = a_{1}^{2} + a_{2}^{2} + a_{3}^{2} + a_{4}^{2}$ ; the identity of Euler for sums of four squares gives an orthogonal substitution showing that $n (x_{1}^{2} + x_{2}^{2} + x_{3}^{2} + x_{4}^{2})$ represents, over $Q$ , the same values as $y_{1}^{2} + y_{2}^{2} + y_{3}^{2} + y_{4}^{2}$ . Grouping the $v$ variables into blocks of four and applying this identity repeatedly collapses the form $A$ on $v$ variables (with $v$ odd, one variable left over) to a form on one variable plus the $λ (\sum x_{i})^{2}$ term. Carrying out the descent, the congruence $A ≅ I_{v}$ forces a rational, hence integral after clearing denominators, solution of $$ z^2 = n, x^2 + (-1)^{(v-1)/2}\lambda, y^2, $$ the sign $(- 1)^{(v - 1) /2}$ recording the determinant $det A = n^{v - 1} (n + v λ) = n^{v - 1} k^{2}$ modulo squares against the determinant $+ 1$ of $I_{v}$ . A nonzero solution exists because the congruence is genuine. $□$

Bridge. This theorem builds toward the entire nonexistence theory of the chapter, and it appears again in the Hadamard-design analysis of 40.06.05, where symmetric $2 - (4 m - 1, 2 m - 1, m - 1)$ designs inherit a BRC test that the Hadamard order constraint already half-anticipates. The foundational reason a counting-balanced configuration can be forbidden is exactly this: the integral matrix $N$ forces a rational congruence $n I + λ J ≅ I$ , and rational congruence is a local-global condition the Hasse-Minkowski theory reads prime by prime. This is dual to the Fisher inequality of 40.06.01, which used the same matrix $N N^{⊤}$ but read its determinant over $R$ for a rank bound; here the same matrix is read over $Q_{p}$ for an existence bound. Putting these together, the central insight is that a ${0, 1}$ incidence matrix carries a rational quadratic form whose congruence class is a complete obstruction at the level of parameters, and the projective-plane case generalises Euler's thirty-six officers into a clean two-squares test. The bridge is that combinatorial existence localises to arithmetic of quadratic forms.

Exercises Intermediate+

Exercise 3 (medium, symbolic).

Prove that in a symmetric design any two distinct blocks meet in exactly $λ$ points, starting from $N N^{⊤} = (k - λ) I + λ J$ with $N$ square.

Hint

Show $N$ commutes with $J$ using the row- and column-sum relations $N 1 = k 1$ , $1^{⊤} N = k 1^{⊤}$ . Then transport the identity from $N N^{⊤}$ to $N^{⊤} N$ by conjugation.

Answer

Each point lies in $r = k$ blocks and each block has $k$ points, so $N 1 = k 1$ and $1^{⊤} N = k 1^{⊤}$ , giving $N J = k J = J N$ . The determinant $det (N N^{⊤}) = (k - λ)^{v - 1} k^{2} \neq = 0$ makes $N$ invertible. Then $N^{⊤} N = N^{- 1} (N N^{⊤}) N = N^{- 1} ((k - λ) I + λ J) N = (k - λ) I + λ N^{- 1} J N = (k - λ) I + λ J$ , since $N^{- 1} J N = N^{- 1} (J N) = N^{- 1} (N J) = J$ . The $(i, j)$ entry of $N^{⊤} N$ is $∣ B_{i} \cap B_{j} ∣$ : it equals $k$ on the diagonal and $λ$ off-diagonal, so distinct blocks meet in $λ$ points. Rubric: full credit for $N J = J N$ , the invertibility, the conjugation, and the block-intersection reading.

Exercise 6 (medium, multiple choice).

Euler's "thirty-six officers" problem asks for a pair of orthogonal Latin squares of order $6$ . Its impossibility is equivalent, through finite geometry, to the nonexistence of which structure?

A. A Hadamard matrix of order $6$
B. A complete set of mutually orthogonal Latin squares of order $6$ , equivalently an affine/projective plane of order $6$
C. A Steiner triple system on $6$ points
D. A symmetric $2 - (6, 3, 2)$ design

Hint

A complete set of $n - 1$ mutually orthogonal Latin squares of order $n$ is equivalent to a projective plane of order $n$ .

Answer

B. A complete set of mutually orthogonal Latin squares of order $n$ exists iff a projective plane of order $n$ exists. Euler conjectured no pair of orthogonal Latin squares of order $6$ exists (Tarry verified it by hand in 1900); Bruck-Ryser later forbids the plane of order $6$ from the two-squares failure. Feedback-wrong: order $6$ is not a multiple of $4$ so Hadamard is irrelevant; a Steiner triple system needs $v \equiv 1, 3 (mod 6)$ ; and $2 - (6, 3, 2)$ has wrong parameters for the question.

Exercise 7 (hard, symbolic).

Prove the Bruck-Ryser case $λ = 1$ , $v$ odd: a projective plane of order $n$ with $v = n^{2} + n + 1$ odd can exist only if $z^{2} = n x^{2} + (- 1)^{(v - 1) /2} y^{2}$ has a nonzero integer solution; deduce that $n \equiv 1, 2 (mod 4)$ forces $n$ to be a sum of two squares.

Hint

Set $λ = 1$ in the general theorem. For the deduction, compute $(v - 1) /2 = (n^{2} + n) /2 = n (n + 1) /2 mod 2$ in terms of $n mod 4$ , then recall that the solvability of $z^{2} = n x^{2} + y^{2}$ is equivalent to $n$ being a sum of two squares.

Answer

With $λ = 1$ the BRC equation is $z^{2} = n x^{2} + (- 1)^{(v - 1) /2} y^{2}$ . Compute $(v - 1) /2 = n (n + 1) /2$ . For $n \equiv 0$ or $3 (mod 4)$ , $n (n + 1) /2$ is even, sign $+ 1$ ; for $n \equiv 1$ or $2 (mod 4)$ , $n (n + 1) /2$ is odd, sign $- 1$ — so the equation reads $z^{2} = n x^{2} - y^{2}$ , i.e. $z^{2} + y^{2} = n x^{2}$ . A nonzero solution of $z^{2} + y^{2} = n x^{2}$ exists iff $n$ is a sum of two squares: scaling by $x^{- 2}$ over $Q$ , $n = (z / x)^{2} + (y / x)^{2}$ , and a rational sum of two squares that is an integer is an integer sum of two squares (the sum-of-two-squares property is closed under the relevant rational descent, by the multiplicativity of the norm form of $Z [i]$ ). Hence for $n \equiv 1, 2 (mod 4)$ the plane forces $n = a^{2} + c^{2}$ . For $n = 6 \equiv 2 (mod 4)$ : $6$ is not a sum of two squares, so no plane of order $6$ exists. Rubric: full credit for the sign computation, the reduction to $z^{2} + y^{2} = n x^{2}$ , the two-squares equivalence, and the $n = 6$ conclusion.

Exercise 8 (hard, symbolic).

Show that the dual of a symmetric $2 - (v, k, λ)$ design is again a symmetric $2 - (v, k, λ)$ design. Then explain why this fails for a non-symmetric $2$ -design.

Hint

The dual has incidence matrix $N^{⊤}$ . Compute $N^{⊤} (N^{⊤})^{⊤} = N^{⊤} N$ and use the symmetric-design identity. For the failure, note that $N^{⊤} N$ is not $(k - λ) I + λ J$ when $N$ is not square.

Answer

The dual structure has incidence matrix $N^{⊤}$ , with points and blocks swapped. Its concurrence matrix is $N^{⊤} (N^{⊤})^{⊤} = N^{⊤} N$ . For a symmetric design $N^{⊤} N = (k - λ) I + λ J$ (Exercise 3), which is the concurrence matrix of a $2 - (v, k, λ)$ design: the dual has $v$ points (the original blocks), block size $k$ (each original point lies in $k$ blocks, $r = k$ ), and any two dual points (original blocks) appear together in $λ$ dual blocks (original points), since two blocks meet in $λ$ points. So the dual is symmetric $2 - (v, k, λ)$ . For a non-symmetric design $N$ is $v \times b$ with $b > v$ (Fisher strict), $N^{⊤} N$ is a $b \times b$ matrix whose off-diagonal entries $∣ B_{i} \cap B_{j} ∣$ are not constant, so the dual is not a $2$ -design at all. Rubric: full credit for the dual concurrence computation, the parameter identification, and the explanation of the non-symmetric failure via non-constant block intersections.

Advanced results Master

The symmetric case sharpens every structural fact of the BIBD theory and adds an arithmetic obstruction absent in the general case. The results below trace the dual rigidity, the Bruck-Ryser-Chowla theorem and its proof architecture, the flagship nonexistence consequences, and the place of biplanes and Hadamard designs.

Theorem 1 (rigidity of the symmetric case). A symmetric $2 - (v, k, λ)$ design has $r = k$ , square nonsingular incidence matrix $N$ with $det N = \pm k (k - λ)^{(v - 1) /2}$ , and $N N^{⊤} = N^{⊤} N = (k - λ) I + λ J$ , so any two distinct blocks meet in exactly $λ$ points and the dual is a symmetric design with identical parameters. The order $n = k - λ$ is the repeated eigenvalue of the concurrence matrix, of multiplicity $v - 1$ ; the remaining eigenvalue is $k^{2}$ . The complement of a symmetric design is the symmetric $2 - (v, v - k, v - 2 k + λ)$ design ^{[van Lint-Wilson Ch. 19]}.

Theorem 2 (Bruck-Ryser-Chowla). A symmetric $2 - (v, k, λ)$ design with order $n = k - λ$ requires: for $v$ even, $n$ a perfect square; for $v$ odd, a nonzero integer solution of $z^{2} = n x^{2} + (- 1)^{(v - 1) /2} λ y^{2}$ . The proof reads the integral identity $N N^{⊤} = n I + λ J$ as a rational congruence $n I + λ J ≅ I_{v}$ of quadratic forms; Witt's theory and the Hasse-Minkowski local-global principle make this congruence solvable everywhere locally, and the explicit descent uses Lagrange's representation $n = a_{1}^{2} + \dots + a_{4}^{2}$ and Euler's four-square identity to collapse the form to the stated three-variable Diophantine equation ^{[Chowla-Ryser 1950]}. For $λ = 1$ this is the Bruck-Ryser projective-plane theorem ^{[Bruck-Ryser 1949]}.

Theorem 3 (nonexistence of the plane of order $6$ ). A projective plane of order $6$ would be a symmetric $2 - (43, 7, 1)$ design with $v = 43$ odd and $n = 6$ . The BRC equation $z^{2} = 6 x^{2} + y^{2}$ (sign $+ 1$ since $(v - 1) /2 = 21$ is odd, so $λ$ carries $- 1$ , giving $z^{2} = 6 x^{2} - y^{2}$ , equivalently $z^{2} + y^{2} = 6 x^{2}$ ) has no nonzero integer solution because $6$ is not a sum of two squares. Hence no plane of order $6$ exists. This recovers the impossibility of Euler's $36$ officers (a pair of orthogonal Latin squares of order $6$ ), since a complete set of mutually orthogonal Latin squares of order $n$ is equivalent to a projective plane of order $n$ ^{[Bruck-Ryser 1949]}.

Theorem 4 (the plane of order $10$ ). The order $n = 10 = 1^{2} + 3^{2}$ passes Bruck-Ryser-Chowla, so the theorem is silent about a $2 - (111, 11, 1)$ design. Lam, Thiel, and Swiercz proved by exhaustive computer search (1989) that no projective plane of order $10$ exists; the search reorganised the problem around the binary code spanned by the rows of the incidence matrix, a $[112, 56]$ self-dual code, and ruled out the existence of codewords of the small weights such a plane would force ^{[Lam-Thiel-Swiercz 1989]}. BRC is therefore a sieve, not a decision procedure: it is necessary, never sufficient.

Theorem 5 (biplanes). A biplane is a symmetric design with $λ = 2$ , parameters $2 - (1 + \frac{k ( k - 1 )}{2}, k, 2)$ . Biplanes are known only for $k \in {3, 4, 5, 6, 9, 11, 13}$ (orders $n = k - 2 \in {1, 2, 3, 4, 7, 9, 11}$ ), and the list is conjectured finite. BRC rules out infinitely many candidate $k$ ; for instance a biplane with $v$ even needs $k - 2$ a perfect square. The biplanes form the first family beyond projective planes ( $λ = 1$ ) where existence is genuinely sporadic ^{[Hughes-Piper Ch. 2]}.

Theorem 6 (Hadamard designs as symmetric designs). The symmetric $2 - (4 m - 1, 2 m - 1, m - 1)$ designs — the Hadamard designs — have order $n = (2 m - 1) - (m - 1) = m$ , and are equivalent to Hadamard matrices of order $4 m$ (40.06.05). For these, $v = 4 m - 1$ is odd and the BRC equation $z^{2} = m x^{2} + (- 1)^{2 m - 1} (m - 1) y^{2} = m x^{2} - (m - 1) y^{2}$ has the standard solution $(x, y, z) = (1, 1, 1)$ , so BRC never obstructs a Hadamard design — consistent with the Hadamard conjecture that one exists for every order $4 m$ .

Synthesis. Putting these together, the symmetric design is the foundational object where the linear algebra of 40.06.01 and the arithmetic of quadratic forms meet: the single identity $N N^{⊤} = N^{⊤} N = n I + λ J$ is exactly the dual rigidity (any two blocks meet in $λ$ points), is exactly the determinant relation $det N = \pm k n^{(v - 1) /2}$ , and is exactly the rational congruence $n I + λ J ≅ I$ that the Hasse-Minkowski principle converts into the Bruck-Ryser-Chowla Diophantine test. This is dual to the real-spectral reading that gave Fisher's inequality: the same concurrence matrix, read over $R$ for rank and over $Q_{p}$ for existence. The central insight is that combinatorial existence localises to arithmetic — the plane of order $6$ dies because $6$ is not a sum of two squares, while the plane of order $10$ survives the arithmetic and must be killed by computation, showing precisely where the arithmetic obstruction stops. The whole picture generalises Euler's thirty-six officers into a structural theorem, and it is dual to the coding-theoretic life of the incidence matrix, whose self-dual code carries the same nonexistence information that the order- $10$ search exploited.

Full proof set Master

Proposition 1 (symmetric block-intersection identity). In a symmetric design $N$ is square and nonsingular, $N J = J N = k J$ , and $N^{⊤} N = (k - λ) I + λ J$ ; any two distinct blocks meet in $λ$ points.

Proof. With $b = v$ , $N$ is $v \times v$ . By the BIBD identity (40.06.01) $N N^{⊤} = (r - λ) I + λ J = (k - λ) I + λ J$ , using $r = k$ . Its determinant $(k - λ)^{v - 1} k^{2} \neq = 0$ (since $k > λ$ and $k > 0$ ), so $N$ is invertible. From $N 1 = k 1$ and $1^{⊤} N = k 1^{⊤}$ , $N J = N 1 1^{⊤} = k 1 1^{⊤} = k J$ and similarly $J N = k J$ , so $N J = J N$ . Then $N^{⊤} N = N^{- 1} (N N^{⊤}) N = N^{- 1} ((k - λ) I + λ J) N = (k - λ) I + λ N^{- 1} J N = (k - λ) I + λ J$ , since $N^{- 1} J N = N^{- 1} (J N) = N^{- 1} (N J) = J$ . The $(i, j)$ entry of $N^{⊤} N$ is $∣ B_{i} \cap B_{j} ∣$ , equal to $k$ when $i = j$ and $λ$ otherwise. $□$

Proposition 2 (determinant and order). $det N = \pm k (k - λ)^{(v - 1) /2}$ , and the eigenvalues of the concurrence matrix are $k^{2}$ (once) and $n = k - λ$ (multiplicity $v - 1$ ).

Proof. The matrix $M = (k - λ) I + λ J$ acts on $1$ with eigenvalue $(k - λ) + λ v$ , and on $1^{⊥}$ (dimension $v - 1$ ) with eigenvalue $k - λ$ . For a symmetric design $λ (v - 1) = k (k - 1)$ , so $(k - λ) + λ v = k + λ (v - 1) = k + k (k - 1) = k^{2}$ . Hence $det (N N^{⊤}) = det M = k^{2} (k - λ)^{v - 1}$ . Since $det (N N^{⊤}) = (det N)^{2}$ and $det N$ is a real number, $det N = \pm k (k - λ)^{(v - 1) /2}$ . $□$

Proposition 3 (Bruck-Ryser-Chowla, $v$ even). If $v$ is even, $n = k - λ$ is a perfect square.

Proof. By Proposition 2, $det N = \pm k n^{(v - 1) /2}$ . As $N$ is an integer matrix, $det N \in Z$ . With $v$ even, $v - 1$ is odd, so $n^{(v - 1) /2} = n^{(v - 2) /2} n$ , an integer only if $n \in Z$ . Hence $n$ is a perfect square. (Equivalently, $n^{v - 1} k^{2}$ is a perfect square — being $(det N)^{2}$ — and $k^{2}$ is already square, so $n^{v - 1}$ is square; with $v - 1$ odd this forces $n$ square.) $□$

Proposition 4 (Bruck-Ryser-Chowla, $v$ odd). If $v$ is odd, the equation $z^{2} = n x^{2} + (- 1)^{(v - 1) /2} λ y^{2}$ has a nonzero integer solution.

Proof. The identity $N N^{⊤} = n I + λ J$ over $Z$ expresses, for the quadratic form $A (ξ) = ξ^{⊤} (n I + λ J) ξ$ , the equality $A (ξ) = (N^{⊤} ξ)^{⊤} (N^{⊤} ξ) = \sum_{i} η_{i}^{2}$ in the linear coordinates $η = N^{⊤} ξ$ . Thus $A$ and the identity form $I_{v}$ are congruent over $Q$ (the change of variables $N^{⊤}$ is rational and invertible). Two rationally congruent forms represent the same nonzero rationals; in particular they agree at every place, by the Hasse-Minkowski principle, so the Hasse invariants and discriminants match. Compute $det A = n^{v - 1} (n + v λ) = n^{v - 1} k^{2}$ , which equals $det I_{v} = 1$ modulo rational squares iff $n^{v - 1}$ is a square times the relevant factor; the discrepancy is recorded by the sign $(- 1)^{(v - 1) /2}$ .

For the explicit equation, write $n = a_{1}^{2} + a_{2}^{2} + a_{3}^{2} + a_{4}^{2}$ (Lagrange). Euler's four-square identity gives a rational orthogonal substitution under which $n (x_{1}^{2} + x_{2}^{2} + x_{3}^{2} + x_{4}^{2}) = w_{1}^{2} + w_{2}^{2} + w_{3}^{2} + w_{4}^{2}$ , each $w_{i}$ a rational linear form in $x_{1}, \dots, x_{4}$ . Group the $v$ variables of $A$ into $(v - 1) /4$ — handled by repeated quartets after first separating the form into the diagonal $n \sum x_{i}^{2}$ part and the rank-one $λ (\sum x_{i})^{2}$ part — reducing the congruence $A ≅ I_{v}$ to a relation among three remaining variables. Clearing denominators in the surviving rational identity produces a nonzero integer solution of $$ z^2 = n x^2 + (-1)^{(v-1)/2}\lambda y^2, $$ the sign being the parity factor from $det A / det I_{v}$ modulo squares. The solution is nonzero because the congruence is a genuine equality of forms, not the zero form. $□$

Proposition 5 (nonexistence of the order- $6$ plane). No symmetric $2 - (43, 7, 1)$ design exists.

Proof. Here $v = 43$ (odd), $k = 7$ , $λ = 1$ , $n = 6$ , and $(v - 1) /2 = 21$ is odd, so the sign is $- 1$ and BRC requires a nonzero solution of $z^{2} = 6 x^{2} - y^{2}$ , i.e. $z^{2} + y^{2} = 6 x^{2}$ . Suppose a nonzero integer solution exists; take one with $x^{2}$ minimal. Reducing $z^{2} + y^{2} = 6 x^{2}$ modulo $3$ gives $z^{2} + y^{2} \equiv 0 (mod 3)$ , and since $- 1$ is a non-residue modulo $3$ this forces $3 ∣ z$ and $3 ∣ y$ . Then $9 ∣ z^{2} + y^{2} = 6 x^{2}$ , so $3 ∣ 2 x^{2}$ , hence $3 ∣ x$ . Thus $(x /3, y /3, z /3)$ is a smaller nonzero solution, contradicting minimality. Hence no nonzero solution exists, BRC fails, and no $2 - (43, 7, 1)$ design exists. $□$

Proposition 6 (complement of a symmetric design). The complement of a symmetric $2 - (v, k, λ)$ design is the symmetric $2 - (v, v - k, v - 2 k + λ)$ design.

Proof. The complementary incidence matrix is $\overline{N} = J - N$ . Each complementary block has $v - k$ points. For two distinct points, the number of blocks containing neither is $b - 2 r + λ = v - 2 k + λ$ (inclusion-exclusion on the $b = v$ blocks, with $r = k$ ), and a block avoids both points iff its complement contains both; so the pair lies in $v - 2 k + λ$ complementary blocks. Since this count is constant and $\overline{N}$ has $b = v$ blocks on $v$ points, the complement is a symmetric $2 - (v, v - k, v - 2 k + λ)$ design, provided $v - 2 k + λ \geq 1$ . $□$

Connections Master

The symmetric design is the equality case $b = v$ of Fisher's inequality proved in 40.06.01: that unit supplies the concurrence identity $N N^{⊤} = (r - λ) I + λ J$ and the real-spectral reading that gives $b \geq v$ ; here the square case $r = k$ makes $N$ invertible, so $N^{⊤} N$ equals $N N^{⊤}$ , blocks meet in $λ$ points, and the same matrix — now read over $Q$ rather than $R$ — becomes the Bruck-Ryser-Chowla obstruction. The foundational reason existence localises to arithmetic is that the integral identity $n I + λ J = N N^{⊤}$ is a rational congruence of quadratic forms.
The co-produced unit 40.06.03 on projective planes is the $λ = 1$ specialisation: a projective plane of order $n$ is exactly a symmetric $2 - (n^{2} + n + 1, n + 1, 1)$ design, the duality of points and lines is the dual-design symmetry proved here, and the Bruck-Ryser theorem $z^{2} = n x^{2} + (- 1)^{(v - 1) /2} y^{2}$ is the plane-specific shadow of Theorem 2. That unit develops the geometry (collineations, coordinatisation, Desargues), while this one owns the matrix and arithmetic obstruction.
The Hadamard designs of 40.06.05 are the symmetric $2 - (4 m - 1, 2 m - 1, m - 1)$ family, equivalent to Hadamard matrices of order $4 m$ ; their BRC equation $z^{2} = m x^{2} - (m - 1) y^{2}$ always has the solution $(1, 1, 1)$ , so the arithmetic never obstructs them — the design-theoretic counterpart of the Hadamard conjecture. This is dual to the coding link: the rows of a symmetric design's incidence matrix span a self-dual binary code, and the nonexistence of the order- $10$ plane was settled through exactly such a $[112, 56]$ code, tying this unit to the bounds of the linear-codes unit 40.06.06.
The arithmetic engine of Bruck-Ryser-Chowla is the theory of rational quadratic forms and the Hasse-Minkowski local-global principle from number theory 21.04.03, together with Lagrange's four-square theorem; the residue class of the order $n$ modulo $4$ and its representability as a sum of two squares (the norm form of $Z [i]$ , 21.01.06) decide existence in the $λ = 1$ case, so a combinatorial impossibility is read off a purely number-theoretic fact.

Historical & philosophical context Master

The thread begins with Leonhard Euler, who in 1782 posed the thirty-six officers problem: arrange six regiments of six ranks in a $6 \times 6$ square so that each row and column contains one officer of each regiment and each rank, that is, a pair of orthogonal Latin squares of order $6$ . Euler conjectured no such arrangement exists for orders $n \equiv 2 (mod 4)$ ; Gaston Tarry confirmed the order- $6$ case by exhaustive hand enumeration in 1900. The geometric reformulation came later: a complete set of $n - 1$ mutually orthogonal Latin squares of order $n$ is equivalent to a projective plane of order $n$ , so Euler's impossibility is the nonexistence of a plane of order $6$ .

The decisive algebraic argument is due to Richard H. Bruck and Herbert J. Ryser in 1949 ^{[Bruck-Ryser 1949]}, who turned the incidence identity $N^{⊤} N = n I + J$ into a statement about which integers a rational quadratic form represents and proved that a plane of order $n \equiv 1, 2 (mod 4)$ requires $n$ to be a sum of two squares, killing order $6$ . Sarvadaman Chowla and Ryser extended the argument to all symmetric $2 - (v, k, λ)$ designs in 1950 ^{[Chowla-Ryser 1950]}, producing the perfect-square condition for even $v$ and the Diophantine condition for odd $v$ — the theorem now carrying all three names. The limit of the arithmetic method was exposed by order $10$ , which passes the test as $10 = 1^{2} + 3^{2}$ . Clement Lam, Larry Thiel, and Stanley Swiercz settled this case by an exhaustive computer search completed in 1989 ^{[Lam-Thiel-Swiercz 1989]}, organised around the binary code of the incidence matrix; Lam's 1991 account documents the scale of the computation and the coding-theoretic reductions that made it feasible ^{[Lam 1991]}.

Bibliography Master

@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{lamthielswiercz1989nonexistence,
  author  = {Lam, Clement W. H. and Thiel, Larry and Swiercz, Stanley},
  title   = {The nonexistence of finite projective planes of order 10},
  journal = {Canadian Journal of Mathematics},
  volume  = {41},
  pages   = {1117--1123},
  year    = {1989}
}

@article{lam1991search,
  author  = {Lam, Clement W. H.},
  title   = {The search for a finite projective plane of order 10},
  journal = {American Mathematical Monthly},
  volume  = {98},
  number  = {4},
  pages   = {305--318},
  year    = {1991}
}

@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}
}

@article{lam1991magic,
  author  = {Lam, Clement W. H.},
  title   = {How reliable is a computer-based proof?},
  journal = {The Mathematical Intelligencer},
  volume  = {12},
  pages   = {8--12},
  year    = {1990}
}

Prerequisites

40.06.01

Tier anchors

beginner: van Lint-Wilson 2001 *A Course in Combinatorics* 2e (Cambridge) Ch. 19 (symmetric designs by hand: equally many blocks and points, any two blocks meeting in the same number of points, the projective plane of order $n$ as the running example); Kirkman / Fano picture for the smallest case and the failed plane of order $6$ as the motivating impossibility
intermediate: van Lint-Wilson 2001 *A Course in Combinatorics* 2e (Cambridge) Ch. 19-20 (symmetric $2\text{-}(v,k,\lambda)$ designs with $b=v$, the dual design, $NN^\top = N^\top N = (k-\lambda)I + \lambda J$, the order $n = k-\lambda$, the Bruck-Ryser-Chowla theorem and the nonexistence of the projective plane of order $6$); Stinson 2004 *Combinatorial Designs* (Springer) Ch. 2
master: van Lint-Wilson 2001 *A Course in Combinatorics* 2e Ch. 19-20 (symmetric designs, the rational congruence of $NN^\top$, the Hasse-Minkowski reduction, the BRC Diophantine condition, biplanes, Hadamard designs); Lam-Thiel-Swiercz 1989 *Canad. J. Math.* 41 (the computer nonexistence of the projective plane of order 10); Bruck-Ryser 1949 *Canad. J. Math.* 1; Chowla-Ryser 1950 *Canad. J. Math.* 2; Hughes-Piper 1985 *Design Theory* (Cambridge) Ch. 2; Lam 1991 *Amer. Math. Monthly* 98 (the order-10 survey)

References

van Lint, J. H. & Wilson, R. M. — A Course in Combinatorics · Cambridge University Press, 2nd edition (2001). Chapters 19-20 develop symmetric 2-designs: a $2\text{-}(v,k,\lambda)$ design with $b=v$ equivalently $r=k$, the dual design, the block-intersection property that any two distinct blocks meet in exactly $\lambda$ points, the identities $NN^\top = N^\top N = (k-\lambda)I + \lambda J$ and $\det N = \pm k(k-\lambda)^{(v-1)/2}$, the order $n = k-\lambda$, the Bruck-Ryser-Chowla theorem via the rational equivalence of the form $(k-\lambda)x^\top x + \lambda(\mathbf 1^\top x)^2$ to the identity form and the Lagrange four-square / Hasse-Minkowski argument, the resulting nonexistence of a projective plane of order $6$, and biplanes.
Bruck, R. H. & Ryser, H. J. — The nonexistence of certain finite projective planes · Canadian Journal of Mathematics 1 (1949), 88-93. The original argument that a projective plane of order $n \equiv 1, 2 \pmod 4$ cannot exist unless $n$ is a sum of two integer squares; the case $n=6$ is excluded, settling Euler's thirty-six officers in the plane formulation. The proof manipulates the matrix identity $N^\top N = nI + \lambda J$ into a statement about which integers the diagonal quadratic form represents, then uses a descent on a four-variable substitution.
Chowla, S. & Ryser, H. J. — Combinatorial problems · Canadian Journal of Mathematics 2 (1950), 93-99. The extension of the Bruck-Ryser nonexistence argument from projective planes ($\lambda=1$) to all symmetric $2\text{-}(v,k,\lambda)$ designs: for $v$ even, $k-\lambda$ must be a perfect square; for $v$ odd, the equation $z^2 = (k-\lambda)x^2 + (-1)^{(v-1)/2}\lambda y^2$ must have a nonzero integer solution. The full Bruck-Ryser-Chowla theorem.
Lam, C. W. H., Thiel, L. & Swiercz, S. — The nonexistence of finite projective planes of order 10 · Canadian Journal of Mathematics 41 (1989), 1117-1123. The computer-assisted proof, after years of exhaustive search organised around the weight enumerator of the associated $[112,56]$ binary code, that no projective plane of order $10$ exists — an order that passes the Bruck-Ryser-Chowla test ($10 = 1^2 + 3^2$) yet admits no design.
Hughes, D. R. & Piper, F. C. — Design Theory · Cambridge University Press (1985). Chapter 2 treats symmetric designs abstractly: the dual design and polarities, the block-intersection number, the standard equations, the Bruck-Ryser-Chowla theorem, the embedding of residual into symmetric designs, and biplanes.
Lam, C. W. H. — The search for a finite projective plane of order 10 · American Mathematical Monthly 98 (1991), 305-318. An expository account of the order-10 search: how Bruck-Ryser-Chowla fails to rule out order 10, how the existence question was reduced to coding-theoretic constraints on the codewords of small weight, and the scale of the eventual computation.

Estimated time

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