外書輪講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回)