# 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.

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!

Note by Mursalin Habib
1 year, 11 months ago

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

• Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
• Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
• Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold
- bulleted- list
• bulleted
• list
1. numbered2. list
1. numbered
2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in $$ ... $$ or $ ... $ to ensure proper formatting.
2 \times 3 $2 \times 3$
2^{34} $2^{34}$
a_{i-1} $a_{i-1}$
\frac{2}{3} $\frac{2}{3}$
\sqrt{2} $\sqrt{2}$
\sum_{i=1}^3 $\sum_{i=1}^3$
\sin \theta $\sin \theta$
\boxed{123} $\boxed{123}$

Sort by:

I can't remember how long it's been since I last wrote something like this on Brilliant. It's definitely been while and it was a lot of fun to do. Please let me know if you want to see more stuff like this. As always, any sort of feedback is very much appreciated.

- 1 year, 11 months ago

- 1 year, 11 months ago

I do get the idea of the proof. But, to me, it is feeling like a magic still. How do we get an intuition that this method will actually do work? Is there any deep connection lying behind always?

- 1 year, 11 months ago

Which book is this?

- 9 months ago

Thirty-three Miniatures: Mathematical and Algorithmic Applications of Linear Algebra

- 8 months, 4 weeks ago