The Existence of Balanced Incomplete Block Designs
On The Replication Number of a Balanced Incomplete Block Design page we defined the replication number $r$ of a $(v, k, \lambda)$-BIBD to be the number of blocks containing any arbitrary point and we derived the formula:
(1)On The Block Number of a Balanced Incomplete Block Design page we defined the block number $b$ of a $(v, k, \lambda)$-BIBD to be the number of blocks in the block design and we derived the formula:
(2)The numbers $r$ and $b$ are so important that we sometimes refer a $(v, k, \lambda)$-BIBD as a $(v, b, r, k, \lambda)$-BIBD.
Furthermore, we note that $r$ and $b$ are always positive integers. As a nice consequence of the formulas for $r$ and $b$ we obtain a couple of necessary conditions for the existence of a $(v, k, \lambda)$-BIBD.
| Theorem 1: If $(X, \mathcal A)$ is a $(v, k, \lambda)$-BIBD then $\lambda (v - 1)$ is divisible by $k - 1$ and $\lambda (v^2 - v)$ is divisible by $k^2 - k$. |
Equivalently, Theorem 1 can be reworded as follows: If $(X, \mathcal A)$ is a $(v, k, \lambda)$-BIBD then $\lambda (v - 1) \equiv 0 \pmod {k - 1}$ and $\lambda (v^2 - v) \equiv 0 \pmod {k^2 - k}$ where we recall that the notation "$a \equiv b \pmod m$" means that $m$ divides $a - b$.
- Proof: Since $(X, \mathcal A)$ is a $(v, k, \lambda)$-BIBD, we have that the replication number $r$ for this BIBD is given by $\displaystyle{r = \frac{\lambda (v - 1)}{k - 1}}$. Since $r$ is a positive integer, this means that $\displaystyle{ \frac{\lambda (v - 1)}{k - 1}}$ is a positive integer, so $\lambda (v - 1)$ is divisible by $k - 1$.
- Similarly, we have that the block number $b$ for this BIBD is given by $\displaystyle{b = \frac{\lambda (v^2 - v)}{k^2 - k}}$. Since $b$ is a positive integer, this means that $\displaystyle{\frac{\lambda (v^2 - v)}{k^2 - k}}$ is a positive integer, so $\lambda (v^2 - v)$ is divisble by $k^2 - k$. $\blacksquare$