Product of the Incidence Matrix of a BIBD with its Transpose

Theorem

For any BIBD with parameters $v,k,\lambda$, let $A$ be its block incidence matrix.

Then:

$A^T \cdot A = \left({a_{ij}}\right) = \left({r - \lambda}\right) I_v + \lambda J_v$

where:

• $A$ is $v\times b$,
• $A^T$ is the transpose of $A$,
• $J_v$ is the all $v\times{v}$ $ 1$'s matrix, and
• $I_v$ is the $v\times{v}$ identity matrix.

That is:

$A^T\cdot A = \begin{bmatrix} r & \lambda & \cdots & \lambda \\ \lambda & r & \cdots & \lambda \\ \vdots & \vdots & \ddots & \vdots \\ \lambda & \lambda & \cdots & r \\ \end{bmatrix}$

Proof

• Consider multiplying $i^{th}$ row of $A$ by the $i^{th}$ column of $A^T$.

This is the same as multiplying the $i^{th}$ row of $A$ by the $i^{th}$ row of $A$.

We know that each row of $A$ has $r$ enteries (since any point must be in $r$ blocks), then:

$ (a_{ii})= r =\sum $ of the all the $1$'s in row $i$

This completes the main diagonal.

• Consider multiplying $i^{th}$ row of $A$ by the $j^{th}$ column of $A^T$.

This is the same as multiplying the $i^{th}$ row of $A$ by the $j^{th}$ row of $A$.

This will give the number of times the $i^{th}$ point is the same block as the $j^{th}$ point.

Therefore:

$i \neq j \implies (a_{ij}) = \lambda$

So:

$A^T \cdot A = (a_{ij})=(r-\lambda)I_v+\lambda{J_v}$

$\blacksquare$