9 Designs 9.1 Examples and basic properties 9.3 Finite linear spaces

9.2 Fisher’s inequality for designs

Here is one of the original motivations for Fisher’s inequality (Theorem 8.12) and sometimes known as Fisher’s inequality too.

Proposition 9.9.

For a $(v,k,\lambda)$ -design with $b$ blocks and $v>k$ we have $b\geq v$ .

In case of $k=v$ , we have $b=1$ and so the inequality fails.

Proof.

Let $B_{1},\ldots,B_{b}$ be the blocks. Consider the sets $S_{p}=\{i:p\in B_{i}\}$ . $S_{p}$ are $r$ -sets of $[b]$ . Furthermore $S_{p}\cap S_{q}$ is of cardinality exactly $\lambda$ for $p\neq q$ . Since $v>k$ , $r>\lambda$ by the replication number identity and so $S_{p}\neq S_{q}$ for $p\neq q$ . Thus $S_{p}$ ’s are distinct and so by Fisher’s inequality, $v\leq b$ . ∎

Proof.

Here is a matrix-theoretic proof of the proposition. For a design introduce the $v\times b$ -incidence matrix $N$ by $N(p,B)=\mathbf{1}[p\in B]$ . Observe that $NN^{T}$ has entries $r$ on diagonal and $\lambda$ elsewhere. So $NN^{T}=(r-\lambda)I+\lambda J$ .

Since $v>k$ , again $r>\lambda$ . $J$ has one eigenvalue $v$ and the rest $0$ . So $NN^{T}$ has $v-1$ eigenvalues $r-\lambda$ and one eigenvalues $(r-\lambda)+\lambda v=rk$ by replication number identity again. Thus $det(NN^{T})=(r-\lambda)^{v-1}rk\neq 0$ and so $N$ has rank $v$ . Thus the column rank of $N$ is also $v$ and so $b\geq v$ ∎

In the above proof, it is easy to see the following: If $b=v$ and $v$ is even, then $N$ is square matrix and $r=k$ . So

det(N)^{2}=det(NN^{T})=(k-\lambda)^{v-1}k^{2},

and hence $k-\lambda$ is a square.