The Incidence Matrix of a Balanced Incomplete Block Design

The Incidence Matrix of a Balanced Incomplete Block Design

We will now look at one way to describe the information in a BIBD by putting it in matrix form.

Definition: Let $(X, \mathcal A)$ by a $(v, b, r, k, \lambda)$-BIBD where $X = \{ x_1, x_2, ..., x_v \}$ and $\mathcal A = \{ A_1, A_2, ..., A_b \}$. The Incidence Matrix of this BIBD is the $v \times b$ matrix $M$ whose entries $m_{ij}$ are defined as $\displaystyle{m_{ij} = \left\{\begin{matrix} 0 \: \mathrm{if} \: x_i \not \in A_j \\ 1 \: \mathrm{if} \: x_i \in A_j \end{matrix}\right.}$.

In other words, the incidence matrix of a $(v, b, r, k, \lambda)$-BIBD is a matrix containing $v$ rows (each row representing a point) $]], and $b$ columns (each column representing a block), where the entry in row $i$ column $j$ is $0$ if the point $x_i$ not contained in the block $A_j$, and where the entry in row $i$ column $j$ is $1$ if the point $x_i$ is contained in the block $A_j$. Thus $M$ tells us which points of $X$ are contained in which blocks of $\mathcal A$.

For example, recall that if $X = \{ 1, 2, 3, 4, 5, 6, 7 \}$ and $\mathcal A = \{ \{ 1, 2, 3 \}, \{ 3, 4, 5 \}, \{ 5, 6, 1 \}, \{1, 7, 4 \}, \{ 2, 7, 5 \}, \{ 3, 7, 6 \}, \{ 2, 4, 6 \} \}$ then $(X, \mathcal A)$ is a $(7, 3, 1)$-BIBD representing the Fano plane. From The Replication Number of a Balanced Incomplete Block Design and The Block Number of a Balanced Incomplete Block Design we can compute $r$ and $b$ to be:

(1)
\begin{align} \quad r = \frac{\lambda (v - 1)}{k - 1} = \frac{1(7 - 1)}{3 - 1} = \frac{6}{2} = 3 \end{align}
(2)
\begin{align} \quad b = \frac{\lambda (v^2 - v)}{k^2 - k} = \frac{1(7^2 - 7)}{3^2 - 3} = \frac{49 - 7}{9 - 3} = \frac{42}{6} = 7 \end{align}

So the Fano plane is more descriptively a $(7, 7, 3, 3, 1)$-BIBD. The incidence matrix of this BIBD is:

(3)
\begin{align} \quad M = \begin{bmatrix} 1 & 0 & 1 & 1 & 0 & 0 & 0\\ 1 & 0 & 0 & 0 & 1 & 0 & 1\\ 1 & 1 & 0 & 0 & 0 & 1 & 0\\ 0 & 1 & 0 & 1 & 0 & 0 & 1\\ 0 & 1 & 1 & 0 & 1 & 0 & 0\\ 0 & 0 & 1 & 0 & 0 & 1 & 1\\ 0 & 0 & 0 & 1 & 1 & 1 & 0 \end{bmatrix} \end{align}

Also recall that if $X = \{ 1, 2, 3, 4, 5 \}$ and is $\mathcal A$ is the collection of all $3$-element subsets of $X$, i.e., $\mathcal A = \{ \{ 1, 2, 3 \}, \{ 1, 2, 4 \}, \{ 1, 2, 5 \}, \{ 1, 3, 4\}, \{ 1, 3, 5 \}, \{ 1, 4, 5 \}, \{ 2, 3, 4 \}, \{2, 3, 5 \}, \{2, 4, 5\}, \{ 3, 4, 5 \} \}$, then $(X, \mathcal A)$ is a $(5, 3, 3)$-BIBD and we computed $r = 6$ and $b = 10$ so this is more descriptively a $(5, 10, 6, 3, 3)$-BIBD. The incidence matrix of this BIBD is:

(4)
\begin{align} \quad M = \begin{bmatrix} 1 & 1 & 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0\\ 1 & 1 & 1 & 0 & 0 & 0 & 1 & 1 & 1 & 0\\ 1 & 0 & 0 & 1 & 1 & 0 & 1 & 1 & 0 & 1\\ 0 & 1 & 0 & 1 & 0 & 1 & 1 & 0 & 1 & 1\\ 0 & 0 & 1 & 0 & 1 & 1 & 0 & 1 & 1 & 1 \end{bmatrix} \end{align}

It is important to note that the incidence matrix of a BIBD can vary depending how we label the points in $X$ and the blocks in $\mathcal A$. Therefore, it is often important to make the labelling of the points and blocks in a BIBD clear when discussing incidence matrices of BIBDs.

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License