peyu’s blog

どの2点の距離も奇数になる4点は存在するか

結論から言うと、実はユークリッド距離では不可能

線形代数を使えば示せる！

証明

平面上に、どの二点間の距離も奇数の4点が存在すると仮定する

一つは原点 $(0,0)$ にとり、残りの3点をそれぞれ $a,b,c$ とする

仮定から、 $\lVert{a}\rVert,\lVert{b}\rVert,\lVert{c}\rVert,\lVert{a-b}\rVert,\lVert{b-c}\rVert,\lVert{a-c}\rVert$ は全て奇数

(以下、合同式は全て $\mod{8}$ )

まず、 $m$ が奇数ならば $m^2\equiv{1}$ を示す

$m=2k+1({k\in\mathbb{Z}})$ とおくと、

$m^2=(2k+1)^2$

$=4k^2+4k+1$

$=4k(k+1)+1$

$k(k+1)$ は連続する2つの整数の積だから2の倍数

したがって $4k(k+1)$ は8の倍数である

ゆえに、 $m$ が奇数ならば $m^2\equiv{1}$

余弦定理と内積の性質から、次の式が導ける

$2(x\cdot{y})=\lVert{x}\rVert^2+\lVert{y}\rVert^2-\lVert{x-y}\rVert^2$

$x=a$ , $y=b$ と代入すると、

$2(a\cdot{b})$

$=\lVert{a}\rVert^2+\lVert{b}\rVert^2-\lVert{a-b}\rVert^2$

各項は全て奇数の2乗だから、

$\equiv1+1-1=1$

同様の式が $2(b\cdot{c})$ , $2(a\cdot{c})$ にも成り立つ

$2(b\cdot{c})\equiv{1}$

$2(a\cdot{c})\equiv{1}$

行列 $B$ を、次のように定める

$B=\begin{pmatrix}a\cdot{a}&a\cdot{b}&a\cdot{c}\\b\cdot{a}&b\cdot{b}&b\cdot{c}\\c\cdot{a}&c\cdot{b}&c\cdot{c}\\\end{pmatrix}=\begin{pmatrix}\lVert{a}\rVert^2&a\cdot{b}&a\cdot{c}\\a\cdot{b}&\lVert{b}\rVert^2&b\cdot{c}\\a\cdot{c}&b\cdot{c}&\lVert{c}\rVert^2\\\end{pmatrix}$

このとき、スカラー倍 $2B$ は:

$2B=\begin{pmatrix}2\lVert{a}\rVert^2&2(a\cdot{b})&2(a\cdot{c})\\2(a\cdot{b})&2\lVert{b}\rVert^2&2(b\cdot{c})\\2(a\cdot{c})&2(b\cdot{c})&2\lVert{c}\rVert^2\\\end{pmatrix}$

先程示した関係から、行列 $2B$ は次の行列 $R$ と合同であると分かる

$R=\begin{pmatrix}2&1&1\\1&2&1\\1&1&2\\\end{pmatrix}$

ここで、行列 $R$ の行列式( $\det{R}$ )を求める

$\det{R}$

$=8+1+1-2-2-2$

$=4$

行列式の性質から、 $\det{2B}\equiv\det{R}=4$

$\det{2B}\ne{0}$ のため行列 $2B$ は正則であり、その非ゼロ倍である行列 $B$ も正則といえる

よって、 $\operatorname{rank}{B}=3$

一方、次のような行列Aを考える

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

$a_1,a_2$ というのはベクトル $a$ の第1,第2成分、すなわち $a$ の $x$ 座標、 $y$ 座標のこと

この行列 $A$ は、転置行列 $A^T$ との積が $B$ と一致する

$A^TA=\begin{pmatrix}a_1&a_2\\b_1&b_2\\c_1&c_2\\\end{pmatrix}\begin{pmatrix}a_1&b_1&c_1\\a_2&b_2&c_2\\\end{pmatrix}$

$=\begin{pmatrix}a_1a_2+a_2a_2&a_1b_1+a_2b_2&a_1c_1+a_2c_2\\b_1a_1+b_2a_2&b_1b_1+b_2b_2&b_1c_1+b_2c_2\\c_1a_1+c_2a_2&c_1b_1+c_2b_2&c_1c_1+c_2c_2\\\end{pmatrix}$