Month: July 2018

by

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.

Inside the library of the university of Leuven, Belgium

by

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.

330px-Tetrahedron

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.

Euler

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.