声に出して読めなくもない数学(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$ 行