エレファント・コンピューティング調査報告

極限に関する順序を論理プログラミングの手法を使って指定することを目指すブロクです。

現代数学のエレファント(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)  m \le n のとき  K^m の有限部分集合  X に対して
    •  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 のときにも成り立ちます。[証明終わり]

 m n 列の行列  M k 列目を有限次元ベクトル空間  K^m の元と見たものを  M_k とするとき  W_M = \{M_1, M_2, \cdots, M_n\} とします。 r(W_M) M の列に関するランクと呼びます。

  • (18) 行列  M の列に関するランクは行列  M の(行に関する)ランクと等しい
  • (19) 行列  M は行に関する基本変形で行に関する階段行列に変形できる
  • (20) 行列  M は列に関する基本変形で列に関する階段行列に変形できる

これで行列のランクを定義から計算できるようになったのですが、 +_1 +_2 の定義があまり良くないような気もするので、次回以降はこのあたりを修正して計算をやっていきたいと思います。

線形性・固有値・テンソル <線形代数>応用への最短コース (KS理工学専門書)

線形性・固有値・テンソル <線形代数>応用への最短コース (KS理工学専門書)

  • 作者:原 啓介
  • 発売日: 2019/02/24
  • メディア: 単行本(ソフトカバー)