外書輪講I(第5回)

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

HPに行く

外書輪講です。

読んでいる本は33-Miniatures(Matousek)です。

線形代数１０問題の続き

$A$ が正則行列であることと、
$\forall {\bf v}\in V$ において $A{\bf v}={\bf 0}\Rightarrow {\bf v}={\bf 0}$

であることが同値であることがさらに残りました。

この関係についてはどうしても理解してほしいと思います。
そして、今回の輪講の中にもそれが登場しました。

Miniarure 4

Same-size intersection(Fisherの不等式)のつづきでした。

Miniature 3に引き続き、行列の階数を用いて行う極値集合論です。

定理

$C_i\ \ (i=1,2,\cdots, m)$ を $n$ 個の元からなる集合の部分集合とする。
$C_i\cap C_j$ が空集合ではなく、お互い違う集合だが、

集合のサイズ(濃度、もしくは元の数)($|C_i\cap C_j|$とかく)が
一致しているとする。このとき、 $m\le n$ である。

この包含関係を行列にして、
$$a_{ij}=\begin{cases}1&j\in C_i\\0&j\not\in C_i\end{cases}$$
として行列 $A=(a_{ij})$ を作る。

今、$B=AA^T$ を考えます。($A^T$ は行列 $A$ の転置)
このとき、
$$B=\begin{pmatrix}d_1&t&\cdots &\cdots&t\\t&d_2&t&\cdots &t\\\vdots&\cdots&\ddots&\cdots&\vdots\\t&\cdots&t&d_{n-1}&t\\t&\cdots&\cdots&t&d_m\end{pmatrix}$$

$d_1,d_2,\cdots, d_m$ は、$|C_1|,|C_2|,\cdots, |C_m|$ であり、
$t=|C_i\cap C_j|$ である。
今、任意の $i$ に対して、$d_i>t$ であるとすると、
この行列は正定値となる。

正定値

対称行列 $A$ が正定置であるとは、

${\bf x}\neq 0\Rightarrow {\bf x}^TA{\bf x}>0$

であることをいう。
対偶をとれば、${\bf x}^TA{\bf x}=0$ ならば、${\bf x}={\bf 0}$ となる。

正定値な行列は、正則であることを示してもらいました。

$B$ が正定値な行列とすると、
$B{\bf x}=0$ とすると、${\bf x}^TB{\bf x}=0$ であり、
このとき、正定値性から、${\bf x}=0$ が成り立ちます。

このことから $B$ が正則であると言えます。
よって、Miniature 3と同じ議論から、
$\text{rank}(B)\le\text{rank}(A)$ から、$m\le n$ が成り立ちます。

残った部分は、$d_i=t$ となってしまう場合ですが、
Matousekではこの場合について最初に $m\le n$ を示しています。

もし、こうなった場合、$C_i$ がすべての $C_j$ に含まれています。
$C_j\setminus C_i\ \ j=1,2,\cdots, m$ は $j\neq i$ でない場合空ではなく、
すべて相異なります。
つまり、$n-t$ の元を $C_j\setminus C_i\ \ j=1,2,\cdots, i-1,i+1,\cdots,m$
の元として振り分ければよいのだから、
これは、$m\le n$ を意味します。

Miniature 5

は誤り訂正符合のについての内容です。

これも、去年やったものがありますので、下にリンクさせておきます。

2017外書輪講I(第5回)
2017外書輪講I(第6回)
2017外書輪講I(第7回)
2017外書輪講I(第8回)

外書輪講I(第4回)

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

HPに行く

今回は、Miniature 2 の途中からとMiniature 3,4の途中まで終わりました。

Miniature 2
は、Fibonacci 数列の一般項を見つける方法です。

${\mathbb R}^\infty=\{(a_n)|a_n\in {\mathbb R},n\in{\mathbb N}\}$
を実数を係数とする数列の空間を表します。

この数列は無限次元でしたが、
$W=\{(a_n)\in{\mathbb R}^\infty|a_{n+2}=a_{n+1}+a_n,n\in{\mathbb N}\}$
として条件を入れると、有限次元となります。
この場合、次元は２です。

$\tau_1,\tau_2$ を $\tau^2-\tau-1=0$となる異なる２つの解とするとき、

$${\bf u}=(\tau_1^0,\tau_1^2,\cdots, \tau_1^n,\cdots)$$

$${\bf v}=(\tau_2^0,\tau_2^2,\cdots, \tau_2^n,\cdots)$$

は、$W$ の元に含まれており、

これらは、一次独立であることが示されます。

$W$ が2次元であることは、すべての $W$ の元がこれらの一次結合であること

を示されれば、$\dim(W)=2$ であることがわかります。
つまり、${\bf u},{\bf v}$ は $W$ の基底となります。

この2つの元 $\{{\bf u},{\bf v}\}$ の他の２つ一次独立の元を使っても
同じように $W$ の全ての元をつくることができます。

系として、次のようなフィボナッチ数列

$$F_0=0, F_1=1, F_2=1,\cdots, $$

を ${\bf u}, {\bf v}$ の一次結合で書くこともできますので、

