# Linear Algebra Riddle

I’d like to tell you about a nice riddle, which I heard from Bob Krueger (one of our current REU participants, who already has four papers on arXiv!!). The riddle requires very basic linear algebra and is in the spirit of the previous post.

Riddle. A library has $n$ books and $n+1$ subscribers. Each subscriber read at least one book from the library. Prove that there must exist two disjoint sets of subscribers who read exactly the same books (that is, the union of the books read by the subscribers in each set is the same).

Hint: Very basic linear algebra. Try the first thing that comes to mind.

# Discrete Geometry Classic: Two-distance Sets

This post presents another simple and elegant argument in Discrete Geometry. This classic is based on the so-called “Linear Algebra method”.

Warm-up problem. What is the maximum size of a set ${\cal P} \subset {\mathbb R}^d$ such that the distance between every two points of the set is 1?

By taking the vertices of a $d$-dimensional simplex with side length 1 in ${\mathbb R}^d$, we obtain $d+1$ points that span only the distance 1. It is not difficult to show that a set of $d+2$ points in ${\mathbb R}^d$ cannot span a single distance.

The two-distance sets problem. A point set $\cal P$ is a two-distance set if there exist $r,s\in {\mathbb R}$ such that the distance between every pair of points of $\cal P$ is either $r$ or $s$. What is the maximum size of a two-distance set in ${\mathbb R}^d$?

There is a simple trick for constructing a two-distance set of size $\binom{d}{2}$ in ${\mathbb R}^d$. You might like to spend a minute or two thinking about it. Here is a picture of Euler to prevent you from seeing the answer before you wish to.

Consider the set of all points in ${\mathbb R}^d$ that have two coordinates with value 1 and the other $d-2$ coordinates with value 0. There are $\binom{d}{2}$ such points, and the distance between every pair of those is either 1 or 2.

Larman, Rogers, and Seidel showed that the above example is not far from being tight.

Theorem. Every two-distance set in ${\mathbb R}^d$ has size at most $\binom{d}{2}+3d+2$.

Proof. Let ${\cal P} = \{p_1,p_2,\ldots, p_m\}$ be a two-distance set in ${\mathbb R}^d$, and denote the two distances as $r,s\in {\mathbb R}$. Given points $a,b\in {\mathbb R}^d$, we denote the distance between them as $D(a,b)$. We refer to a point in ${\mathbb R}^d$ as $x=(x_1,\ldots,x_d)$. For $1\le j \le m$, define the polynomial $f_j\in {\mathbb R}[x_1,\ldots,x_d]$ as

$f_j(x) = \left(D(x,p_j)^2 - r^2\right) \cdot \left(D(x,p_j)^2 - s^2\right).$

That is, $f_j$ is a polynomial of degree four in $x_1,\ldots,x_d$ that vanishes on points at distance $r$ or $s$ from $p_j$. Every such polynomial is a linear combination of the polynomials

$\left(\sum_{j=1}^d x_j^2\right)^2,\qquad x_k \sum_{j=1}^d x_j^2,\qquad x_k,\qquad x_\ell x_k,\qquad 1,$

for every $1\le \ell, k\le d$. Since every $f_j$ is a linear combination of $t = \binom{d}{2}+3d+2$ polynomials, we can represent $f_j$ as a vector in ${\mathbb R}^t$. In particular, the vector $V = (v_1,\ldots,v_t)$ corresponds to the polynomial

$v_1 \cdot \left(\sum_{j=1}^d x_j^2\right)^2 + v_2\cdot x_1 \sum_{j=1}^d x_j^2 + v_3\cdot x_2 \sum_{j=1}^d x_j^2 + \cdots + v_{t} \cdot 1.$

For $1\le j \le m$, let $V_j$ denote the vector corresponding to $f_j$. Consider $\alpha_1,\ldots,\alpha_m\in {\mathbb R}$ such that $\sum_{j=1}^m \alpha_j V_j = 0$. Let $g(x) = \sum_{j=1}^m \alpha_j f_j(x)$. By definition, the polynomial $g(x)$ is identically zero. For some fixed $p_k\in {\cal P}$, note that $f_j(p_k)=0$ for every $j\neq k$ and that $f_j(p_j) = r^2s^2$. Combining the above implies

$g(p_k) = \sum_{j=1}^m \alpha_j f_j(p_k) = \alpha_kr^2s^2.$

Since $g(x)=0$, we have that $\alpha_k=0$. That is, the only solution $\sum_{j=1}^m \alpha_j V_j = 0$ is $\alpha_1=\cdots = \alpha_m = 0$. This implies that the vectors $V_1,\ldots,V_m$ are linearly independent. Since these vectors are in ${\mathbb R}^t$, we conclude that $m \le t = \binom{d}{2}+3d+2$. $\Box$

One can improve the above bound by showing that the polynomials $f_j$ are contained in a smaller vector space. This is left as an exercise of your googling capabilities.