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 0\vec{0}, a\vec{a}, b\vec{b} and c\vec{c}. Here we are treating the points as vectors in R2\mathbb{R}^2. Without any loss of generality, we took the first vector to be the null vector. By assumption, all of a|\vec{a}|, b|\vec{b}|, c|\vec{c}|, ab|\vec{a}-\vec{b}|, bc|\vec{b}-\vec{c}| and ca|\vec{c}-\vec{a}| are odd.

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

Since the square of an odd number leaves a remainder of 11 when divided by 88, it follows that a2=a,a1(mod8)a^2=\langle \vec{a}, \vec{a}\rangle\equiv 1 \pmod{8}. Also from the cosine theorem, we have 2a,b=a2+b2ab21(mod8)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=[a,aa,ba,cb,ab,bb,cc,ac,bc,c]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[211121112](mod8)2B\equiv \begin{bmatrix} 2 & 1 & 1 \\ 1 & 2 & 1 \\ 1 & 1 & 2 \end{bmatrix} \pmod{8}

Taking the determinant, we get det(2B)4(mod8)\text{det}(2B)\equiv 4 \pmod{8}. In particular, we have det(2B)0\text{det}(2B)\neq 0 and so det(B)0\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 det(B)0\text{det}(B)\neq 0, it means that the rows of BB are linearly independent. So the maximum number of linearly independent rows of BB is simply equal to the number of rows of BB. In other words, rank(B)=3\text{rank}(B)=3.

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

A=[a1b1c1a2b2c2]A=\begin{bmatrix} a_1 & b_1 & c_1 \\ a_2 & b_2 & c_2 \end{bmatrix}

Here (a1,a2)=a(a_1, a_2) = \vec{a}, (b1,b2)=b(b_1, b_2)=\vec{b} etc. Since AA has two rows, it means that the rank of AA 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 ATAA^TA can't be larger than the rank of AA which itself is at most 22. So, rank(B)2\text{rank}(B)\leq 2. But that's a contradiction since we already established that rank(B)=3\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
3 years, 4 months ago

No vote yet
1 vote

  Easy Math Editor

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.
  • Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list

  • bulleted
  • list

1. numbered
2. 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 1

paragraph 2

paragraph 1

paragraph 2

[example link]( 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×3 2 \times 3
2^{34} 234 2^{34}
a_{i-1} ai1 a_{i-1}
\frac{2}{3} 23 \frac{2}{3}
\sqrt{2} 2 \sqrt{2}
\sum_{i=1}^3 i=13 \sum_{i=1}^3
\sin \theta sinθ \sin \theta
\boxed{123} 123 \boxed{123}


Sort by:

Top Newest

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.

Mursalin Habib - 3 years, 4 months ago

Log in to reply

This was indeed nice. I definitely enjoying reading your notes.

Agnishom Chattopadhyay - 3 years, 3 months ago

Log in to reply

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?

Rayhan Rashed - 3 years, 4 months ago

Log in to reply

Which book is this?

Shashwat Asthana - 2 years, 1 month ago

Log in to reply

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

Agnishom Chattopadhyay - 2 years, 1 month ago

Log in to reply


Problem Loading...

Note Loading...

Set Loading...