外書輪講I(第10回)

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

HPに行く

今回はMiniature 17を行いました。

Miniature 17
この話は、16と同じような手法を用いるという点で、少し16と似ています。

最初に、極値集合論一般論について書いてありますが、それは省略します。
もし、輪講などで話すときには、この部分を忠実に訳して説明する必要は特になく、
もし話すとしても、手早くまとめて、本題に入るとよいと思います。

定理を述べておきます。
もし、ある、結果を話す場合には、必ず、定理の主張を黒板に書いて
ください。そして、証明を始めましょう。

定理
$X$ を $n$ 個の頂点からなる集合とします。$p$ を素数として、$X$ の中の
$2p-1$ 個の点集合からなる部分集合族を $\mathcal{F}$ とおきます。
ここで、$\mathcal{F}$ の中のどの２つの部分集合族を取っても
その共通部分は、$p-1$ 個ではない場合、$\mathcal{F}$ の要素の数は、
$$|\mathcal{F}|\le \binom{n}{0}+\binom{n}{1}+\cdots+\binom{n}{p-1}$$
という不等式を満たす。


まず、$\mathcal{F}$ の中に入る元は、高々、$\binom{n}{2p-1}$ くらいという
ことになりますが、以下説明するように、定理の主張最後の不等式の右辺は
それほど大きくはありません。
つまり、$p-1$ 個の点を共通部分を持つような集合族がないとすれば、
そのような集合族は、それほど多くはないということを意味しています。
(この条件は、$2p-1$ 個の中の $p-1$ 点は、丁度半分くらいの点の数ですから
話も表題(Midium-Size Intersection Is Hard To Avoid)にあるとおりですね。)
さらにそれを数値的に表しているのが、次の系です。


系
$n=4p$ とする。$\mathcal{F}$ を上の定理と同じものとします。
このとき、
$$\frac{\binom{4p}{2p-1}}{|\mathcal{F}|}\le 1.1^n$$
が成り立つ。

$\binom{4p}{2p-1}$ の中で、$|\mathcal{F}|$ の比率は、$1/1.1^n$くらいですから
それほどでもないと思うかもしれませんが、
$p=2$ のときは、0.46、$p=3$ のときは、0.31
$p=5$ のときは、0.14、$p=7$ のときは、0.07
$p=11$ のときは、0.02...
となり、極端に小さくなっていきます。
つまり、$p$ が大きくなっていけば、必ず、どこかの共通部分に
$p-1$ 点となるようなものが増えていくということになります。
(これはどういうことなのでしょうか？)

系の証明は不等式処理だけなので、このブログではスキップします。

今、$\{0,1\}^n$ 上の ${\mathbb F}_p$ に値をもつ関数全体を $V$ とし、$\mathcal{F}\subset \{0,1\}^n$ 上の関数全体を
$V_\mathcal{F}$ とします。
これらは、体 ${\mathbb F}_p$ 上のベクトル空間となります。


定理の証明をしましょう。

$A\in \mathcal{F}$ とします。
このとき、$A$ に対して、${\mathbb F}^n_p$ を
もし、$A\subset \{1,\cdots, n\}$ が $2p-1$ 個の点集合のとき、
特性ベクトル $c_A\in {\mathbb F}_2^n$ を以下のように定義します。
$c_A=(a_1,\cdots, a_n)$ と書いた時、
$i\in A$ なら、$a_i=1$ で、そうでない場合、$a_i=0$ とします。

$A\in \mathcal{F}$ に対して $f_A\in V_\mathcal{F}$ を以下のような関数とします。
$$f_A(x)=\prod_{s=0}^{p-2}(\sum_{x_i\in A}x_i-s)$$
前回(Miniature 16)で登場した関数 $f$ にほどよく似ていますね。
Miniature 16 ではさらに、$\prod_{s=0}^{p-1}(1-x_s)$ のようなものを引いていますが、今回はありません。

ここで、${\mathbb F}_p$ が体であるので、$ab=0$ ならば、$a=0$ もしくは、$b=0$ である
ことに注意しておきます。
$B\in \mathcal{F}$ に対して、$(b_1,\cdots, b_n)=c_B$ としたとき、
また、$\sum_{i\in A}b_i=|A\cap B|$ であることにも注意しておきます。

今、$f_A(c_B)\neq 0\bmod p$ とすると、$0\le \forall s\le p-2$ に対して、
$|A\cap B|\not\equiv  s\bmod p$ となります。よって、$|A\cap B|\equiv p-1\bmod p$
となり、条件から、$A=B$ でなければなりません。

逆に、$f_A(c_A)=\prod_{s=0}^{p-2}(|A|-s)$ の各項は、$0$ ではならいので、全て掛け合わせても $0$ にはなりません。
よって、$f_A(c_A)\not\equiv 0\bmod p$ となります。

つまり、以下の同値関係が成り立ったことになります。

$$f_A(c_B)\equiv 0\bmod p\Leftrightarrow A\neq B$$