$F_n=\alpha \tau_1^n+\beta\tau_2^n$ のように書くことができます。

この式は、任意の $n$ に対して成り立ちますが、$\alpha,\beta$ は $n$ によらない定数です。

ここで、$\tau_1=\frac{1+\sqrt{5}}{2}, \tau_2=\frac{1-\sqrt{5}}{2}$ 

となりますので、$\alpha=\frac{1}{\sqrt{5}}$, $\beta=-\frac{1}{\sqrt{5}}$ 

であるから結局、

$$F_n=\frac{1}{\sqrt{5}}\left(\left(\frac{1+\sqrt{5}}{2}\right)^n-\left(\frac{1-\sqrt{5}}{2}\right)^n\right)$$

と計算できます。

Miniature 3

は、Odd townクラブの話です。
この話は、極値集合論の話(組み合わせ数学の領域の話)です。

「The Clubs of Odd town 」とは、以下のような話です。
$n$ 人の住民はクラブを作るのが好きである。

住民はいくらでもクラブを作るので、それを制限するために

以下の条件を設けた。

• 各クラブに入る人数は奇数である。
• 任意の２つのクラブに対して、そのクラブに共通して入っている人の数は偶数である

このとき、クラブの数 $m$ は $n$ 以下となる。

この話は以前も書いたので、こちらにリンクを貼っておきます。

この不等式は、線形代数を使って示すことができます。

 $i=1,2.\cdots, m$ として、$C_i$を名前が $i$ のクラブとする。

$j\in C_j$ として、クラブ $j$ に $i$ という人が所属していることを表します。

行列 $A$ を

$$A=(a_{ij})$$

として、$a_{ij}=\begin{cases}1&j\in C_i\\0&j\not\in C_i\end{cases}$

として定義をします。

このとき、$A{}^tA$ は条件から ${\mathbb Z}/2{\mathbb Z}$ において

単位行列になりますので、

$m= \text{rank}(A{}^tA)\le \text{rank}(A)\le n$ となるので、

$m\le n$ が成り立ちます。

Minature 4

は、Miniature 3に引き続き組み合わせ論で類似の話です。

$C_i$ を $n$ 個の元からなる集合の空ではない部分集合とします。

$C_1,C_2,\cdots, C_m$ を互いに異なるそうした部分集合とする。

つまり、これら $\{C_1,C_2,\cdots, C_m\}$ は、最大 $2^n-1$ 個の
ヴァリエーションがあります。
なので、自然に、$m\le 2^n-1$ なる不等式が成り立ちます。

この章での主張は次です。

定理(Generalized Fisher inequality)

もし、$C_i\cap C_i$ $i,j$ によらずすべて同じ数の元からなる集合のとき、

$m$ は、$n$ 以下になる。

次回は、この定理の続きからです。

発表の準備で心がけること

人の前で何かを説明するとき(プレゼンや発表など数学に限らず)、

心がけることは、本説明をしているときに、細部を怠らないことで

説明することです。(あまり本筋と関係のない細部について説明するときや
脱線の話をするときは細部をそれほど話す必要はありません。)
そのとき、口で言うだけでなく、何か形に

残すように(例えばスライドや黒板に書くようにして)で提示します。
例えば、何回も復習する場合は、黒板に残しておいて
なんども引用します。

(こんな簡単なことは説明をしなくてもわかるだろう)ということは
決してありません。

例えば、フィボナッチ数列なら、必ずフィボナッチ数列を特徴付ける式

や関係式、行列表示をするならその行列は書くことが必須ですし、

定理を書くなら、仮定、結論などはかき、
証明をするならレポートで証明を書くくらいの精度でかくこと方が
良いでしょう。

とにかく丁寧に丁寧に説明をしてください。

また、Odd townなら、どのような条件でクラブを作るのかなど

は必ず書くようにします。

また、説明をしている人はよくわからないとおもますが、
一生懸命予習をした人なら、内容についてはよくわかっていますが、
そうでない人には、よくわかっていないということがわかりません。
その点注意しましょう。
つまり、説明は一度言えばわかってもらえるとも限らないので、

(自分はよくわかっていても)説明を繰り返すことが有効です。

少しくどいかなと思われるくらいがちょうど良いです。

外書輪講I(第3回)

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

HPに行く

今回は先週残った線形代数の発表とマトウセクのMiniature 1,2をやりました。

線形代数の問題についていくつか
(3)
2次元ベクトル空間 $V$ の任意の3つのベクトルは一次従属である。

(学生が行った解答)
${\bf a},{\bf b },{\bf c}$ を任意の3つのベクトルとする。
このとき、${\bf a},{\bf b}$ が一次独立であるとすると、
2次元ベクトル空間の2つの一次独立なベクトルは基底であるから、
${\bf c}=u{\bf a}+v{\bf b}$ とすることができる。
よって、$u{\bf a}+v{\bf b}-{\bf c}=0$ という関係式が得られたので
${\bf a},{\bf b},{\bf c}$ は一次従属である。

