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

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

HPに行く
manabaに行く

今回は、

• Langの線形代数における直和、直積(Chapter1)
• Matousek のMiniature 4の途中までやりました。

直和

$W_i\subset V$ が部分ベクトル空間であるとき、

$W_1+W_2$ を集合 $\{w_1+w_2|w_i\in W_i\}$ として定義します。

このとき、この集合は $V$ の部分空間となります。

定義(直和)

部分ベクトル空間 $W_1,W_2\subset V$ が

$V=W_1+W_2$ を満たし、$\forall v=w_1+w_2$ となるような $w_i\in W_i$ が一意に決まる時、$V$ は $W_1, W_2$ の直和といい、$V=W_1\oplus W_2$ と書きます。

$W_1,W_2\subset V$ が $V$ の直和であるための必要十分条件は、

$W_1\cap W_2=\{0\}$ であり、$V=W_1+W_2$ であることです。

この同値性はすぐ証明できます。また、この条件を直和の定義とする本もあります。

また、Langは直積の定義もしています。

定義(直積)

$W,U$ をベクトル空間として、を $(w,u)$ ($w\in W$, $u\in U$) なる

ペアとして得られる、 $(w,u)$ の集合全体を $W,U$ の直積といい、
$W\times U$ とかく。そのようなペア全体は、成分どうしの和とスカラー倍で
ベクトル空間になります。

直積と直和は考え方として同一ですが、最初の設定と構成方法が違います。

直和は、あるベクトル空間の２つの部分空間のうち、一意 $w_1+w_2$ と書き表せられる

ものをいい、

直積は、勝手な２つのベクトル空間に対してその直積として定義されます。
なので、直積の方はちゃんと和とスカラー倍を定義してやらないとベクトル空間に
なりません。

また、

$W_1=W\times \{0\}$ $W_2=\{0\}\times U$ として定義すると、

$W_i\subset W\times U$ は部分ベクトル空間で、

$W=W_1\oplus W_2$ となります。

例えば、$W=U=V$ であるような場合、直積 $V\times V$ は、

$(v_1,v_2)$ $v_i\in V$ のようなペアについてのベクトル空間となります。

基本的に、２つの部分ベクトル空間があったときに、その和で、共通部分が

$\{0\}$であっときに、できる直和のことを内部直和といったりします。

また、抽象的にベクトル空間 $W,U$ があったときに、その(上の意味での)直和

を取ることを外部直和と言ったりします。

どちらの直和も２つのベクトル空間を重ねる(ペアをとる)ことで一致しているので、

次元はそれぞれの次元の和になります。

Same-size intersections

極値集合論というのは、組み合わせ数学の中の一つの分野で、与えられた条件を

満たす一番大きな、もしくは一番小さな部分集合族の構造を調べるものをいいます。

(下記の参考文献を参照)

この参考文献の徳重さんの文章は、極値集合論の日本語の良い解説であり、

最初の方は、Babai-FranklのWarm-upの最初の文章、MatousekのＭiniature 4

の日本語訳を含んでいます。

(そもそも、Matousekの本は徳重さんによる日本語訳が出ています。)

Babai-Frankl の本は出版する気は無いらしいですが、大層良い本で、前知識は

ほとんどいりませんので、大学一年生でも読めるレベルだと思います。

また、多くの演習問題が付属しており、関連問題をといて、力をつけるのにも

適していると思います。

Warm-Upの2つ目の話題は、Ｍatousekの本でもMiniature 15としてとりあげており、

読み応えのある話だと思います。

この分野の感想としては、組み合わせ論などの非常に複雑な世界の話が

大学一年生レベルの数学を用いて面白い結果が出るというのは面白いと思います。

設定を微妙に替えれば、すぐにいろいろな問題を作れますが、その中で

解ける面白い問題を見つけるのはセンスが必要となるでしょう。

しかし、使われる技術は、応用数学や、その他様々な研究の中で

汎用性が高い場合もあるので、勉強して技術を身につけて、

将来研究者になるのはよい選択肢だと思います。

