## Fisher’s inequality

Posted: February 19, 2011 in Elementary Algebra; Problems & Solutions, Linear Algebra
Tags:

Problem. (Fisher’s inequality) Suppose that $S_1, S_2, \cdots , S_m$ are distinct subsets of $\{1,2, \cdots , n \}.$ Prove that if there exists $1 \leq k < n$ such that $|S_i \cap S_j|=k$ for all $i \neq j,$ then $m \leq n.$

Solution. Define the $n \times m$ matrix $A=[a_{ij}]$ by

$a_{ij}=\begin{cases}1 & \text{if} \ i \in S_j \\ 0 & \text{if} \ i \notin S_j \end{cases}.$

Let $\bold{x}_j \in \mathbb{R}^n, \ 1 \leq j \leq m,$ be the $j$-th column of $A.$ Clearly every entry in $\bold{x}_j$ is either one or zero and the number of ones in every $\bold{x}_j$ is equal to $|S_j|.$ Thus for every $1 \leq j \leq m$

$||\bold{x}_j||^2=\bold{x}_j \cdot \bold{x}_j = |S_j| \geq k \ \ \ \ \ \ \ \ \ \ \ (1)$

and for all $i \neq j$

$\bold{x}_i \cdot \bold{x}_j = |S_i \cap S_j|=k. \ \ \ \ \ \ \ \ \ \ \ \ \ (2)$

Now, suppose, to the contrary, that $m > n.$ Then $\{\bold{x}_1, \cdots , \bold{x}_m \}$ will be linearly dependent over $\mathbb{R}$ because these vectors are in $\mathbb{R}^n.$ So, there exist $r_1, \cdots, r_m \in \mathbb{R}$ such that $r_j \neq 0$ for some $1 \leq j \leq m$ and

$r_1 \bold{x}_1 + \cdots + r_m \bold{x}_m=\bold{0}. \ \ \ \ \ \ \ \ \ \ \ \ \ \ (3)$

Squaring both sides of (3) give us

$\sum_{j=1}^m r_j^2 ||\bold{x}_j||^2 + 2 \sum_{i \neq j} r_ir_j \bold{x}_i \cdot \bold{x}_j = 0.$

Thus by (2), $\sum_{j=1}^m r_j^2|| \bold{x}_j||^2 + 2k \sum_{i \neq j}r_ir_j=0,$ which gives us

$\sum_{j=1}^m r_j^2(||\bold{x}_j||^2 - k) + k \left (\sum_{j=1}^m r_j \right)^2=0. \ \ \ \ \ \ \ \ \ \ \ \ (4)$

By (1), each term in (4) is non-negative and so they add up to zero if and only if each of them is zero. Hence

$r_j(||\bold{x}_j||^2 - k)=0, \ \forall \ j, \ \ \sum_{j=1}^m r_j = 0. \ \ \ \ \ \ \ \ \ \ \ \ (5)$

We know that not all $r_j$ are zero. Now, the second relation in (5) tells us that at least two of $r_j$ are non-zero. So suppose $r_u \neq 0$ and $r_v \neq 0.$ Then the first relation in (5) gives us $||\bold{x}_u||^2=||\bold{x}_v||^2=k.$ Thus, by (1) and (2), $|S_u|=|S_v|=|S_u \cap S_v|,$ which implies $S_u=S_v.$ This is a contradiction because $S_1, \cdots , S_m$ are assumed to be distinct. This contradiction proves that $m \leq n. \ \Box$