この関数 $\{f_A|A\in \mathcal{F}\}$ のその双対ベクトル(正確にはその定数倍)は、
$V_{\mathcal{F}}$ で一次独立となります。
よって、$|\mathcal{F}|$ の個数は、$V$ の中の  $\{f_A|A\in \mathcal{F}\}$
で張られるベクトル空間 $V_\mathcal{F}$ の次元と考えれば、
$V_{\mathcal{F}}$ がどのようなベクトルの部分空間となるかを
考えればよいことになります。

$V_\mathcal{F}$ の次元を評価します。
$f(x)$ は $\{0,1\}^n$ 上の、${\mathbb F}_p^n$ に値をもつ多項式で、
$x_i^2=x_i$ であることから、

$f_A(x)$ の単項式には、2次の因子を除くことができます。
よって、$f_A(x)$ の形は、$\{1,2,\cdots, n\}$ の部分集合だけあり、
最大 $p-1$ 個だけ選んでいるので、

$$\dim(V_\mathcal{F})\le \binom{n}{0}+\binom{n}{1}+\cdots+\binom{n}{p-1}$$
が成り立ちます。

外書輪講I(第9回)

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

HPに行く

今回はMiniature 5, 16, 10を行いました。

Miniature 5

誤り訂正符号の話です。

用語の説明をしておきます。

$S$ をアルファベットといい、$S^n$ の元をワード(語)としておきます。

このとき、$C$ が符号であるとは、$C\subset S^n$ とワードの部分集合とします。

線形符号の場合は、線形部分空間です。

$u,v$ をワードとして、
$u=u_1u_2\cdots u_n$ かつ $v=v_1v_2\cdots v_n$ としておきます。

$d(u,v)=\#\{i|u_i\neq v_i\}$ をハミング距離と言います。

つまり、2つのワードに含まれるアルファベットのうち、違っているものの数

ということです。

よって任意の2つのワードの最大距離は $n$ となります。

$\forall u\in S^n$ に対して、$d(u,v)\le t$ となる$v\in C$ が高々1つ存在するとき、

$C$ は $t$ 個の誤りを直す ($C$ corrects $t$ errors) と言います。

よって、$t$ 個の誤りを直すとすると、$u\in C$ であれば、$d(v,u)\le t$ となる

$v\in C$ は存在しないということになります。

また、$d(C)=\min\{d(u,v)|u,v\in C,u\neq v\}$ とします。

ここで、$C$ が誤りを $t$ 個直すことと、$d(C)\ge 2t+1$ であることは同値です。
これは簡単なのですが、学生にやってもらおうと思っています。

感想ですが、このMiniature 5は、それほど難しくないと思うのですが、
他のものと比べると、学生にとっては少し難しいようです。

Miniature 16

は、少し先の章ですが、やってもらいました。

$I$ を閉 $0,1$ 区間とします。

$\{0,1\}^n\subset I^n$ とします。

この左は、$0,1$ の長さ $n$ の列を表します。

その列に応じた $I^n\subset {\mathbb R}^n$ の中の頂点の位置です。

例えば、列が $0,1,1,0,1,1$ なら、頂点 $(0,1,1,0,1,1)$ を表します。

また、超空間とは、${\mathbb R}^n$ の中で、1次元方程式

$a_1x_1+\cdots +a_nx_n=b$  を満たす点集合 $(x_1,\cdots, x_n)$ のことを指し、
$(a_1,\cdots, a_n)\neq (0,\cdots, 0)$ と仮定します。

主張は以下です。

定理

いくつかの超空間 $h_1,\cdots, h_m$ は、すべて ${\mathbb R}^d$ の原点を通らない
とする。さらに、この超空間の和集合は、頂点 $\{0,1\}^d\subset I^d$ のうちで、原点を除いたもの全てを通るとします。 このとき、$m\ge d$ である。

例えば、$d=2$の場合 なら、$(0,1),(1,0),(1,1)$ は同一直線上に乗らないので
この3点を通るような $1$ 本の直線は存在しないというのは、感覚としては当然です。

また、2本なら、$x_1=1$ と、$x_2=1$ があれば大丈夫です。
$x_1=0$, $x_1=1$ は、1本が原点を通るのでだめです。

一般にも、$x_1=1$, $x_2=1$, $x_3=1,\cdots, x_d=1$ として

$d$ 本で覆えるというのは分かります。

それが最小だというのがこの主張となります。

もし、$m<d$ であるとします。

$h_1,\cdots, h_m$ をその町空間とします。

その一次式を

$a_{11}x_1+\cdots +a_{1n}x_d=1, \cdots, a_{m1}x_1+\cdots+a_{md}=1$

とします。ここで、定数項はゼロではないので、その数で割っているため、定数項
は1として良いことになります。

このとき、$f(x_1,\cdots, x_d)=\prod_{j=1}^{m}(1-(a_{j1}x_1+\cdots+a_{jd}x_d))-\prod_{j=1}^d(1-x_j)$

のようにおきます。この関数のおき方がエクセレントです。

このとき、$f$ は、$I^d$ の頂点 $\{0,1\}^d$ においては、全て $0$ になります。

