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