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

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s