2020-10-20

声に出して読めなくもない数学(2)

前回の議論を「エレファント化」していきます。すなわち、定義から数式の変換で証明できるようにしていきます。

$X$ を有限次元ベクトル空間 $V = K^\nu$ の有限部分集合とするとき、 $X$ の元の個数を $\#X$ 、 $X$ で張られた部分空間を $\langle X \rangle$ と書くことにします。 $\langle X_1 \cup \cdots \cup X_n \rangle$ を $\langle X_1, \cdots, X_n \rangle$ と書き、 $X_i = \{x\}$ のとき $X_i$ のかわりに $x$ と書いても良いということにします。 $X = Y \cup Z$ 、 $Y \cap Z = \varnothing$ のとき $X = Y + Z$ と書くことにします。 $X = Y + Z$ のとき $\#X = \#Y + \#Z$ となります。

1次独立と1次従属

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

(1) 空集合は1次独立
(2) $X$ は1次独立かつ $v \notin \langle X \rangle$ ならば $X + \{v\}$ は1次独立

空集合から (2) を繰り返してできる集合を1次独立とし、そうではない集合を1次従属とします。

(3) $X$ は1次独立かつ $X = Y + \{v\}$ ならば $Y$ は1次独立

[証明] $\#Y$ に関する帰納法で示します。 $\#Y = 0$ のときは1次独立の定義 (1) から成り立ちます。
$\#Y \ge 1$ として $\#Y$ より小さいときは成り立っていると仮定します。1次独立の定義より $X = Z + \{u\}$ を満たす1次独立な $Z$ とベクトル $u$ が存在します。 $Y = Z$ のときは成り立ちます。 $Y \ne Z$ とすると $u \ne v$ 、 $Y = (Y \cap Z) + \{u\}$ 、 $Z = (Y \cap Z) + \{v\}$ となります。帰納法の仮定より $Y \cap Z$ は1次独立となり、(2) より $Y$ は1次独立となります。[証明終わり]

(4) $X$ は1次独立かつ $Y \subseteq X$ ならば $Y$ は1次独立

[証明] (3) を繰り返せば成り立ちます。[証明終わり]

(5) $Y \subseteq X$ かつ $Y$ は1次従属ならば $X$ は1次従属

[証明] (4) より成り立ちます。[証明終わり]

(6) $v \in \langle X \rangle \setminus X$ ならば $X + \{v\}$ は1次従属

[証明] $v \in \langle X \rangle$ かつ $X + \{v\}$ は1次独立と仮定します。 $X + \{v\}$ は空集合ではないので (2) より $X + \{v\} = Y + \{w\}$ かつ $Y$ は1次独立、 $w \notin \langle Y \rangle$ である $V$ の部分集合 $Y$ と $w \in V$ が存在します。 $w = v$ または $w \in X$ となります。

$w = v$ のときは $X + \{v\} = Y + \{v\}$ かつ $v \notin \langle Y \rangle$ となります。 $X = Y$ となるので $v \notin \langle X \rangle$ となって $v \in \langle X \rangle$ に反します。

$w \in X$ のときは $X = X' + \{w\}$ となる $X$ の部分集合 $X'$ が存在します。 $X' + \{w\} + \{v\} = Y + \{w\}$ 、 $X' + \{v\} = Y$ 、 $v \in \langle X \rangle = \langle X', w \rangle$ となり、 $X' = \{u_1, u_2, \cdots, u_n\}$ とすると $v = a_1 u_1 + a_2 u_2 + \cdots + a_n u_n + bw$ と表すことができて $v \notin \langle X' \rangle$ より $b \ne 0$ となります。よって $w = \cfrac{1}{b}( -(a_1 u_1 + a_2 u_2 + \cdots + a_n u_n) + v ) \in \langle X', v \rangle = \langle Y \rangle$ となるので $w \notin \langle Y \rangle$ に反します。[証明終わり]

