現代数学のエレファント(1) - エレファント・ビジュアライザー調査記録

「声に出して読めなくもない数学」は「現代数学のエレファント」に変更しました。このシリーズでは数学のいろいろな理論を「エレファント化」していく予定です。四色問題のコンピューターを使った証明がエレガントではなくエレファントと言われたらしいです。ここでは(意味は少し違うとは思いますが)定義から計算で証明できるようにすることを「エレファント化」と呼ぶことにします。

たとえば、「円周率の小数点以下8457桁目は何？」や「7492+6383は何？」のような問題は、答えを知らなくても計算する方法があるという事実は知っているので答えを知っているのも同然ということになります。これを「エレファント状態」と呼ぶことにします。サーバーで永久に動き続けるプログラムの実行順序を説明することが難しいので、この問題を「エレファント状態」にするのがこのブログの目標の1つとなっています。

基底と次元

$X$ をベクトル空間 $V$ の有限部分集合とするとき、 $X$ の元の個数を $\#X$ 、 $X$ で張られた部分空間を $\langle X \rangle$ と書くことにします。

$V = \langle X \rangle$ かつ $X$ は1次独立のとき $X$ を $V$ の基底と呼びます。前回の (10) より $V$ の基底の元の個数は、基底 $X$ のとり方によらず決まります。 $V$ の基底の元の個数を $V$ の次元と呼び $\dim V$ と書きます。 $V = \langle X \rangle$ かつ $X$ は1次独立のとき $\dim V = \#X$ となります。

ベクトル空間 $V$ の有限集合の基底が存在するとき $V$ を有限次元ベクトル空間と呼びます。 $K$ を体とするとき $V = K^n$ は有限次元ベクトル空間となります。 $a_{ij}$ を $i = j$ のとき $a_{ij} = 1$ 、 $i \ne j$ のとき $a_{ij} = 0$ 、 $e_i = (a_{i1}, a_{i2}, \cdots, a_{in})$ とすると、 $E_n = \{e_1,e_2, \cdots, e_n\}$ は $K^n$ の基底となります。

行列のランク

$m$ 行 $n$ 列の行列 $M$ の $k$ 行目を有限次元ベクトル空間 $K^n$ の元と見たものを $M_k$ とします。 $V_M = \{M_1, M_2, \cdots, M_m\}$ とします。

$K^n$ の有限部分集合 $X$ に対して $r(X) = \dim \langle X \rangle$ とおきます。 $r(V_M) = \dim \langle V_M \rangle$ を $M$ のランクと呼びます。

$m \le n$ のとき $K^m$ の元の $m+1$ 番目から $n$ 番目までの成分を $0$ とすることで $K^m \subseteq K^n$ とみなします。

$K^\nu$ の有限部分集合 $X$ が $K^n$ で1次独立( $n \le \nu$ )であるということを以下のように帰納的に定義します。

(1) 空集合は $K^n$ で1次独立
(2- $n$ ) $X$ は $K^n$ で1次独立かつ $v \in K^n \setminus \langle X \rangle$ ならば $X \cup \{v\}$ は $K^n$ で1次独立

空集合から (2- $n$ ) を繰り返してできる集合を $K^n$ で1次独立とします。 $K^n$ で1次独立ではない集合を $K^n$ で1次従属とします。

(3) のときの有限部分集合に対して
- $X$ は $K^m$ で1次独立 $\iff$ $X$ は $K^n$ で1次独立
(4) $X \subseteq Y \implies r(X) \le r(Y)$
(5) $r(X \cup Y) \le r(X) + r(Y)$
(6) $r(\varnothing) = r(\{0\}) = 0$
(7) $r(\{u\}) \le 1$
(8) $r(X) \le \#X$
(9) $X$ は1次独立 $\implies r(X) = \#X$
(10) $X \subseteq E_n \implies r(X) = \#X$

行に関する基本変形

集合 $X$ と集合 $Y$ の集合の直和を $X +_1 Y$ と書くことにします。集合の直和は $X \cap Y = \varnothing$ のときの $X \cup Y$ になります。

(11) $a \ne 0 \implies r(X +_1 \{u\}) = r(X +_1 \{au\})$
(12) $r(X +_1 \{u\} +_1 \{v\}) = r(X +_1 \{u\} +_1 \{u+v\})$
(13) $a \ne 0 \implies r(X +_1 Y) = r(X +_1 aY)$
(14) $r(X +_1 Y +_1 Z) = r(X +_1 Y +_1 (Y + Z))$

列に関する基本変形

行に関する議論を列に関する議論にすることができます。 $m$ 行 $n$ 列の行列 $M$ の $k$ 列目を有限次元ベクトル空間 $K^m$ の元と見たものについて同様の議論ができます。この場合の集合 $X$ と集合 $Y$ の集合の直和を $X +_2 Y$ と書くことにします。

(15) $a \ne 0 \implies r(X +_2 Y) = r(X +_2 aY)$
(16) $r(X +_2 Y +_2 Z) = r(X +_2 Y +_2 (Y + Z))$

(17) $K^n$ の任意の有限部分集合 $X$ に対して、 $X$ から行に関する基本変形と列に関する基本変形を繰り返して得られる $Y \subseteq E_n$ が存在して、 $r(X) = r(Y)$ を満たす

[証明] $X \subseteq K^m$ を満たす最小の $m$ に関する帰納法で示します。 $m = 0$ のときは成り立っています。 $m \ge 1$ とします。

$v \in (X \cap K^m) \setminus K^{m-1}$ が存在します。 $v = (a_1, a_2, \cdots, a_m)$ とすると $a_m \ne 0$ となります。 $X = \{u_1, u_2, \cdots, u_k, v\}$ 、 $u_i = (b_{i1}, b_{i2}, \cdots, b_{im})$ とします。 $Y = \{u_1 - \frac{b_{1m}}{a_m} v, u_2 - \frac{b_{2m}}{a_m} v, \cdots, u_k - \frac{b_{km}}{a_m} v\}$ とおくと $Y \subseteq K^{m-1}$ となります。

帰納法の仮定より $Y$ から行に関する基本変形と列に関する基本変形を繰り返して得られる $Z \subseteq E_n$ が存在して、 $r(Y) = r(Z)$ を満たします。 $Y +_1 \{v\}$ から列に関する基本変形で $Y +_1 \{e_m\}$ に変形できるので $r(X) = r(Y +_1 \{v\}) = r(Y +_1 \{e_m\}) = r(Z +_1 \{e_m\})$ となって $m$ のときにも成り立ちます。[証明終わり]