Using Linear Algebra to Solve Combinatorial Problems: Odd Distances

Recently I've been reading a draft version of a book by Jiří Matoušek. The book seems to take problems that are combinatorial or algorithmic in nature and solves them using ideas of linear algebra. What's amazing about the problems is that on first glance they don't seem to have anything to do with linear algebra at all. But the book solves them using linear algebra anyway: it forms certain matrices, multiplies them, takes their determinants, argues about their ranks and somehow produces a solution.

In this note, I want to share one of my favorite problems from that book. You do need to know a little bit of linear algebra to understand what's going on in the solution. But it's not anything highly technical. In fact, this solution, like most of the other solutions in the book, hinges on just one fact: the rank of the product of matrices is no larger than the minimum of the ranks of the factors. Even if you don't know why this is true, you can still follow along. But if you don't know what the rank of a matrix is, things are probably going to be hard for you to follow.

I think I've done enough talking. It's time to see the problem.

There can't exist four points on the plane such that the distance between any pair of them is an odd integer.

I'm going to be honest here. This is the sort of problem I wouldn't know how to even begin to solve. I guess I would start by drawing some pictures and noticing that the statement seems to hold true no matter what. But I would then eventually give up without making any sort of significant progress.

But this article isn't about my problem-solving skills or the lack thereof. This is about how we're going to solve a problem with no apparent connection to linear algebra with linear algebra. So let's begin!

For the sake of contradiction, we're going to assume that there are four such points that the distance between any pair of them is odd. Let the points be $\vec{0}$, $\vec{a}$, $\vec{b}$ and $\vec{c}$. Here we are treating the points as vectors in $\mathbb{R}^2$. Without any loss of generality, we took the first vector to be the null vector. By assumption, all of $|\vec{a}|$, $|\vec{b}|$, $|\vec{c}|$, $|\vec{a}-\vec{b}|$, $|\vec{b}-\vec{c}|$ and $|\vec{c}-\vec{a}|$ are odd.

Let $\langle\vec{a}, \vec{b}\rangle=ab\cos\theta$ be the very familiar dot product of $\vec{a}$ and $\vec{b}$. Here $\theta$ is the angle between the vectors $a$ and $b$.

Since the square of an odd number leaves a remainder of $1$ when divided by $8$, it follows that $a^2=\langle \vec{a}, \vec{a}\rangle\equiv 1 \pmod{8}$. Also from the cosine theorem, we have $2\langle \vec{a}, \vec{b}\rangle = |\vec{a}|^2+|\vec{b}|^2-|\vec{a}-\vec{b}|^2\equiv 1\pmod{8}$.

Now consider the matrix

$B=\begin{bmatrix} \langle\vec{a}, \vec{a}\rangle & \langle\vec{a}, \vec{b}\rangle & \langle\vec{a}, \vec{c}\rangle\\ \langle\vec{b}, \vec{a}\rangle & \langle\vec{b}, \vec{b}\rangle & \langle\vec{b}, \vec{c}\rangle \\ \langle\vec{c}, \vec{a}\rangle & \langle\vec{c}, \vec{b}\rangle & \langle\vec{c}, \vec{c}\rangle \end{bmatrix}$

Note that, $2B\equiv \begin{bmatrix} 2 & 1 & 1 \\ 1 & 2 & 1 \\ 1 & 1 & 2 \end{bmatrix} \pmod{8}$

Taking the determinant, we get $\text{det}(2B)\equiv 4 \pmod{8}$. In particular, we have $\text{det}(2B)\neq 0$ and so $\text{det}(B)\neq 0$.

This is the time we need to know about the rank of a matrix. If you aren't familiar with it, just think of it as the maximum number of linearly independent rows of a matrix. Some rows of a matrix are said to be linearly independent if none of the rows can be expressed as a linear combination of the other rows. If none of these terms seem familiar, look them up. You don't need to know much linear algebra to know what these terms mean.

Since $\text{det}(B)\neq 0$, it means that the rows of $B$ are linearly independent. So the maximum number of linearly independent rows of $B$ is simply equal to the number of rows of $B$. In other words, $\text{rank}(B)=3$.

The crucial part of the proof is to notice that $B=A^TA$ where

$A=\begin{bmatrix} a_1 & b_1 & c_1 \\ a_2 & b_2 & c_2 \end{bmatrix}$

Here $(a_1, a_2) = \vec{a}$, $(b_1, b_2)=\vec{b}$ etc. Since $A$ has two rows, it means that the rank of $A$ is at most two.

Now we're ready to use the fact mentioned at the beginning of the article: the rank of the product of matrices is no larger than the minimum of the ranks of the factors. So the rank of $A^TA$ can't be larger than the rank of $A$ which itself is at most $2$. So, $\text{rank}(B)\leq 2$. But that's a contradiction since we already established that $\text{rank}(B)=3$.

So, we're wrong in assuming the existence of the points. This concludes the proof.

If you haven't seen a proof like this before, this should all feel like magic. It takes a while (at least it did for me) to really understand what's going on. But damn is it elegant!