A combinatorial question on Steiner systems from book of Dixon-Mortimer

43 Views Asked by At

Let $S(t,k,v)$ be a Steiner system.

[Means: we have a set $S=\{\alpha_1,\alpha_2,\ldots,\}$ with $v$ elements, some blocks($\equiv$subsets of $S$) $B_1,B_2,\ldots$ of size $k$, such that, every subset of $S$ of size $t$ is in unique $B_i$.]

Assume: Each element of $S$ lies in exactly $r$ blocks $B_i$.

Let $A$ be the incidence matrix of this system: $(i,j)$-th enetry is $$\langle \alpha_i, B_j\rangle=\begin{cases} 1 & \mbox{ if } \alpha_i\in B_j \\ 0 & \mbox{ otherwise} \end{cases}.$$ Problem: Show that $AA^t$ is ($v\times v$) matrix with diagonal entries $r$ and non-diagonal entries $1$.

What I did:

$$(AA^t)_{ij}= \sum_k A_{ik} (A^t)_{kj} = \sum_k \langle \alpha_i, B_k\rangle \cdot \langle \alpha_j, B_k\rangle.$$
So, if $i=j$, then, by assumption, there are exactly $r$ many blocks which contains $\alpha_i=\alpha_j$, so diagonal entry of $AA^t$ is $r$.

What about non-diagonal entries? For example, why $\alpha_1,\alpha_2$ can not be in more than one blocks (unless we have a Steiner system $S(2,k,v)$?)


Ref: Permutation Groups: Dixon and Mortimer, Theorem $6.2$A (p. $180$-$181$)