$(0,\cdots,0)$ の場合は、$1-1=0$ で、それ以外の頂点の場合は、$0-0=0$

となり、どちらにしても $0$ になります。

いま、$\{0,1\}^d$ 上の実数値関数全体を $V$ とします。

$V$ は有限次元ですので、ここから線形代数の活躍となります。

${\mathbb R}^d$ 上の関数を $V$ の関数だと思うとき、

このとき、$\varphi:C({\mathbb R}^d,{\mathbb R})\to V$ という

線形写像ができていることに注意しましょう。
ここで、$C({\mathbb R}^d,{\mathbb R})$ は、${\mathbb R}^d$ から ${\mathbb R}$ への連続関数全体とします。

$f$ を $V$ の元としたとき、$0$ に写ります。

また、$x^2_i$ と $x_i$ は $V$ では同じ関数となってしまいます。

つまり、$x_i^2-x_i$ はこの写像 $\varphi$ の核(カーネル)になります。

ですので、$V$ において、(${\mathbb R}^d$ における)多項式関数の

各単項式 ($cx^{i_1}_1\cdots x^{i_d}_d$ という形の項)は、$V$ の元としては、
2次の因子はなくてもよい、つまり $i_1,\cdots, i_d$ は高々 $1$ としてよいことになります。

つまり、多項式関数を $\varphi$ によって $V$ に写したものは、
$V$ の元として、$S\subset \{1,2,\cdots,d\}$ が $S=\{l_1,\cdots, l_p\}$ であるとき、
$c_Sx_{l_1}\cdots x_{l_p}$ のような項の一次結合で書けることになります。

ここで、$c_S\in {\mathbb R}$ です。
今、$x_S=x_{l_1}\cdots x_{l_p}$ と書きましょう。

以下、$\chi=\{x_S|S\subset \{1,2,\cdots, d\}\}$ が一次独立であることを示します。

もしそうだとすると、$m<d$ であるから、$f(x_1,\cdots, x_d)$ は、
$\pm x_1\cdots,x_d$ が次数最大の項で、 $V$ においてもそうです。

ということは、$V$ 上で $f=0$ であることから、この項が
他の $x_S$ の一次結合で書けなければなりません。
これはこれらの単項式が一次独立であることから矛盾します。

よって、$\chi$ が一次独立であることを示せばよいことになります。

$$\sum_{S\subset \{1,2,\cdots, d\}}\alpha_Sx_S=0\ \ \ \ (\ast)$$

とします。

今、$S\subset \{1,2,\cdots, d\}$ に対して、$x_S$ を代入します。
そうすると、$S$ の部分集合 $S’\subset S$ に対しても、$x_{S’}$ の項が残ります。
ですので、マトクセクの本文では、$\alpha_S\neq 0$ となる(包含関係において)

極小の $S$ をとって代入すればよいと言っています。

この辺もスマートな証明ですね。

それか、$|S|=1$ となるもの頂点をまず代入してそのような $S$ に
対して $\alpha_S=0$ になる。

次に、$|S|=2$ となるものを代入してそのような $S$ に対して $\alpha_S=0$ となる。

という具合にしたから順番にやっていってもよいと思います。
が、マトウセクの方がやはりスマートですね。

Miniature 10

は、グラフ理論と計算量についての話です。

グラフ理論とは、頂点と辺のある組み合わせ論的対象です。

ネットワークを抽象化したものということもできます。
この本でももうすでに何回か出てきました。
計算量は、計算機科学の分野の用語です。

最初の問題は、グラフの中に、いったいいくつの三角形、つまり、

周期３のサイクルが存在するか？という問題です。

グラフの頂点に $1$ から $n$ の番号をつけておきます。

グラフのサイクルとは、頂点 $i$ から出発して、それが辺で $j$ とつながっている。

また、$j$ が頂点 $k$ と辺でつながっている、さらに、$k$ が辺で $i$ とつながっている

という状態のことをいいます。

グラフの隣接行列 $A$ を以下のように定義します。

つまり、

$i\neq j$ であり、頂点 $i,j$ をつなぐ辺が存在したとき $a_{ij}=1$ 

で、

それ以外は $a_{ij}=0$ 

となる行列 $A=(a_{ij})$ です。

このとき、このグラフの頂点 $i,j,k$ の間に三角形が存在するかどうかは、

$A$ と $A^2$ の間の $(i,j)$ 成分がどちらもゼロではないことに同値となります。

これはちょっと考えれば分かります。

次の問題は、三角形が存在するかどうか検出するために、どれほどの
時間がかかるか？ということです。
それは、計算量というもので測ることができます。

つまり、$A,A^2$ が計算できればよいですが、

与えられているのは、$A$ ですから、$A^2$ がどれほどの時間で計算できるか
ということにかかってきます。

計算量とは、ある計算 $X(n)$ をするのに、

ある基準の計算を何回用いたか数えたものをいます。

その回数を $n$ によって表した時に、その回数のオーダーを考えるのです。

