Fisher's Inequality

Theorem

For any BIBD $\left({v, k, \lambda}\right)$, 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^T \cdot A = \begin{bmatrix} r & \lambda & \cdots & \lambda \\ \lambda & r & \cdots & \lambda \\ \vdots & \vdots & \ddots & \vdots \\ \lambda & \lambda & \cdots & r \\ \end{bmatrix}$

Using Necessary Condition For The Existence of a BIBD, we have that $r > \lambda$.

So we can write $r = \lambda + \mu$ and so:

$A^T \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:

	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \det \left({A^T\cdot A}\right)\)	\(=\)	\(\displaystyle \mu^{v-1} \left ({\mu + v \lambda}\right)\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	from Determinant of Combinatorial Matrix
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle \left ({r + \left({v-1}\right) \lambda}\right) \left({r - \lambda}\right)^{v-1}\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle r k \left({r - \lambda}\right)^{v-1}\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	by Necessary Condition For The Existence of a BIBD

Now, since $k < v$ (this is obvious) and using the properties of a BIBD, we get that $r>\lambda$.

So $\det(A^TA) \ne 0$.

Since $A^TA$ is a $v\times v$ matrix, then the rank, $\rho$, of $A^TA=v$.

Using the facts that $\rho(A^TA)\leq\rho(A)$, and $\rho(A)\leq b$ (since A only has b cols), then $v\leq\rho(A)\leq b$.

$\blacksquare$

Source of Name

This entry was named for Ronald Aylmer Fisher.