The origins of the linear algebra method in combinatorics

How many subsets of a set of cardinality n can pairwise share the same number of elements?

In 1940’s statistician R. A. Fisher, while working on the “design of experiments”, made an interesting discovery that in a balanced incomplete block design the number of blocks is never less than the number of points (see page 54 in [1]).

How is this relevant for the problem stated above?

Well, a balanced incomplete block design (BIBD), which nowadays is known as a $2$$(v,k,\lambda)$ design is simply a collection of $k$-subsets, called blocks, of $v$ points such that every pair of distinct points lie in exactly $\lambda$ blocks. By simple counting it can be shown that in a BIBD there exist constants $b$ and $r$ where $b$ is the total number of blocks and $r$ the total number of blocks through a fixed point such that $bk = rv$ and $(v-1)\lambda = (k-1)r$. Now, if you take $n = b$ and consider the set of blocks through a fixed point as subsets then the condition of a BIBD translates into two such distinct subsets sharing $\lambda$ elements. And the Fisher’s inequality states that the number of subsets $v$ is at most the number of elements in the set, $b$.

R. C. Bose observed a few years later that the Fisher’s inequality holds for a more general case than originally proved by Fisher. He proved that , if every pair of sets in a uniform family has equal intersection size, then the number of sets does not exceed the number of points [2]. Though the significance of this 2-page paper of Bose goes far beyond proving the Fisher’s inequality. The method he used is what is now known as the ”linear algebra bound” which has since been used to prove numerous important results [3].

At around the same time Paul Erdős solved the following question in a joint paper with N. G. De Bruijn [4]: Maximally how many subsets of an n-set can have pairwise precisely one common element?

While the result of Bose assumes that each subset has the same size (uniform family) the de Bruijn-Erdős inequality makes no such assumption. But their method couldn’t be generalized for $\lambda > 1$. The general problem, posed in the beginning of this post, was ultimately solved by Majumdar (1953 [5]) and Isbell (1959 [6]) independently. Here’s a short proof of this result due to Babai [3].

Theorem. Let $S_1$, $S_2$, $\ldots$, $S_m$ be distinct subsets of $[n] = \{1, 2, \ldots, n\}$ and $\lambda$ a fixed integer satisfying $1 \leq \lambda < n$.  If  for every $i \neq j$, $|S_i \cap S_j| = \lambda$ then $m \leq n$.

Proof. First we take care of some boundary cases. Say there exists an $i$ such that $|S_i| < \lambda$, then clearly $m = 1 < n$. Now without loss of generality, say $|S_1| = \lambda$  then $S_i \cap S_j = S_1$ for all distinct $i, j$ and hence $S_i \setminus S_1$, $i > 0$ are disjoint sets. Therefore, $m - 1 + \lambda \leq n$.
So, now we can assume that $|S_i| > \lambda$ for all $i$. Define $k_i = |S_i| - \lambda$. Then all $k_i$‘s are positive. Let $M$ be the incidence matrix, i.e., $n \times m$ matrix with $M_{ij} = 1$ if $i \in S_j$ and $0$ otherwise. Consider the elements of $M$ to be coming from the field $\mathbb{R}$ of real numbers. Let $A \in \mathcal{M}_m(\mathbb{R})$ be the intersection matrix with $A_{ij} = |S_i \cap S_j|$. Then the intersection conditions can be stated as $A = M^TM = \lambda J + D$, where $J$ is the all-one matrix  of order $m \times m$ and  $D$ the diagonal matrix $[k_1 - \lambda, \ldots, k_m - \lambda]$.
From basic linear algebra it follows that $rank(A) = rank(M^TM) \leq rank(M) \leq n$. We can check that the matrix $\lambda J$ is positive semidefinite and the matrix $\lambda D$ is positive definite. Therefore, their sum must be positive definite. This proves that $A$ has full rank and hence $m \leq n$.

To show that the matrix $A$ has full rank we could have also computed its determinant (product of eigenvalues in this case as the matrix is symmetric). This is what Bose did in [2]. Alternately one can directly show that the $m$ incidence vectors corresponding to the subsets are linearly independent [8].

This result shows the power of using linear algebra in combinatorics. It has been used extensively to solve several interesting combinatorial and geometrical problems, many of which could not be proved in any other way. Here is a nice mathoverflow question that discusses the use of linear algebra in combinatorics: http://mathoverflow.net/questions/17006/linear-algebra-proofs-in-combinatorics, and here is a blog post by Gowers discussing this kind of dimension argument in combinatorics: https://gowers.wordpress.com/2008/07/31/dimension-arguments-in-combinatorics/