ここでは、計算量を測るのにラージオーというオーダーを使います。
(ラージオーについては以前書いたので、こちらを参照してください。)

ある計算をするのに、$n^3$ 位の

多項式オーダーである場合、つまり、$3n^3+2n+1$ 回かかっても、

$2n^3+n^2$ 回かかっても、全て、そのトップの次数の多項式をとることで、

$O(n^3)$ のようにかきます。

$O$ の中は、多項式とも限りません。

例えば、$n$ 番目のフィボナッチ数を計算するのに、足し算で計算すれば、

$O(n)$ のオーダーで計算できますが、掛け算を用いれば、$O(\log n)$ の計算量
でできることになります。(Miniature 1)

話を元に戻しましょう。

ここで、行列算の計算量を考えます。

行列 $A=(a_{ij})$, $B=(b_{ij})$ の積を考えるとき、

(ここで簡単のため、正方行列としておきます)、基準となる操作は、
掛け算です。行列を計算するのに足し算も使うのですが、足し算の回数は数えません。

その理由は、掛け算に比べて足し算はその桁に関しておよそ線形回くらいの操作で

大丈夫だが、掛け算は、2乗のオーダーくらいの計算回数がかかります。

例えば、0から9までの九九、0から9までの足し算をそれぞれ計算回数1回と
カウントすることにします。
このとき、$n$ 桁の数を２つ足すことと、２つかけることでは、
小学校の筆算を思い出してもらえばわかる通り、
前者は線形のオーダーつまり、$O(n)$ であるのに対し、後者は、$O(n^2)$ となります。
ですので、足し算の計算量は、掛け算にしてみれば、無視できるレベルだという
ことがわかります。

なので、計算回数の基準を掛け算にしてしまって、足し算をカウントしないという

ことにしてもよいわけです。

そうすると、(かけ算1回を1としてカウントした計算量で)
$n\times n$ の行列の掛け算の計算量は、それぞれの

成分ごとに $n$ 回の掛け算がありますので、全部計算するのに、
$n^3$ 回となるのです。

元の話に戻ります。本当に行列の掛け算を計算するのにをするのに、

$n^3$ 回かかるのでしょうか？

実は、2つの行列をかける計算量は、$O(n^3)$ より真に小さくすることができます。

Strassen のアルゴリズムというのがあります。(マトウセクの本文にもあります。)
$2\times 2$ 行列の積を計算するのに、本来８回かけ算をする必要がありますが、
かかることになりますが、実は７回でいけるのです。
下記の文献参照。

ですので、$4\times 4$ 行列を積を計算するのには、それを応用することで

$7\times 7=49$ 回の計算量で計算できます。本当なら64回必要です。

一般に、$n=2^k\times 2^k$ 行列の積を計算するのには、$7^k$ 回の計算量 

で充分となります。

つまり、$7^k=7^{\log_2{n}}=n^{\log_27}$ で、

$\log_27$ は大体2.8くらいですので、

$O(n^{2.807})$ の計算量ということになります。

これにより、$n^3$ より少し改善されたことになります。

このシュトラッセンの方法が最初の3より小さいアルゴリズムのようです。

このようにさらによい計算方法が今では考えられており、
現在知られている最小のオーダーは、この本では、Coppersmith-Winograd による、$O(n^{2.376})$ と書いてあります。
現在この競争がどれほど進展しているんでしょうか？

予想として、このオーダーが2でいけるのではないかと信じられているようです。

参考文献

• Strassen, Volker, Gaussian Elimination is not Optimal, Numer. Math. 13, p. 354-356, 1969
• D. Coppersmith and S. Winograd, Matrix multiplication via arithmetic progressions. J. Symbolic Comput. 9 (1990), no. 3, 251–280

外書輪講I(第8回)

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

HPに行く

　今回は、線形代数の続き、MatousekのMiniature 5を少しと9をやりました。

線形代数

問題は、以下の同値関係を示せというものです。
$A$ を正方行列とする。

$A$ が正則である$\Leftrightarrow$ 連立一次方程式 $A{\bf v}={\bf 0}$ は、${\bf v}={\bf 0}$ 以外解を持たない

$A$ が正則であるとは、逆行列をもつということとします。

(解)

($\Rightarrow$)

$A$ が逆行列をもつとします。

${\bf v}\in {\mathbb C}^n$ が $A{\bf v}={\bf 0}$ を満たすとき、

$A^{-1}$ を両辺にかけることで、${\bf v}=A^{-1}A{\bf v}=A^{-1}{\bf 0}={\bf 0}$ となります。よって${\bf v}={\bf 0}$ が成り立つので、

$A{\bf v}={\bf 0}$ には非自明な解以外持たないことがわかります。

($\Leftarrow$)

行列 $A$ を$A=({\bf a}_1{\bf a}_2\cdots {\bf a}_n)$ と縦ベクトルとして書くとき、

同値関係の右の条件は、${\bf a}_1,\cdots,{\bf a}_n$ が一次独立であること

と同値です。

なぜなら、${\bf v}^T=(c_1,c_2\cdots, c_n)$ と仮定します。