３回前の外書輪講でのblogで奇数町のクラブについての話を
しましたが、もう一度しておきます。

2017年数学外書輪講I第8回(リンク)

奇数町のクラブ数についての問題をもう一度書いておきます。

問題

$n$ 人の市民がいる。その市民たちはクラブをいくつか作っている。

市民はやたらクラブをつくるので、市議会は法律を使ってそれを規制したい。

どのような規則をつくればいいか？

これは大雑把な問題ですが、さらに問題を制限して、以下のような

規則を作ります。

同じメンバーを持つようなクラブは作れないと仮定することは自然です。

これを認めてしまえば、同じメンバーで違うクラブをいくらでも作ることは

簡単にできてしまうからです。

この規則を課せば、クラブに入るかどうかを指定することで、

クラブの数はせいぜい $2^n$ 個です。

しかし、$2^n$ 個のクラブでもまだ多いのでもう少し小さくすることを考えます。

そのため、以下のような規則を作ります。

1. クラブに入る市民の数は奇数。
2. 任意の２つのクラブに共通して入っている市民の数は偶数。

まず、同じメンバーをもつクラブを作ることはできないことはすぐわかります。

また、だれも入っていないクラブも作ることはできません。

よって、この規則1. 2. は最初の規則よりは厳しいことになります。

定理

この規則を課せば、作ることができるクラブの数は $n$ を超えることはできない。

これを、奇数町定理(Oddtown theorem)といいます。

Matousekの本では、Babai-Franklの内容の、second proof をしていますが、

ここではFirst proofをしてみます。これらの証明は、本質的には同じです。

(証明)

$m$ をクラブの数とします。$1,..,n$ を市民の名前とします。

また、$C_1,...,C_m$ は各クラブで、所属する市民の集合とします。

このとき、$v_i\ \ (i=1,...,m)$ を $v_i\in {\mathbb F}_2^n$ として、

$v_i$ の $j$ -成分を 

$\begin{cases}1&j\in C_i\\0&j\not\in C_i\end{cases}$

として定義します。

$\{v_i\}$ ($i=1,...,m$) は線型独立であることが示されれば、

$m=\dim(\langle v_1,...,v_m\rangle)\le \dim {\mathbb F}_2^n=n$

が成り立ち、主張が示されます。

$\{v_i\}$ が線型独立であることを示します。

$v_i\cdot v_j=|C_i\cap C_j|\bmod 2$ となります。

ここで、$|C_i\cap C_j|$ は $C_i$ と $C_j$ の両方に入っている人数とします。

条件 1. 2. から、

$v_i\cdot v_j=\delta_{ij}$

となります。ここで、$\delta_{ij}$ はクロネッカーのデルタで、
$i=j$ ならば、$\delta_{ij}=1$ であり、$i\neq j$ であれば、$\delta_{ij}=0$ となる数です。

$\lambda=\lambda_1v_1+\cdots +\lambda_nv_n=0$ とすると、

$\lambda\cdot v_i=\lambda_iv_i\cdot v_i=\lambda_i=0$ となり、

一次独立が簡単に示されます。

また、Babai-Franklの演習問題には、1. 2. のルールの奇数と偶数を逆にしたもので

も、同じ結論(不等式 $m\le n$) がわかるとなっています。証明はほぼ同じなので、

ここでは割愛します。

ちなみに、

$J_m$ を全ての成分が $1$ の $m\times m$ 行列とし、$I_m$ を $m\times m$ 

単位行列としますと、

$\text{rank}(J_m-I_m)=\begin{cases}m&m:\text{even}\\m-1&m:\text{odd}\end{cases}$

となります。

連休明けの火曜日は振替で月曜日の授業ですので、気をつけてください。

参考文献

• 徳重典英, 極値集合論における線形代数的手法, 数理解析研究所講究録1956, 2015年7月101-110
  http://www.cc.u-ryukyu.ac.jp/~hide/kokyuroku-revised.pdf
• L. Babai, P. Frankl, Linear algebra methods in combinatorics (with applications to Geometry and Compute Science),