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/

Currently a maths PhD student at Ghent University working in the Incidence Geometry research group. I am broadly interested in combinatorics, finite geometry and group theory.
This entry was posted in Combinatorics and tagged , . Bookmark the permalink.

One Response to The origins of the linear algebra method in combinatorics

1. “The affiliation listed on Bose’s paper is the Institute of Statistics, University of North Carolina. Before taking up residence in the U.S. in 1948, Bose worked at the Indian Statistical Institute in Calcutta. One of the most influential combinatorialists of the decades to come, Bose was forced to become a statistician by the lack of employment chances in mathematics in his native country. A pure mathematician hardly in disguise, he reared generations of combinatorialists. His students at Chapel Hill included D. K. Ray-Chaudhuri, a name that together with his student R. M. Wilson (so, may be a grandson of Bose?) will appear several dozen times on these pages for their far reaching extension of Bose’s method.” – pg. 77, Linear Algebra Methods in Combinatorics by Babai and Frankl.