$A{\bf v}=c_1{\bf a}_1+c_2{\bf a}_2+\cdots +c_n{\bf a}_n={\bf 0}$ とすると

この $(c_1,c_2,\cdots, c_n)$ の解が $(0,0,\cdots, 0)$ しかないことは、

${\bf a}_1,\cdots,{\bf a}_n$ が一次独立であることと同値であるからです。

${\bf a}_1,{\bf a}_2\cdots, {\bf a}_n$ が一次独立とします。

このとき、以下の行の基本変形をすることで行列を簡約化します。

$$A\to A_1 \to A_2\to \cdots \to B$$

をそのような列とします。$B$をその簡約行列とします。

とくに、$B$ は階段行列です。

$B$ の $i$ 行目は、

$$(0,\cdots, 0,1,\ast,\cdots, \ast)$$

のような形にしており、最初の $0$ の数は、 $i$ が増えるに従って単調増加します。

また、$1$ のある列を、$B$ の先頭列といいます。

先頭列は、必ず数ベクトル空間の標準基底となっています。

つまり、$B$ の縦ベクトルのいくつかは、標準基底となっています。

それ以外の列があれば、その列はその標準基底の一次結合によって

書くことができます。

$A$ の全ての縦ベクトルは一次独立なので、$B$ の縦ベクトルも一次独立です。

よって、$B$ の全ての縦ベクトルは全て先頭列、つまり標準基底出なければならない

(つまり $B$ には、先頭列以外のベクトルは存在しない。)

ので、$B$ は単位行列 $E$ というなります。

行の基本変形は左から正則行列を掛けることに対応するので、

ある正則行列 $G$ が存在して、

$$GA=B=E$$

となります。よって、$A$ には、逆行列 $G$ が存在するので、

$A$ は正則行列ということになります。

$A$ には、左逆行列が存在するので、$A=G^{-1}E=G^{-1}$

となり、$AG=G^{-1}G=E$ となり、右逆行列も存在し、

$G=A^{-1}$ とおけば、

$A^{-1}A=AA^{-1}=E$ となり、$A$ は正則行列ということになります。$\Box$

以下が成り立つことになります。

$n\times n$ 行列 $A$ が正則でないとすると、

${\bf 0}\neq {\bf v}\in {\mathbb R}^n$ が存在して、

$A{\bf v}={\bf 0}$ となる。

Miniature 5

ですが、まだあまり理解していなかったようですので来週となりました。「

Miniature 9

ですが、こちら(←リンク)に先週Equiangular linesの定義とその定理について記述したので、

今回はその証明ということになります。

定理

${\mathbb R}^d$ に存在する等角直線族は、高々 $\binom{d+1}{2}$ 本

であり、$d=3$ の場合は、その最大 6 をとることができる。

後半の主張は、正２０面体を取ればよいですから、

示すべきなのは、前半の主張です。

証明、

${\bf v}_i$ ($i=1,2,\cdots, m)$ をその等角直線を表す単位ベクトルとする。

このとき、$i\neq j$ であり、$|\langle {\bf v}_i,{\bf  v}_j\rangle|=\cos\theta$ となります。

ここで、${\bf v}_i$ は縦ベクトルです。

$S_i={\bf v}_i\cdot {\bf v}_i^T$ は $d\times d$ のサイズの対称行列となります。

この行列 $S_1,S_2,\cdots, S_m$ は、$M(d,{\mathbb R})$ の対称行列全体の

なすベクトル空間の中で、一次独立であることが分かれば、

$m\le \binom{d+1}{2}$ となります。ここで、$\binom{d+1}{2}$ は

対称行列全体のなすベクトル空間の次元です。

よって、$S_1,\cdots, S_m$ が一次独立を示せばよいことになります。

$a_1S_1+\cdots+a_mS_m=O$ とします。

ここで、$O$ は零行列です。このとき、

$$\sum_{i=1}^ma_i{\bf v}_j^T{\bf v}_i{\bf v}_i^T{\bf v}_j=\sum_{i=1}^ma_i\langle {\bf v}_i,{\bf v}_j\rangle^2=a_j+\sum_{i\neq j}a_i\cos^2\theta$$

となります。

ここで、$M$ を $m\times m$ として、その $i$ 行は、

$\begin{pmatrix}\cos^2\theta&\cdots &\cos^2\theta&1 &\cos^2\theta&\cdots &\cos^2\theta\end{pmatrix}$

とし、$1$ は、$i$ 番目の成分とする。このとき、

$M=(1-\cos^2\theta)I_n+\cos^2\theta J_n$ となります。

$J_n$ は成分全て $1$ の行列とします。

この行列 $M$ が正定値であることを示します。

${\bf x}$ を ${\bf x}\neq {\bf 0}$ なる ${\bf x}\in {\mathbb R}^m$ とし、

${\bf x}^T=(x_1,x_2,\cdots, x_m)$ とします。

${\bf x}^TM{\bf x}=(1-\cos^2\theta)||{\bf x}||^2+\cos^2\theta{\bf x}^TJ_n{\bf x}$

