Skip to main content

Section 17.2 Fisher's Inequality

There is one more important inequality that is not at all obvious, but is necessary for the existence of a BIBD\((v,k,\lambda)\text{.}\) This is known as Fisher's Inequality, since it was proven by Sir Ronald Aylmer Fisher (1890—1962). The standard proof of this theorem uses linear algebra, but Math 3410 is not a prerequisite for this course, so we will also give a (much longer) proof that does not require this background.

Before proving this fact, let's observe the consequences in terms of the usual parameters: \(v\text{,}\) \(k\text{,}\) and \(\lambda\text{.}\) We know from Equation (17.1.2) that

\begin{equation*} b=\frac{\lambda v(v-1)}{k(k-1)}\text{,} \end{equation*}

so \(b \ge v\) implies

\begin{equation*} \frac{\lambda v(v-1)}{k(k-1)}\ge v\text{.} \end{equation*}

Since \(v\) is the number of points of a design, it must be positive, so dividing through by \(v\) does not reverse the inequality. Thus,

\begin{equation*} \frac{\lambda (v-1)}{k(k-1)}\ge 1\text{.} \end{equation*}

Since \(k\) is the number of points in each block, both \(k\) and \(k-1\) must be positive (we are ignoring the trivial case \(k=1\)), so multiplying through by \(k(k-1)\) does not reverse the inequality. Thus,

\begin{equation*} \lambda (v-1) \ge k(k-1)\text{.} \end{equation*}
Let \(A\) be the adjacency matrix of the BIBD:

  • This is a \(v \times b\) matrix of \(0\)s and \(1\)s.

  • To construct it, number the points \(x_1, x_2,\ldots,x_v\) and the blocks \(B_1,B_2,\ldots,B_b\text{.}\)

  • The \((i,j)\)-entry of \(A\) tells us whether \(x_i\) is in \(B_j\text{:}\) the entry is \(1\) if \(x_i \in B_j\text{;}\) otherwise, it is \(0\text{.}\)

Then \(A \, A^T\) is a \(v \times v\) matrix with \(r\) on the diagonal and \(\lambda\) everywhere else.

It can be shown (by induction) that the determinant of \(A\) is
\begin{equation*} (r-\lambda)^{v-1} \bigl( r + \lambda(v-1) \bigr) . \end{equation*}
Since \(k < v\text{,}\) the formula \(r(k-1) = \lambda(v-1)\) implies \(r > \lambda\text{,}\) so the determinant is not \(0\text{.}\)

To complete the proof, we will use linear algebra (Math 3410). Since its determinant is nonzero, the matrix \(A A^T\) is invertible, which implies that the rank of \(A A^T\) is \(v\text{.}\) Therefore, the rank of \(A\) must be at least \(v\text{.}\) Since \(A\) is a \(v \times b\) matrix (and the rank of a matrix cannot be more than the number of columns), this implies that \(b \ge v\text{.}\)
⬛

Suppose we have an arbitrary BIBD\((v,k,\lambda)\text{.}\) Let \(B\) be an arbitrary block of this design. For each value of \(i\) between \(0\) and \(k\) (inclusive), let \(n_i\) denote the number of blocks \(B'\neq B\) such that \(|B'\cap B|=i\text{.}\) (When we say \(B' \neq B\) we allow the blocks to be equal as sets if the block \(B\) is a repeated block of the design; we are only insisting that \(B'\) not be the exact same block of the design as \(B\text{.}\))

The following equations involving \(n_i\) are consequences of easy combinatorial proofs, together with the definition of \(n_i\text{:}\)

\begin{equation} \sum_{i=0}^k n_i = b-1\text{,}\label{eqn_Fisher1}\tag{17.2.1} \end{equation}

because both sides of this equation count every block except \(B\text{.}\)

\begin{equation} \sum_{i=0}^k in_i = k(r-1)\text{,}\label{eqn_Fisher2}\tag{17.2.2} \end{equation}

because both sides of this equation count the number of times elements of \(B\) appear in some other block of the design.

\begin{equation*} \sum_{i=2}^k i(i-1)n_i =k(k-1)(\lambda-1)\text{,} \end{equation*}

because both sides of this equation count the number of times all of the ordered pairs of elements from \(B\) appear together in some other block of the design. Note that when \(i=0\) or \(i=1\text{,}\) we have \(i(i-1)n_i=0\text{,}\) so in fact

\begin{equation} \sum_{i=0}^k i(i-1)n_i =\sum_{i=2}^k i(i-1)n_i =k(k-1)(\lambda-1)\text{.}\label{eqn_Fisher3}\tag{17.2.3} \end{equation}

Adding Equations (17.2.2) and (17.2.3) gives

\begin{equation} \sum_{i=0}^k i^2n_i = k(k-1)(\lambda-1)+k(r-1)\text{.}\label{eqn_Fisher4}\tag{17.2.4} \end{equation}

