# Linear Algebra (Odd Distance )

I need assistance in understanding the proof of this theorem :

"There are no four points in a plane such that the distance between each pair is an odd integer".

We proof this in contradiction and assume that one of the point is zero and the remaining ones $a, b, c$ and $\| a- b \| , \|b - c\| , \|c - a\|$ are odd integers. considering euclidean length of a vector $\|x\|$. We observe that if $m$ is an odd integer, then $m ^2 = 1 \pmod 8$.

We use the cosine theorem, asserting that every two vectors $a, b \in \mathbb R^n$ satisfy $2(a, b) = \|a\|^2 + \|b\|^2 - \|a-b\|^2 = 1 \pmod 8$ and the same holds for $2(a, c)$ and $2(b,c)$ but $(a, a ) , (b , b), (c, c)$ are all equal to $1$.

My question is why is the latter so? If I can get a better explanation, that will be great for me.

-
(a,a),(b,b),(c,c) are all equal to 1 (mod 8) –  Hassan Feb 11 '12 at 17:41
yes Asaf Karagila –  Heat Feb 11 '12 at 18:46
Say "yes" to Asaf Karagila! Four more years! –  Asaf Karagila Feb 11 '12 at 19:00

Since $\|a-b\|$ is an odd integer, $\|a-b\|^2$ is congruent to 1 mod 8.

We also have that $\|a-0\|=\|a\|$ is an odd integer (remember $0$ is one of the points). So $\|a\|^2$ is also congruent to 1 mod 8 (likewise $\|b\|^2$ and $\|c\|^2$ are congruent to 1 mod 8).

Thus mod 8 we have $\|a-b\|^2-\|a\|^2-\|b\|^2=1+1-1=1$.

$\|a-b\|^2=(a-b,a-b)=(a,a-b)-(b,a-b)$ $=(a,a)-(a,b)-(b,a)-(b,b)$ $=\|a\|^2-2(a,b)+\|b\|^2$. Therefore, $2(a,b)=\|a\|^2+\|b\|^2-\|a-b\|^2$ is congruent to 1 mod 8.

Likewise, $2(a,c)=\|a\|^2+\|c\|^2-\|a-c\|^2$ and $2(b,c)=\|b\|^2+\|c\|^2-\|b-c\|^2$ are both congruent to 1 mod 8.

Then as Joriki points out there's a good bit more of the proof left.

Notice if $a=(a_1,a_2)$, $b=(b_1,b_2)$, and $c=(c_1,c_2)$ (these are points in the plane). Then we can form the matrix $A = \begin{bmatrix} a_1 & b_1 & c_1 \\ a_2 & b_2 & c_2 \end{bmatrix}$.

$$B = A^TA = \begin{bmatrix} a_1 & a_2 \\ b_1 & b_2 \\ c_1 & c_2 \end{bmatrix} \begin{bmatrix} a_1 & b_1 & c_1 \\ a_2 & b_2 & c_2 \end{bmatrix} = \begin{bmatrix} a_1^2+a_2^2 & a_1b_1+a_2b_2 & a_1c_1+a_2c_2 \\ a_1b_1+a_2b_2 & b_1^2+b_2^2 & b_1c_1+b_2c_2 \\ a_1c_1+a_2c_2 & b_1c_1+b_2c_2 & c_1^2+c_2^2 \end{bmatrix}$$

Therefore, $B = \begin{bmatrix} \|a\|^2 & (a,b) & (a,c) \\ (a,b) & \|b\|^2 & (b,c) \\ (a,c) & (b,c) & \|c\|^2 \end{bmatrix}$. Thus $2B$ is congruent to $\begin{bmatrix} 2 & 1 & 1 \\ 1 & 2 & 1 \\ 1 & 1 & 2 \end{bmatrix}$ mod $8$. But then $\mathrm{det}(2B)$ is congruent to $4$ mod $8$. So $\mathrm{det}(B) \not=0$ [otherwise $\mathrm{det}(B)=0$ mod $8$ and so would $\mathrm{det}(2B)$]. Therefore, $B$ is invertible. But this is impossible since $B=A^TA$ which has rank at most 2 (since rank of $B$ is no more than rank $A$ which is at most $2$).

-
perfect... Bill. That explain my worries. –  Heat Feb 11 '12 at 19:50

It seems you somehow lost the second part of the proof, which you can find here. There's a lot more to it than what you reproduced. As Asaf remarked, $(a,a)=(b,b)=(c,c)=1$ holds only $\bmod8$.

-
I made no such remark! I just made $\LaTeX$ improvements. –  Asaf Karagila Feb 11 '12 at 19:04
@ Joriki, yes, I'm aware of that but all the same , thank you.. –  Heat Feb 11 '12 at 19:52
@Asaf: Sorry -- I saw "yes Asaf" and wrongly inferred that the comment above it was yours :-) –  joriki Feb 11 '12 at 20:36