$=(1-\cos^2\theta)||{\bf x}||^2+\cos^2\theta(x_1+x_2\cdots+x_m)^2> 0$

となります。よって、$M$ は正定値の行列となります。

正定値行列は正則でるので、$M$は正則となります。よって、

$M\begin{pmatrix}a_1\\\vdots\\a_m\end{pmatrix}={\bf 0}$

なら、$a_1=a_2=\cdots =a_m=0$ となります。

よって、$S_1,S_2,\cdots, S_m$ は一次独立であるので、$m\le\binom{d+1}{2}$

が成り立つ。$\Box$

この等角直線の問題は、ある　$m$ 本の等角直線族が構成できれば、

そこから1本抜けば、$m-1$ 本の等角直線族が構成できるのは言うまでもないので、

重要なのは、それが最大何本取れるかということです。

$v(d)$ を $d$ 次元のユークリッド空間上の等角直線の最大個数とします。

座標軸を取ったときは、全て直角な等角直線ですので、

明らかな不等式、$d\le v(d)$ があります。

$v(d)$ が最低何本取れるか？最高何本取れるか？

に興味があります。

このとき、いつでも $\v(d)=\binom{d+1}{2}$ 取れるというわけではなく、

例えば、

$v(2)=3$ かつ、$v(3)=6$ であることはすぐに分かりますが、

$v(4)=6$ (Haantjes) や 

$v(5)=10$, $v(6)=16$  (Van Lint and Seidel)

$v$ の値は、順に、

$$1,3,6,6,10,16,28,28,28,28,28,28,28,\cdots$$

(Wikipedia)

Wikipediaには、7次元の $\binom{7+1}{2}=28$ 個の

等角直線族の作り方が描いてありました。

${\mathbb R}^8$ 上で、

$(-3,-3,1,1,1,1,1,1)$ と、それらを入れ替えた28個のベクトルを用意すると、

それらの内積は、$\pm8$ となるので、等角直線族となる。

また、それらは全て、$(1,1,1,1,1,1,1,1)$ と直交するので、

そのベクトル空間の中で、この28個は最大の等角直線族となる。

これらのベクトルは、７次元の中の $3_{21}$ と呼ばれる多胞体(多面体の高次元版)

の頂点(頂点は56個あり、原点を通る直線は、その半分の28本)に位置しており、

その対称変換群が $E_7$ で分類されるコクセター群になります。

など、次元によって $v(d)$ は異なり、構成も難しいです。

しかし、自分なりのベクトルをとって数値実験をしてみたり、

有限幾何と絡めて見たりと、研究してみると面白いかもしれませんね。

参考文献の[L-S]には、今回の不等式が載っていますが、

著者２人がGerzonとprivate communication

をしたとなっており、Gerzonの不等式としています。

[L-S]に証明されている定理として、

定理[L-S(Theorem 3.5)]

$v(r)\le r(r+1)/2$ が成り立つ。また等式が成り立つなら、$r+2$は

4,5となるか、ある1より大きい奇数の2乗となる。

があります。

上の7次元の例は、$7+2=3^2$ となっているので、丁度、この

定理を満たす十分条件にもなっています。

参考文献

• [L-S]  P. W. H. Lemmens and J. J. Seidel, Equiangular Lines, Journal of Algebra, vol 24, (1973), 494-512

外書輪講I(第7回)

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

HPに行く

今回は、Miniature 7,8,9

をやりました。

Miniature 7

は、続きですが、定理は以下のようになります。

定理

非負実数 $m_{ij}$ が、$m_{ij}=m_{ji}$ となるとき、

${\mathbb R}^n$ 上の $n+1$ 点 ${\bf p}_0,{\bf p}_1, \cdots, {\bf p}_n$ 

が、存在して、$||{\bf p}_i-{\bf p}_j||=m_{ij}$ となるための

必要充分条件は、$g_{ij}=\frac{1}{2}(m_{0i}+m_{0j}-m_{ij})$ となる

行列 $G=(g_{ij})$ が半正定値となることである。

これを証明してもらったのですが、内容はそれほど難しくありませんでした。
ただ、$A$ が半正定値であることと、
$A=X^TX$ となるような実正方行列 $X$ が存在することが
同値であることがまだ分からなかったようですので
その証明をもう一回やってもらうことになりました。

$n=2$ の場合に考えれば、この定理の条件は、
平面上の三角形の存在条件、つまり
それぞれの辺に関する三角不等式と同値になるはずです。

