Combinatorial Designs - Main Theorem

Fisher's Inequality provides a fundamental lower bound on the number of blocks in balanced designs, revealing deep structure in symmetric designs.

Proof:

Let $M$ be the $v \times b$ incidence matrix where $M_{ij} = 1$ if point $i$ is in block $j$, and $M_{ij} = 0$ otherwise.

Consider the product $MM^T$ (a $v \times v$ matrix):

$(MM^T)_{ii}$ counts the number of blocks containing point $i$, which equals $r$ for all $i$ by definition.

For $i \neq j$, $(MM^T)_{ij}$ counts the number of blocks containing both points $i$ and $j$, which equals $\lambda$ by the balanced property.

Therefore: $MM^T = (r-\lambda)I + \lambda J$

where $I$ is the identity matrix and $J$ is the all-ones matrix.

Computing the determinant:

We have $\det(MM^T) = \det(M) \det(M^T) = \det(M)^2 \geq 0$.

To find $\det((r-\lambda)I + \lambda J)$, note that $J$ has rank 1 with eigenvector $(1,1,\ldots,1)^T$ (eigenvalue $v$) and $v-1$ eigenvectors orthogonal to it (eigenvalue 0).

For $(r-\lambda)I + \lambda J$:

• Eigenvector $(1,1,\ldots,1)^T$ has eigenvalue $r-\lambda + \lambda v = r + \lambda(v-1) = rk$ (using $\lambda(v-1) = r(k-1)$)
• Other $v-1$ eigenvectors have eigenvalue $r-\lambda$

Therefore: $\det(MM^T) = rk \cdot (r-\lambda)^{v-1}$

Key observation: Since $M$ has rank at most $\min(v,b)$ and $MM^T$ is $v \times v$, if $\det(MM^T) \neq 0$, then $M$ has rank $v$. This requires $b \geq v$.

Since $v > k$, we have $r > \lambda$ (from $r(k-1) = \lambda(v-1)$ and $k < v$), so $r - \lambda > 0$.

Also, $r > 0$ and $k > 0$, so $\det(MM^T) > 0$, implying $M$ has full rank $v$.

Therefore, $b \geq v$. $\square$

Equality case:

If $b = v$, then $M$ is a $v \times v$ matrix with $\det(M) \neq 0$, so $M$ is invertible. The design is symmetric, and one can show that any two blocks intersect in exactly $\lambda$ points by analyzing $M^TM$.