数学外書輪講I(第12回)

[場所1E501（月曜日5限）]

HPに行く

これは、7/8の外書輪講での授業の内容です。

シルベスターガレイの定理

今回は以下の定理を紹介してくれました。

シルベスターガレイの定理

平面上で同一直線上にない勝手な $n$ 点をとる。

そのとき、その $n$ 点のうちちょうど２点を含むような

平面上の直線が存在する。

(証明)
$\mathcal{P}$ を平面上の $n$ 点の集合とし、
$\mathcal{L}$ を $\mathcal{P}$ のうち少なくとも2点を通る
直線の集合とします。

$\{(P,\ell)\in \mathcal{P}\times \mathcal{L}|P\not\in \ell\}$ となる集合のうち、
$P$ から $\ell$ への距離が最小のものをとります。
それを、$(P_0,\ell_0)$ とします。

$P_0$ から $\ell_0$ への垂線の足を $Q$ とします。

ここで、$\ell_0$ が3点以上の点を含むとします。
そのとき、そのうち2点 $P_1, P_2$ が $Q$ を挟んで $\ell$ 上の同じ側
にあるとしてきます。それらのうち1つが $Q$ と一致しても構いません。

また、$P_1$ が $Q$ と $P_2$ の間にあると仮定しましょう。
このとき、$P_2$ と $P$ を結んだ直線を $\ell_1$ とおくと、
$P_1$ と $\ell_1$ との距離は、$P$ と $\ell_0$ との距離より短くなっています。

れは、$P$ と $\ell_0$ の距離が最小ということに反します。
故に、$\ell_0$ には2点以上の点を含まないことになります。

よって、シルベスターガレイの定理が導けました。
これによって、平面上の2 点には、
ちょうど2点を通る直線が存在することが示されました。

このことは平面であるから成り立ちますが、
他の空間では反例もあります。


また、次の定理も成り立ちます。
定理
平面上の$n(\ge 3)$ 点集合 $\mathcal{P}$ が一直線上に並んでいないとすると、
$\mathcal{P}$ の点を2点以上含む直線の集合 $\mathcal{L}$ は
$|\mathcal{L}|\ge n$ である。

証明
帰納法で示します。
もし、$n$ 点の場合が示されたとします。

$|\mathcal{P}|=n+1$ とします。
このとき、シルベスターガレイの
定理から、$\ell_0\in \mathcal{L}$ が存在して、$\ell_0$ は
$\mathcal{P}$ の点をちょうど2点含みます。

そのうち1点を$Q$ として、$\mathcal{P}'=\mathcal{P}\setminus \{Q\}$
とし、$\mathcal{L}'$ を $\mathcal{P}'$ のうち2点以上含む
直線の全体とします。もし、$\mathcal{P}'$ が1直線上に
乗らないとすると、帰納法の仮定から、$|\mathcal{L}'|\ge n$ であり、
$\ell_0\not\in \mathcal{L}'$ であり、
$\mathcal{L}'\cup\{\ell_0\}\subset \mathcal{L}$ であるから、$|\mathcal{L}|\ge n+1$
を満たします。
もし $\mathcal{P}$ が一直線上に乗るとすると、それらを$P_1,P_2,\cdots, P_n$ とすると、
$\overline{QP_i}\in \mathcal{L}$ であり、互いに異なるので、
$|\mathcal{L}|=n+1$ となり、この場合もやはり成り立ちます。

また、次の定理を示してもらいました。

定理
$X$ を3点以上を持つ点の集合とします。
そのとき、$A_1,\cdots A_m$ を$X$ の真部分集合とします。
もし、$X$ の各2点が、どこかの集合 $A_i$ のみに
存在するとしたら、$m\ge n$ である。

$X$ 自身を取ってしまうと、その中に、任意の
2点が含まれますから $m=1$ でOKになってしまいます。
なので、真部分集合ということになります。

また、この設定の一例として、平面上の有限点集合 $P$ に対して、
2点以上含む直線の集合 $\mathcal{L}$
があります。

(証明)
そのような$A_1,\cdots, A_m$ が存在したとして、
$x\in X$ に対して $x$ を含む $A_i$ の数を $r_x$ とします。
そのとき、仮定から、$2\le r_x<m$ です。
今、$x\in A_i=\{y_1,\cdots, y_k\}$ であるとすると、
$\{x,y_j\} $を含む集合は、$A_1,\cdots, A_m$ の中から、ちょうど
$A_{p_j}$ だけしかないので、それを並べることで、
$A_{p_1},\cdots, A_{p_m}$ は重複はなく条件から $r_x$ 以下しかありません。
よって、$m\le r_x$ です。つまり、$|A_i|\le r_x$ となります。

$m<n$ と仮定しましょう。このとき、$m|A_i|<nr_x$ であり、
$x\in A_i$ に対して、$m(n-|A_i|)>n(m-r_x)$ を満たします。
よって、
$\{(x,A_i)\in X\times \{A_1,\cdots, A_m\}|x\not\in A_i\}$ という集合を考えると、

$$1=\sum_{x\in X}\frac{1}{n}=\sum_{x\in X}\sum_{A_i:x\not\in A_i}\frac{1}{n(m-r_x)}>\sum_{A_i}\sum_{x\not\in A_i}\frac{1}{m(n-|A_i|)}$$
$$=\sum_{i=1}^m\frac{1}{m}\sum_{x\in X:x\not\in A_i}\frac{1}{n-|A_i|}=\sum_{i=1}^m\frac{1}{m}=1$$

となり矛盾します。
よって、$m\ge n$ であることがわかります。


(別証明)
この証明の別証明を隣接行列を用いて行うこともできます。
$X=\{x_1,\cdots, x_n\}$ とし、$A_1,\cdots A_m$ がそのような部分集合とします。

$B=(b_{ij})$ を
$$b_{ij}=\begin{cases}1&x_i\in A_j\\0&x_i\not\in A_j\end{cases}$$
とすると、
$$BB^t=\begin{pmatrix}r_{x_1}&1&\cdots&\cdots&1\\1&r_{x_2}&1&\cdots &1\\\cdots&\cdots&\cdots&\cdots&\cdots\\1&\cdots&\cdots &1&r_{x_n}\end{pmatrix} $$
$$=\begin{pmatrix}r_{x_1}-1&0&\cdots&\cdots&0\\0&r_{x_2}-1&0&\cdots &0\\\cdots&\cdots&\cdots&\cdots&\cdots\\0&\cdots&\cdots &0&r_{x_n}-1\end{pmatrix} +J$$
となります。ここで、$J$ は全ての成分が 1 である行列です。
この行列 $BB^t$ は正則行列です。
なぜなら、$\forall x\in A_i$ となる $i$ が唯1つしかないとすると、
そのような $A_i$ は $X$ と一致しないといけません。
よって、$r_{x_{i}}>2$ であることがわかります。
つまり、対角行列 $D$ と $J$ を用いて $BB^t=D+J$ と書いたときに、
$D$ の対角成分が全ての正の数ということになります。
この授業の第10回で書いたことと同じ議論をすることで、
$BB^t$ は正定値行列ということになります。
特に、$BB^t$ は正則行列となります。
故に、$\text{rank}(BB^t)=n$ となり、
$n=\text{rank}(BB^t)\le \text{rank}(B)\le \min\{n,m\}\le m$
であるから、$n\le m$ が成り立ちます。