$$G=\begin{pmatrix}g_{11}&g_{12}\\g_{21}&g_{22}\end{pmatrix}$$
が半正定値でるあることは、この行列の固有値がどちらも非負であることですが、
これは、$\det(G)\ge 0$ かつ、$g_{11}\ge 0$ であることと同値となります。
(実対称行列の固有値はいつでも実数です。)
ここで、$g_{11}=m_{01}=||{\bf p}_0-{\bf p}_1||^2$ であるので、
この条件は $\det(G)\ge 0$ だけでよいことになります。
$\det(G)$ を計算します。
$m_{01}=x,m_{02}=y,m_{12}=z$ とすると、
$g_{11}=x^2$, $g_{12}=\frac{1}{2}(x^2+y^2-z^2)=g_{21}$, $g_{22}=y^2$
であるから、
$$\det(G)=x^2y^2-\frac{1}{4}(x^2+y^2-z^2)^2$$
$$=\frac{1}{4}(y+z-x)(x+y-z)(x-y+z)(x+y+z)$$
となります。
不等式 $\det(G)\ge 0$ であることと、
$y+z-x\ge 0$, $x+y-z\ge 0$, $x-y+z\ge 0$
は同値となります。
しかし、これは自明ではないので、これにもやはり証明が必要です。

Miniature 8

は、グラフ理論の話です。
完全グラフの辺を完全二部グラフの和によって

表すことに関する定理です。

まず、完全グラフ $K_n$ とは、頂点が $n$ 個のグラフで、
辺が最大のグラフをいいます。よって辺の数は $\binom{n}{2}$ となります。

二部グラフというのは、グラフで、頂点の集合が黒と白のどちらかの色がつけ、
そのグラフが黒同士、白同士には辺がないものを言います。

完全二部グラフとは、二部グラフで、辺が最大のものを言います。

グラフ $G$ がグラフの和によって表すということは、
$G$ の辺を互いに素な(共通部分を持たない)集合の和集合によって
$G=G_1\sqcup G_2\sqcup\cdots \sqcup G_n$
のように分解することとを表し、その辺の集合がグラフとなることをいいます。
この和は辺の分解を表し、頂点の集合は重なりがあってもよいです。

定理は、以下になります。

定理

もし、完全グラフ $K_n$ の辺が、部分完全二部グラフ $H_1,\cdots, H_m$

の和として、表せるとすると、$m\ge n-1$ が成り立つ。

例えば、$K_n$ の任意の辺に対して、その辺の両端の２個の頂点のみを
頂点とする完全二部グラフを作ることができます、
このとき、$\binom{n}{2}$ 個の部分完全二部グラフが作れるので、
$K_n$ には最大、$\binom{n}{2}$ 個の部分完全二部グラフの和として表され
ることが分かると思います。
このように、辺の分割を最大にするように部分二部グラフを作ることはすぐにできます。
しかし、どれほど小さい数の和として表されるかはすぐには分からない訳です。

この本では、$K_6$ に対して、5個の完全二部グラフの和によって
表す方法を示していますが、それより小さい完全二部グラフの和として
表されるかどうかはすぐにはわかりません。

実際、この定理は、そのような最小限界が $n-1$ だということを主張しているのです。

Miniature 9

は、Equiangular Linesの話題です。

等角直線の訳です。

原点を通る直線の族を考えます。この族は、

角度は何度でもよいが、とにかく、どの２つの直線もその

間の角度が等しくなるようにしたものをいいます。
問題は、${\mathbb R}^d$ 上に等角直線が何本引けるか？ということです。

示すのは、

定理

${\mathbb R}^d$ の原点を通る直線の族が

等角直線であるなら、その本数は、$\binom{d+1}{2}$ を大きくなることはない。

です。
たとえば、${\mathbb R}^3$ の中では、
正２０面体の対角線をとると、６本あり、この値は、
丁度定理の $\binom{d+1}{2}$ を与えています。
なので、$d=3$ ではこれ以上小さくはできないのですが、
$d\ge 4$ では、まだ、小さくすることもできるようです。

つまり、この定理では等角直線族の本数の上界を与えていますが、
その最大値を求める問題は非常に難しく、
一般にその値を与えることは未解決となっています。

ということで、この話題で何か研究することは、現代でもまだ続いているという
ことになります。

ある次元でも面白い直線の配置を求めることができれば面白い結果になるのでは
ないでしょうか？

外書輪講I(第6回)

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

HPに行く

今回はMiniature 5,6,7についてやりました。

Miniature 5
は、誤り訂正符号についてです。

符号とは送るための情報のことです。
通常、符号を電気信号に乗せて送ると、それを受け取るとき、
送りたかった情報と少々のずれが出てしまう可能性があります。
そのずれは、何かの外的要因かもしれないし、偶然かもしれない。
何らかのノイズということです。
その無意味なノイズを除去するために
符号自身にその誤りを見つける機構を含ませたものを誤り訂正符号
といいます。

除去するアイデアとして、送りたい情報に余分なビット(ビットとは情報のボリュームのこと)
を増やして符号を作り、それを送るのです。

この付け加えたビットのことをparity check bitsといいます。

Matousekの本にあるように、
$abcd$ の4bitの情報をおくるのに、
$efg$ という情報を付け加えて $abcdefg$
という情報にしたものを符号として送るのです。つまり $efg$ の部分がparity check digits
ということになります。
いまは、このアルファベットを0か1としましょう。

