A fundamental matrix equation for finite sets

Abstract:

Let $S = \{ {x_1},{x_2}, \cdots ,{x_n}\}$ be an n-set and let ${S_1},{S_2}, \cdots ,{S_m}$ be subsets of S. Let A of size m by n be the incidence matrix for these subsets of S. We now regard ${x_1},{x_2}, \cdots ,{x_n}$ as independent indeterminates and define $X = {\text {diag}}[{x_1},{x_2}, \cdots ,{x_n}]$. We then form the matrix product $AX{A^T} = Y$, where ${A^T}$ denotes the transpose of the matrix A. The symmetric matrix Y has in its (i,j) position the sum of the indeterminates in ${S_i} \cap {S_j}$, and consequently Y gives us a complete description of the intersection patterns ${S_i} \cap {S_j}$. The specialization ${x_1} = {x_2} = \cdots = {x_n} = 1$ of this basic matrix equation has been used extensively in the study of block designs. We give some other interesting applications of the matrix equation that involve subsets with various restricted intersection patterns.