(7) $X + Y$ は1次独立、 $v \in \langle X, Y \rangle \setminus \langle Y \rangle$ ならば

$X^- = X \setminus \{u\}$ 、 $Y^+ = Y + \{v\}$ 、 $\langle X, Y \rangle = \langle X^-, Y^+ \rangle$ を満たす $u \in X$ が存在する
[証明] $X = \{u_1, u_2, \cdots, u_n\}$ 、 $Y = \{w_1, w_2, \cdots, w_m\}$ とすると $v = a_1 u_1 + a_2 u_2 + \cdots + a_n u_n + b_1 w_1 + b_2 w_2 + \cdots + b_m w_m$ と表すことができます。 $v \notin \langle Y \rangle$ よりある $a_k \ne 0$ となります。

$u = u_k$ 、 $X^- = X \setminus \{u\} = \{u'_1, u'_2, \cdots, u'_{n-1}\}$ とおきます。 $v = a_k u + a'_1 u'_1 + a'_2 u'_2 + \cdots + a'_{n-1} u'_{n-1} + b_1 w_1 + b_2 w_2 + \cdots + b_m w_m \in \langle X^-, Y, u \rangle$ 、 $u = \cfrac{1}{a_k}( -(a'_1 u'_1 + a'_2 u'_2 + \cdots + a'_{n-1} u'_{n-1}) - (b_1 w_1 + b_2 w_2 + \cdots + b_m w_m) + v ) \in \langle X^-, Y, v \rangle$ より $\langle X^-, Y, u \rangle \subseteq \langle X^-, Y, v \rangle$ かつ $\langle X^-, Y, v \rangle \subseteq \langle X^-, Y, u \rangle$ となって $\langle X^-, Y, u \rangle = \langle X^-, Y, v \rangle$ となります。 $\langle X, Y \rangle = \langle X^-, Y, u \rangle = \langle X^-, Y, v \rangle = \langle X^-, Y^+ \rangle$ となります。[証明終わり]

(8) $X, Y$ は1次独立、 $Y \subseteq \langle X \rangle$ ならば

$X = Y' + Z$ 、 $\#Y = \#Y'$ 、 $\langle X \rangle = \langle Y, Z \rangle$ 、 $Y \cap Z = \varnothing$ 、 $Y + Z$ は1次独立となる $Y', Z \subseteq X$ が存在する
[証明]
$n = \#Y$ に関する帰納法で示します。 $n = 0$ のときは $Y' = Y$ 、 $Z = X$ が条件を満たします。 $n \ge 1$ として $n-1$ のとき成り立つと仮定します。

$X = \{u_1, u_2, \cdots, u_{n-1}, u_n, u_{n+1}, \cdots, u_m\}$ 、 $Y = \{v_1, v_2, \cdots, v_{n-1}, v_n\}$ は1次独立で $Y \subseteq \langle X \rangle$ とします。

$Y_{n-1} = \{v_1, v_2, \cdots, v_{n-1}\}$ とおくと $Y_{n-1}$ は1次独立、 $Y_{n-1} \subseteq \langle X \rangle$ となるので帰納法の仮定より $X = Y'_{n-1} + Z_{n-1}$ 、 $\#Y_{n-1} = \#Y'_{n-1}$ 、 $\langle X \rangle = \langle Y_{n-1}, Z_{n-1} \rangle$ 、 $Y_{n-1} \cap Z_{n-1} = \varnothing$ 、 $Y_{n-1} + Z_{n-1}$ は1次独立となる $Y'_{n-1}, Z_{n-1} \subseteq X$ が存在します。 $X$ の順序を入れ替えて $X' = \{u'_1, u'_2, \cdots, u'_{n-1}, u'_n, u'_{n+1}, \cdots, u'_m\}$ としたとき $Y'_{n-1} = \{u'_1, u'_2, \cdots, u'_{n-1}\}$ 、 $Z_{n-1} = \{u'_n, u'_{n+1}, \cdots, u'_m\}$ とします。

$v_n \in Z_{n-1}$ のときは $Y' = Y'_{n-1} + \{v_{n}\}$ 、 $Z = Z_{n-1} \setminus \{v_{n}\}$ とおくと $X = Y' + Z$ 、 $\#Y = \#Y'$ 、 $\langle X \rangle = \langle Y, Z \rangle$ 、 $Y \cap Z = \varnothing$ 、 $Y + Z$ は1次独立となります。

$v_n \notin Z_{n-1}$ とします。

$v_n \in Y \subseteq \langle X \rangle = \langle Y_{n-1}, Z_{n-1} \rangle$ 、 $v_n \in \langle Y_{n-1}, Z_{n-1} \rangle \setminus \langle Y_{n-1} \rangle$ 、 $Y_{n-1} + Z_{n-1}$ は1次独立であることから (7) より $Z_{n} = Z_{n-1} \setminus \{w\}$ 、 $Y_n = Y _{n-1}+ \{v\}$ 、 $\langle Y_{n-1}, Z_{n-1} \rangle = \langle Y_{n}, Z_{n} \rangle$ を満たす $w \in Z_{n-1}$ が存在します。

$v_n \in \langle Y_{n-1}, Z \rangle$ とすると $w \in \langle Y, Z \rangle = \langle Y_{n-1}, Z, v_n \rangle = \langle Y_{n-1}, Z \rangle$
(6) より $Y_{n-1} + Z + \{w\} = Y_{n-1} + Z_{n-1}$ は1次従属となります。 $Y_{n-1} + Z_{n-1}$ は1次独立なので $v_n \notin \langle Y_{n-1}, Z \rangle$ となって (2) より $Y + Z$ は1次独立となります。

$v_n \notin Z_{n-1}$ なので $Y \cap Z = (Y _{n-1}+ \{v_n\}) \cap (Z_{n-1} \setminus \{w\}) = \varnothing$ となります。[証明終わり]

(9) $X, Y$ は1次独立、 $Y \subseteq \langle X \rangle$ ならば $\#Y \le \#X$

[証明] $m = \#X$ 、 $n = \#Y$ とおき、 $n \ge m$ とします。 $Y = Y_1 + Y_2, \ \#Y_1 = m$ となる $Y_1, Y_2$ をとることができます。(4) より $Y_1$ は1次独立となります。(8) より $X = X' + Y', \ \#Y_1 = \#Y', \ \langle X \rangle = \langle X', Y_1 \rangle$ を満たす $X', Y'$ が存在します。 $m = \#X = \#X' + \#Y' = \#X' + \#Y_1 = \#X' + m$ より $\#X' = 0$ となって $X' = \varnothing$ となります。 $Y_2 \subseteq Y \subseteq \langle X \rangle = \langle X', Y_1 \rangle = \langle Y_1 \rangle$ となって $Y_1$ は1次独立なので (6) より $Y_2 = \varnothing$ となります。 $n = \#Y = \#Y_1 + \#Y_2 = \#Y_1 = m$ より $n \ge m$ ならば $n = m$ となります。よって $n \le m$ となり $\#Y \le \#X$ となります。[証明終わり]

(10) $X, Y$ は1次独立、 $\langle X \rangle = \langle Y \rangle$ ならば $\#X = \#Y$

[証明] (9) より $\#Y \le \#X$ かつ $\#X \le \#Y$ となるので $\#X = \#Y$ となります。[証明終わり]

2020-10-10

声に出して読めなくもない数学(1)

無限の順序を指定する方法を考えるということがこのブログの1つの目的なのですが、そのためには数学の理論のイメージを持つ必要があると考えています。「声に出して読みたい…」というのが以前ありましたが、数学に置き換えると数式の操作を通じてイメージを得るということになるのでしょうか。そのための数式の操作の動画を作ることはできないかということを考えていきます。

普通の数式の操作の動画はすでに存在すると思われますので、ここでは帰納的な定義から導かれる操作について、論理プログラミング的な方法で操作をすることを考えていきます。論理プログラミング的な方法とは、「定義を書けば計算してくれる」のような意味です。ここではそのような計算ができる「エレファント電卓」を作っていって、そこで最終的に動画を作れるようにしたいと考えています。「エレファントなポアンカレ予想」の中で何でも計算でやるのは「エレファント」というのではないか、というようなことを書いたのでここでも「エレファント」という言葉を使いますが、本来の意味とは違うかもしれません。

ホモロジーの計算をやっていたら行列のランクの計算が出てきたので、まず行列のランクについて考えます。

行列のランク

体 $K$ の元を成分とする行列
$\hspace{4em} A = \begin{pmatrix} a_{11} & a_{12} & \cdots & a_{1n} \\ a_{21} & a_{22} & \cdots & a_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{m1} & a_{m2} & \cdots & a_{mn} \\ \end{pmatrix}$
の各行を $u_i = (a_{i1} , a_{i2} , \cdots , a_{in})$ $(i = 1, 2, \cdots , n)$ とおきます。 $u_i$ をベクトル空間 $K^n$ の元(ベクトルと呼びます)と考えます。 $\{u_1, u_2, \cdots , u_n\}$ の中の1次独立なベクトルの最大個数を行列 $A$ のランクと呼び $\operatorname{rank}(A)$ と書きます。

$\{u_1, u_2, \cdots , u_n\}$ を含む最小の $K^n$ の部分ベクトル空間(部分空間)を $\{u_1, u_2, \cdots , u_n\}$ によって張られた部分空間と呼びます。ここでは $\{\{u_1, u_2, \cdots , u_n\}\}$ と書きます。 $\{\{u_1, u_2, \cdots , u_n\}\} = \{a_1 u_1 + a_2 u_2 + \cdots + a_n u_n \mid a_1, a_2, \cdots , a_n \in K\}$ となります。 $\operatorname{rank}(A)$ は $\{\{u_1, u_2, \cdots , u_n\}\}$ の次元となります。

ベクトル空間の基底の個数が1次独立な元の最大個数と一致することは「群論の計算(17)」でも説明しましたが、また後で説明することにします。 $K^n$ の次元は $n$ となります。

行列のランクの帰納的定義

$\hspace{4em} A_k = \begin{pmatrix} a_{11} & a_{12} & \cdots & a_{1n} \\ a_{21} & a_{22} & \cdots & a_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{k1} & a_{k2} & \cdots & a_{kn} \\ \end{pmatrix}$
とおきます( $k \le m$ )。 $V_k = \{\{u_1, u_2, \cdots , u_k\}\}$ 、 $r_k = \operatorname{rank}(A_k) = \dim V_k$ とおきます。 $r_0 = 0$ 、 $r_m = \operatorname{rank}(A)$ 、
$\hspace{4em} \displaystyle r_{k+1} = \begin{cases} r_k & (u_{k+1} \in V_k \ のとき),\\ r_k + 1 & (u_{k+1} \notin V_k \ のとき) \end{cases}$
となります。

行列の基本変形

$V = \{\{u_1, u_2, \cdots , u_n\}\}$ とおきます。

ある $u_i \in \{u_1, u_2, \cdots , u_n\}$ を $u_i$ の $c$ 倍 $(c \in K \setminus \{0\})$ で置き換えたもので張られた部分空間を $V_1 = \{\{u_1, \cdots , cu_i, \cdots , u_n\}\}$ ( $i$ 番目が $cu_i$ )とすると、 $V = V_1$ となります。
ある $u_i\in \{u_1, u_2, \cdots , u_n\}$ を $u_i$ に $u_i$ とは異なる $u_j\in \{u_1, u_2, \cdots , u_n\}$ の $c$ 倍 $(c \in K)$ を加えたもので置き換えたもので張られた部分空間を $V_2 = \{\{u_1, \cdots , u_i + cu_j, \cdots , u_n\}\}$ ( $i$ 番目が $u_i + cu_j$ )とすると、 $V = V_2$ となります。
ある $u_i\in \{u_1, u_2, \cdots , u_n\}$ と $u_i$ とは異なる $u_j\in \{u_1, u_2, \cdots , u_n\}$ を入れ替えたもので張られた部分空間を $V_3 = \{\{u_1, \cdots , u_j , \cdots , u_i, \cdots , u_n\}\}$ ( $i$ 番目が $u_j$ 、 $j$ 番目が $u_i$ )とすると、 $V = V_3$ となります。

これらの操作

行列のある行 $u_i$ を $c$ 倍する $(c \in K \setminus \{0\})$
行列のある行 $u_i$ に別の行 $u_j$ の $c$ 倍を加える。 $(c \in K)$
行列のある行 $u_i$ と別の行 $u_j$ を入れ替える。

を行列の基本変形と呼びます。上に書いた議論により行列の基本変形によって行列のランクは変わりません。

これは列に対しても成り立ちます。列に対する操作も行列の基本変形と呼びます。これも後で説明します。

階段行列

$i \le k$ となる $i$ に対しては $i$ 行の成分は

先頭の $p_i$ 個の成分は $0$
$p_i+1$ 個目の成分は $1$

で、 $i \le k-1$ に対して $p_i < p_{i+1}$ であり、 $i \ge k+1$ となる $i$ に対しては $i$ 行の成分はすべて $0$ である
$\hspace{4em} \begin{pmatrix} 1 & a_{12} & a_{13} & a_{14} & a_{15} \\ 0 & 0 & 1 & a_{24} & a_{25} \\ 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \\ \end{pmatrix}$
のような行列を階段行列と呼びます。

$A$ の $k$ 行までを階段行列に変形した行列 $B_k$ を帰納的に作っていきます。 $B_0 = A$ 、 $l_0 = 0$ とおきます。 $k$ 行までを階段行列に変形したとき $l_k$ 列まで階段行列に変形されているとします。

$B_k$ から $B_{k+1}$ を作ります。 $B_k$ の $(i, j)$ 成分を $b(k,i,j)$ と書くことにします。

$\hspace{4em} \begin{matrix} b(k,k+1,l_k+1) & \cdots & b(k,k+1,n) \\ \vdots & \ddots & \vdots \\ b(k,m,l_k+1) & \cdots & b(k,m,n) \\ \end{matrix}$
の成分がすべて $0$ であるとき $B_k$ は階段行列となります。階段行列になったとき $k$ が $A$ のランクとなります。とくに $k=m$ のとき $B_k$ は階段行列となります。

そうではないときは $B_{k+1}$ を作ります。
$\hspace{4em} \begin{matrix} b(k,k+1,l_k+1) & \cdots & b(k,k+1,r-1) \\ \vdots & \ddots & \vdots \\ b(k,m,l_k+1) & \cdots & b(k,m,r-1) \\ \end{matrix}$
の成分がすべて $0$ である最大の $r$ をとります。

$b(k,k+1,r) = 0$ のときは $b(k,k',r) \ne 0$ であるような $k'$ 行を $k+1$ 行に加えて(または行を入れ替えて)得られる行を
$b'(k,k+1,1), b'(k,k+1,2), \cdots , b'(k,k+1,n)$
とすると、 $b'(k,k+1,r) \ne 0$ となります。

この行の各成分を $b'(k,k+1,r)$ で割った行を $B_{k+1}$ の $k+1$ 行、
$B_{k}$ の $k+2$ 行から $m$ 行までの各行を、その行( $s$ 行)の各成分から $B_{k+1}$ の $k+1$ 行の $b(k+1,s,r)$ 倍を引いたものを $B_{k+1}$ の $k+2$ 行から $m$ 行、
$B_{k}$ の $1$ 行から $k$ 行までの各行を $B_{k+1}$ の $1$ 行から $k$ 行

としたものを $B_{k+1}$ とします。 $l_{k+1} = r+1$ とします。

この $B_{k}$ から $B_{k+1}$ への1回の変形は

$b(k,k+1,r) = 0$ のときは「 $k'$ 行を $k+1$ 行に加える」または「 $k'$ 行と $k+1$ 行を入れ替える」
「 $k+1$ 行を $b'(k,k+1,r)$ で割る」
$k+2$ 行から $m$ 行までの $s$ 行に対して「 $s$ 行から $k+1$ 行の $b(k+1,s,r)$ 倍を引く」

という基本変形を続けたものになっています。

$k = m$ になれば階段行列になるので、この手順は $m$ 回以内に終了して階段行列ができます。

まずはこの一冊から意味がわかる線形代数 (BERET SCIENCE)

作者:石井俊全
発売日: 2014/12/05
メディア: Kindle版

線型代数 (ちくま学芸文庫)

作者:毅, 森
発売日: 2020/01/10
メディア: 文庫

2020-10-04

エレファントなポアンカレ予想(1)

ポアンカレ予想エレファントなポアンカレ予想

「論理プログラミング的ポアンカレ予想」は「エレファントなポアンカレ予想」に変更しました。エレガントではないものをエレファントというそうです。「補助線を1本引けば証明できる」というのがエレガントであるのに対して「計算すればできる」というのがエレファントとなります。この意味でホモロジー、ホモトピーの計算は非常にエレファントと言うことができます。これを論理プログラミング的な手法でさらにエレファントにすることができるか、ということが「エレファントなポアンカレ予想」の一連の記事の目標となります。

「はじめてのトポロジー」では曲面の分類を行っているので、この計算をやってみたいと思うのですが、曲面の定義は

ある図形 $M$ の上の任意の点 $P$ について、 $P$ の周囲が円板と同じ形をしているとき、その図形を曲面という。

となっています。これは「2次元多様体」のことを表していると考えられますが分類については「連結2次元閉多様体」の分類を行っていると考えられます。この定義もどこかに書かれているのかもしれませんがよくわかりません。

このままでは計算をするのは難しいということと、ホモロジーの計算には三角形に分割すれば良いらしいということで三角形で考えることにして、

有限個の三角形を辺のところでつなげたもので
任意の三角形の辺には別の1つの三角形がつながっていて
任意の三角形から別の三角形に隣の三角形をたどって到達することができる

という図形に同相であるものをここでは曲面と呼ぶことにします。

多様体、同相の定義はなくても計算はできそうなので定義は後回しとします。

この本には証明は載っていないようですが、曲面の分類について以下のようなことが書かれています。証明は三角形に分割すればできるらしいです。

定義

曲面 $M$ 上の閉曲線を曲面上の切断線といい、その切断線が曲面を2つの部分に分けるとき、その閉曲線をホモローグ0の切断線という。
球面上の切断線はすべてホモローグ0です。このことを「球面の1次元ホモロジー群は0である」といいます。
トーラスのホモローグ0でない切断線の様子を表す $\mathbb{Z} \oplus \mathbb{Z}$ をトーラスの1次元ホモロジー群といいます。

定理(曲面の1次元ホモロジー群)

球面 $S$ : $H_1(S) = 0$
種数 $n$ のトーラス $T_n$ : $H_1(T_n) = \mathbb{Z} \oplus \mathbb{Z} \oplus \cdots \oplus \mathbb{Z}$ ( $2n$ 個)
クライン管 $K$ : $H_1(K) = \mathbb{Z} \oplus \mathbb{Z}_2$
射影平面 $P$ : $H_1(P) = \mathbb{Z}_2$