Now comes the part of the proof where something mysterious happens, and for reasons that are not at all apparent, the result we want will emerge. To fully understand a proof like this one requires deeper mathematics, but even seeing a proof is useful to convince ourselves that the result is true.

Take the polynomial in \(x\) given by

\begin{equation*} \sum_{i=0}^k (x-i)^2 n_i = \sum_{i=0}^k (x^2-2xi+i^2)n_i= x^2\sum_{i=0}^k n_i-2x\sum_{i=0}^k in_i+\sum_{i=0}^k i^2n_i\text{.} \end{equation*}

Using Equations (17.2.1),  (17.2.2), and (17.2.4), we see that this is equal to

\begin{equation*} x^2(b-1)-2xk(r-1)+k(k-1)(\lambda-1)+k(r-1)\text{.} \end{equation*}

Notice that the format in which this polynomial started was a sum of squares times non-negative integers, so its value must be non-negative for any \(x \in \mathbb R\text{.}\)

Using the quadratic formula, \(ax^2+b'x+c=0\) has roots at

\begin{equation*} \frac{-b'\pm\sqrt{(b')^2-4ac}}{2a}\text{.} \end{equation*}

If a quadratic polynomial has two real roots, then there is a region in which its values are negative. Since this polynomial is non-negative for every \(x \in \mathbb R\text{,}\) it can have at most one real root, so \((b')^2-4ac \le 0\text{.}\) Substituting the actual values from our polynomial, this means that

\begin{equation*} (-2k(r-1))^2-4(b-1)(k(k-1)(\lambda-1)+k(r-1)) \le 0\text{.} \end{equation*}

Hence,

\begin{equation*} k^2(r-1)^2-k(b-1)((k-1)(\lambda-1)+r-1) \le 0\text{.} \end{equation*}

Let's rewrite the \(b\) in terms of \(v, r\text{,}\) and \(k\text{.}\) By Theorem 17.1.7, we have \(bk=vr\text{,}\) so

\begin{equation*} k(b-1)=bk-k=vr-k\text{.} \end{equation*}

Hence

\begin{equation*} k^2(r-1)^2-(vr-k)((k-1)(\lambda-1)+r-1) \le 0\text{.} \end{equation*}

Expand the second term slightly, and multiply both sides of the inequality by \(v-1\text{:}\)

\begin{equation*} k^2(r-1)^2(v-1)-(vr-k)(k-1)(\lambda-1)(v-1)-(vr-k)(r-1)(v-1) \le 0\text{.} \end{equation*}

In the middle expression, we have \((\lambda-1)(v-1)\text{.}\) By Theorem 17.1.7, we know that \(\lambda=r(k-1)/(v-1)\text{,}\) so

\begin{equation*} \lambda-1=\frac{r(k-1)-(v-1)}{v-1}\text{.} \end{equation*}

Therefore,

\begin{equation*} (\lambda-1)(v-1)=r(k-1)-v+1\text{.} \end{equation*}

Thus, we have

\begin{equation*} k^2(r-1)^2(v-1)-(vr-k)(k-1)(rk-r-v+1)-(vr-k)(r-1)(v-1) \le 0\text{.} \end{equation*}

The next step is a lot of work to do by hand. Fortunately there is good math software that can perform routine tasks like this quickly. If we expand this inequality fully, remarkably it has a nice factorisation:

\begin{equation*} r(k-r)(v-k)^2 \le 0\text{.} \end{equation*}

Now, \(r >0\) for any design, and \((v-k)^2\) is a square, so must be nonnegative. Therefore, this inequality forces \(k-r \le 0\text{,}\) so \(k \le r\text{.}\) Hence \(r/k\ge 1\text{.}\) Using Theorem 17.1.7, we have

\begin{equation*} b=vr/k\ge v\text{,} \end{equation*}

as desired.

⬛

  1. Find values for \(v\text{,}\) \(k\) and \(\lambda\) that satisfy Theorem 17.1.9 but do not satisfy Fisher's Inequality. What can you say about the existence of a design with these parameters?

  2. Suppose that \(\lambda=1\) and \(k=20\text{.}\) How big must \(v\) be to satisfy Fisher's Inequality? What is the smallest value for \(v\) that satisfies all of the necessary conditions?

  3. Suppose that \(\lambda=2\) and \(k=20\text{.}\) How big must \(v\) be to satisfy Fisher's Inequality? What is the smallest value for \(v\) that satisfies all of the necessary conditions?

  4. Explain how you know there does not exist a BIBD with \(v = 46\text{,}\) \(b = 23\text{,}\) and \(k = 10\text{.}\)

  5. Explain how you know there does not exist a BIBD with \(v = 8\text{,}\) \(b = 10\text{,}\) \(k = 4\text{,}\) and \(r = 5\text{.}\)

  6. If \(\bibd\) is a BIBD with \(v = 22\text{,}\) then what can you say about the value of \(b\text{?}\)