ただ、$e=a+b+c$、$f=a+b+d$、$g=a+c+d$ という関係式があるとします。
なので、1011という情報を送る場合には、
1011001という符号にして送るのです。
ここで、上の足し算は、$1+0=0+1=1$ かつ $1+1=0$ という2元体 ${\mathbb F}_2$
の演算を用いて計算しています。
この7けたの数全体をベクトル空間として${\mathbb F}_2^7$ という7次元の
空間とみなします。このとき、$$G=\begin{pmatrix}1&0&0&0&1&1&1\\0&1&0&0&1&1&0\\0&0&1&0&1&0&1\\0&0&0&1&0&1&1\end{pmatrix}$$
と行列を定義すると、${\bf v}\in {\mathbb F}_2^4$に対して、
$G^T{\bf v}$ を送ることになります。
この $G$ のことを生成行列(Generator matrix)といいます。

このとき、7桁にした、送られる符号全体は、
あるベクトル空間となることが分かります。つまり、
$$\text{Im}(G^T)\subset {\mathbb F}_2^7$$
がそのベクトル空間です。
そのベクトル空間を解にもつ、連立一次方程式の係数行列を
parity check matrixといいます。
つまり、送られた符号をこの連立一次方程式にいれてやって
解になれば符号は間違っていないとされ、もし解にならないのなら
符号は間違っているとされます。

ここで少しだけ注意することは、符号が間違っていないとされても
本当に間違っていない符号かどうかは判定できない場合あるということです。
つまり、間違いが複数あるとすると、間違いがありすぎて、結局
合っているという可能性です。そのようなことは確率的には少ないので
この理論では検知できないし無視しようということになるのです。

Miniature 6
は、Odd Distancesですが、この話は、行列の階数を用いたちょっとした応用です。
この話も、次のMiniature 7につづく関連する話でもあります。

このランクの不等式 $\text{rank}(AB)\le \text{rank}(A)$ の不等式の使用は
これで３回目です。

主張する定理は以下です。

定理
お互いの長さが奇数であるような平面上の４点は存在しない。

この定理についてそれほど知っている人は少ないと思いますが、確かに
そうなるようです。

すぐ思いつく平面上の４点は、長方形ですが、そのときでは、
ピタゴラスの定理から、例えば、対角線の長さが5となる。辺の長さが3,4となる
長方形を考えられますが、確かに、全て奇数というわけにはいきません。
一般の四角形にも上の定理のような約束が成り立っているようです。

特に、このような長方形の２倍の長方形を考えることで、全て点の
間の距離が偶数になっている4点は存在するわけです。

この話でうまいところは、
全て奇数となる平面上の4点 ${\bf 0},{\bf a}, {\bf b},{\bf c}$ に対して、
$2\langle {\bf a},{\bf b}\rangle=||{\bf a}||^2+||{\bf b}||^2-||{\bf a}-{\bf b}||^2$
などを用いて、
行列
$$\begin{pmatrix}2\langle {\bf a},{\bf a}\rangle&2\langle {\bf a},{\bf b}\rangle&2\langle {\bf a},{\bf c}\rangle\\2\langle {\bf b},{\bf a}\rangle&2\langle {\bf b},{\bf b}\rangle&2\langle {\bf b},{\bf c}\rangle\\2\langle {\bf c},{\bf a}\rangle&2\langle {\bf c},{\bf b}\rangle&2\langle {\bf c},{\bf c}\rangle\end{pmatrix}$$

のランクの話に帰着させるところと、奇数の2乗は必ず8で割って1余る
という事実を組み合わせることです。

上の行列の $1/2$ 倍は、グラム行列といいます。
それを $G$と書けば、$G$ は、平面上の３点なのだからランクは2以下です。
($G$はMiniature 7 にも登場します)

しかし、全て奇数だとすると、この行列は、ランク3になってしまいます。

Miniature 7
は、Are These Distances Euclidean?
ですが、これは、Miniature 6を受けてユークリッド空間の中の
何点かの長さについての問題ですが、

問題は、非負実数 $m_{ij}$ $(i,j=0,1,\cdots,n)$ が、
$||{\bf p}_i-{\bf p}_j||$ となるような
${\bf p}_i\in {\mathbb R}^n$  ($i=0,1,2,\cdots, n$) が存在するための
$m_{ij}$ の条件とは何か？という問題です。

もちろん、$m_{ij}$ は $m_{ij}=m_{ji}$ でかつ、$m_{ii}=0$ であることは
必要ですが、そのほかに条件はないか？ということです。

$n=2$ の場合、つまり平面上の3点の場合は、三角不等式が
この問題の答えに相当します。

Miniature 6は、平面上の4点ですが、ここでは、$n$ 次元空間の中の $n+1$ 点です
ので、この問題には直接は関係はありません。

ここで使うのは、半正定値実対称行列 $A$ は、ある実正方行列 $X$ が存在して、
$A=X^TX$ と書けるということです。
ここで、半正定値の行列であるとは、全ての固有値が非負となる
対称行列のことです。(対称行列の固有値は全て実数であるという性質があります。)

逆に、正方実行列 $X$ に対して、$X^TX$ は半正定値実対称行列であることは
すぐ分かるでしょう。