**Problem**. (Fisher’s inequality) Suppose that are distinct subsets of Prove that if there exists such that for all then

**Solution**. Define the matrix by

Let be the -th column of Clearly every entry in is either one or zero and the number of ones in every is equal to Thus for every

and for all

Now, suppose, to the contrary, that Then will be linearly dependent over because these vectors are in So, there exist such that for some and

Squaring both sides of (3) give us

Thus by (2), which gives us

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

We know that not all are zero. Now, the second relation in (5) tells us that at least two of are non-zero. So suppose and Then the first relation in (5) gives us Thus, by (1) and (2), which implies This is a contradiction because are assumed to be distinct. This contradiction proves that