Fisher's Inequality
Theorem
For any BIBD $\struct {v, k, \lambda}$, the number of blocks $b$ must be greater then or equal to the number of points $v$:
- $ b \ge v$
Proof
Let $A$ be the incidence matrix.
By Product of the Incidence Matrix of a BIBD with its Transpose, we have that:
- $A^\intercal \cdot A = \begin{bmatrix} r & \lambda & \cdots & \lambda \\ \lambda & r & \cdots & \lambda \\ \vdots & \vdots & \ddots & \vdots \\ \lambda & \lambda & \cdots & r \\ \end{bmatrix}$
From Necessary Condition for Existence of BIBD:
- $r > \lambda$
So we can write $r = \lambda + \mu$ for some $\mu > 0$ and so:
- $A^\intercal \cdot A = \begin{bmatrix} \lambda + \mu & \lambda & \cdots & \lambda \\ \lambda & \lambda + \mu & \cdots & \lambda \\ \vdots & \vdots & \ddots & \vdots \\ \lambda & \lambda & \cdots & \lambda + \mu \\ \end{bmatrix}$
This is a combinatorial matrix of order $v$.
So:
\(\ds \map \det {A^\intercal \cdot A}\) | \(=\) | \(\ds \mu^{v - 1} \paren {\mu + v \lambda}\) | Determinant of Combinatorial Matrix | |||||||||||
\(\ds \) | \(=\) | \(\ds \paren {r + \paren {v - 1} \lambda} \paren {r - \lambda}^{v - 1}\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds r k \paren {r - \lambda}^{v - 1}\) | Necessary Condition for Existence of BIBD |
Now, since $k < v$ (this is obvious) and using the properties of a BIBD, we get that $r > \lambda$.
So $\map \det {A^\intercal A} \ne 0$.
Since $A^\intercal A$ is a $v \times v$ matrix, then the rank, $\rho$, of $A^\intercal A = v$.
Using the facts that $\map \rho {A^\intercal A} \le \map \rho A$, and $\map \rho A \le b$ (since $A$ only has $b$ cols), we have that:
- $v \le \map \rho A \le b$
$\blacksquare$
Source of Name
This entry was named for Ronald Aylmer Fisher.