${\bf a},{\bf b}$ が一次従属であるとすると、
$(u,v)\neq (0,0)$ であって、$u{\bf a}+v{\bf b}=0$ とできる。
よって、
$u{\bf a}+v{\bf b}+0{\bf c}=0$ であるからこの関係式から
${\bf a},{\bf b},{\bf c}$ は一次従属である。


(別解答)
2次元ベクトルであるということは、基底として2つのベクトルを取ることができる
ということだから、
${\bf v},{\bf w}\in V$ を基底とするように取れます。

このとき、$V$ の3つのベクトルを ${\bf a}, {\bf b}, {\bf c}$ をとります。
すると、
${\bf a}=a_{11}{\bf v}+a_{12}{\bf w}$
${\bf b}=a_{21}{\bf v}+a_{22}{\bf w}$
${\bf c}=a_{31}{\bf v}+a_{32}{\bf w}$

となるような係数 $a_{11},\cdots, a_{32}$ があります。
よって、
$({\bf a}, {\bf b}, {\bf c})=({\bf v}, {\bf w})\begin{pmatrix}a_{11}&a_{21}&a_{31}\\a_{12}&a_{22}&a_{32}\end{pmatrix}$

もし、${\bf a},{\bf b},{\bf c}$ が一次独立であるなら、
$\begin{pmatrix}a_{11}\\a_{12}\end{pmatrix},\begin{pmatrix}a_{21}\\a_{22}\end{pmatrix},\begin{pmatrix}a_{31}\\a_{32}\end{pmatrix}$
も一次独立である。つまり $\begin{pmatrix}a_{11}&a_{21}&a_{31}\\a_{12}&a_{22}&a_{32}\end{pmatrix}$ のランクが3である。しかし、行列はランクは一般に行数や列数以下。
よって、ランクは2以下にならなければならない。
これは矛盾する。

よって、${\bf a},{\bf b},{\bf c}$ は一次従属。

(4) ベクトル空間の足し算 $V+W$ は以下のようにして定義されます。
$$V+W=\{{\bf v}+{\bf w}|{\bf v}\in V,{\bf w}\in W\}$$
です。この定義を説明すると、$V,W$ のベクトルのそれぞれの和としてかけるベクトル全体
ということです。

(6) $A$ を $n$ 次正方行列とし、${\bf v}\in  {\mathbb C}^n$ とする。このとき、連立方程式 $A{\bf v}=0$ に自明でない解が あることと、$\det(A)=0$ であることは同値であることを示せ。

対偶をとれば、
$A{\bf v}=0$ に自明でない解がないこと $\Leftrightarrow A$ が正則(逆行列がある)であること。
なる同値関係を示せばよいわけですが、
$\Leftarrow $は逆行列をかければよい。

$\Rightarrow $ の証明。逆行列が存在しないとすると、$A$ の $n$ 個の縦ベクトルは
一次従属ということであるから、${\bf v}=(a_1,a_2,\cdots, a_n)\neq (0,0,\cdots, 0)$ となる
ベクトルが存在して、$A{\bf v}=0$ が成り立ちます。

Miniature 1
Miniature 1はフィボナッチ数列 $\{F_n\}$ を計算を手早く計算しようという
内容です。

$$\begin{pmatrix}F_{n+2}\\F_{n+1}\end{pmatrix}=\begin{pmatrix}1&1\\1&0\end{pmatrix}\begin{pmatrix}F_{n+1}\\F_{n}\end{pmatrix}=M\begin{pmatrix}F_{n+1}\\F_{n}\end{pmatrix}$$
を用いて、$M$ を書けることで、次々にフィボナッチ数を計算することができるように
なります。つまり、足し算によって計算していたフィボナッチ数列は、行列の
掛け算を計算すればよいということになります。$F_{2^k}$ の計算は、
$M^{2^k}=M^2\cdots M^2\cdots M^2$ のように $k$ 回の計算で
できるようになります。
同じように、一般の $n$ (For $n$ arbitrary) に対して
$$n=2^{k_1}+2^{k_2}+\cdots+2^{k_t}$$
のように書き表せます(2進法)ので、
同じように大体 $F_n$ を計算する回数は、$2\log n$ 回くらいに減らせるという
ことが分かります。

発表者は、よく説明ができていました。
もっと黒板を多く使って分かりやすく説明するとよいと思います。
binary は2進法(バイナリ)でした。

Miniature 2
次の話は、$F_n$ を計算するのに線形代数を使うということです。
そのとき、一度大きな空間を考えるます。
${\mathbb R}^\infty=\{(a_n)|n\in {\mathbb N},a_n\in {\mathbb R})\}$
です。これは、 全ての数列からなる空間で、無限次元べｋ取る空間です。
この中から、フィボナッチ数列からなる有限次元ベクトル空間を選び出します。

$$V=\{(a_n)\in {\mathbb R}^n|a_{n+2}=a_{n+1}+a_n\}$$
です。このとき、$V$は 2次元ベクトル空間となります。

本には2次元になるとさらりと書いてありますが、証明をすることは
できるでしょうか？基底を２つ選んでこればよいわけですが、
これも線形代数でできますね。

来週はこの続きからやります。