現代数学のエレファント(6) - エレファント・コンピューティング調査報告

ガウスの消去法

Wikipediaによると、ガウスの消去法(または掃き出し法)は連立一次方程式の解法に使われるものですが

行列の階数の計算
行列式の計算
正則行列の逆行列の計算

でも使われます。

この記事は行列式や行列のランクを定義から計算できるようにすることが目的なのですが、行列式は定義から直接計算でき、行列式と行列のランクは行列式で表すことができるので、これらも定義から直接計算できると言えます。しかし定義と計算方法の関連がわかりにくいため、ここでは掃き出し法との関連を調べて掃き出し法の方法で計算する方法を考えます。

連立一次方程式の解法(1)

$K$ を体とします。連立一次方程式
$\begin{eqnarray*} a_{11} x_1 + a_{12} x_2 + \cdots + a_{1,n-1} x_{n-1} + a_{1n} x_n & = & y_1 \\ a_{21} x_1 + a_{22} x_2 + \cdots + a_{2,n-1} x_{n-1} + a_{2n} x_n & = & y_2 \\ \vdots \hspace{4em} & & \\ a_{m1} x_1 + a_{m2} x_2 + \cdots + a_{m,n-1} x_{n-1} + a_{mn} x_n & = & y_m \\ \end{eqnarray*}$
に $a_{ij} = 0$ である $a_{ij}$ を追加して $m=n$ となるようにしても連立一次方程式としては同じものを表しているので、まず $m=n$ の場合を考えます。

(1-1) 第 $n$ 式の両辺をを $a_{nn}$ で割った
$\cfrac{a_{n1}}{a_{nn}} x_1 + \cdots + \cfrac{a_{n,n-1}}{a_{nn}} x_{n-1} + x_n = \cfrac{1}{a_{nn}} y_n$
を考えます。
$a_{nn} = 0$ のときは割ることはできないのですが、逆行列は行列式で書けるので、行列式が $0$ でなければこのまま進めることができます( $a_{nn}$ を変数と考えて $K$ に変数 $a_{nn}$ を追加した体(有理関数体 $K(a_{nn})$ )を考えれば良い)。本来の掃き出し法では係数は実際の数値で行うので、係数が $0$ ではない変数を見つけなければなりません。これについては後で考えます。

(1-2) 第 $i$ 式( $i= 1, \cdots, n-1$ )から第 $n$ 式の $a_{in}$ 倍を引くと
$\begin{eqnarray*} (a_{11} - \cfrac{a_{n1}a_{1n}}{a_{nn}}) x_1 + \cdots + (a_{1,n-1} - \cfrac{a_{n,n-1}a_{1n}}{a_{nn}}) x_{n-1} & = & y_1 - \cfrac{a_{1n}}{a_{nn}} y_n \\ (a_{21} - \cfrac{a_{n1}a_{2n}}{a_{nn}}) x_1 + \cdots + (a_{2,n-1} - \cfrac{a_{n,n-1}a_{2n}}{a_{nn}}) x_{n-1} & = & y_2 - \cfrac{a_{2n}}{a_{nn}} y_n \\ \vdots \hspace{4em} & & \\ (a_{n-1,1} - \cfrac{a_{n1}a_{n-1,n}}{a_{nn}}) x_1 + \cdots + (a_{n-1,n-1} - \cfrac{a_{n,n-1}a_{n-1,n}}{a_{nn}}) x_{n-1} & = & y_{n-1} - \cfrac{a_{n-1,n}}{a_{nn}} y_n \\ \cfrac{a_{n1}}{a_{nn}} x_1 + \cdots + \cfrac{a_{n,n-1}}{a_{nn}} x_{n-1} + x_n & = & \cfrac{1}{a_{nn}} y_n \end{eqnarray*}$
となります。

第 $1$ 式から第 $n-1$ 式までは $n-1$ 個の変数に関する $n-1$ 個の連立一次方程式となるので、 $n$ に関する帰納法によりこの解 $x_1, \cdots, x_{n-1}$ が決まったとすると、
(1-3) $x_n = \cfrac{1}{a_{nn}} y_n - (\cfrac{a_{n1}}{a_{nn}} x_1 + \cdots + \cfrac{a_{n,n-1}}{a_{nn}} x_{n-1})$
によって $x_n$ が決まります。

よって $n$ に関する帰納法により $x_1, \cdots, x_n$ が決まります。

連立一次方程式の解法(2)

上記の議論を書き直します。

$K$ を体、 $V$ を $K$ 上の $n$ 次元ベクトル空間、 $\{e_1, e_2, \cdots, e_n\}$ を $V$ の基底、 $W$ を $K$ 上の $m$ 次元ベクトル空間、 $\{e'_1, e'_2, \cdots , e'_m\}$ を $W$ の基底とします。

$f_j \in V^{*}$ を $f_j(e_i) = \delta_{ij}$ 、 $g_i \in \mathcal{L}(K, W)$ を $g_i(a) = ae'_i$ とおくと、 $\mathcal{L}(V, W)$ の元は $\displaystyle \sum_{i=1}^{m} \sum_{j=1}^{n} a_{ij} g_i f_j$ ( $a_{ij} \in K$ )と表すことができます。ここで $\delta_{ij}$ は
$\delta_{ij} = \begin{cases} 0 & (i \ne j \ のとき) \\ 1 & (i = j \ のとき) \end{cases}$
を表すものとします。 $\mathcal{L}(V^k, W^k)$ のときもこの記法を使うことにします。

$a_1, a_2, \cdots, a_n \in K$ に対して $f^*(a_1, a_2, \cdots, a_n) \in V^*$ を $f^*(a_1, a_2, \cdots, a_n) = a_1 f_1 + a_2 f_2 + \cdots + a_n f_n$ とします。 $b_1, b_2, \cdots, b_m \in \mathcal{L}(K, V)$ に対して $g^*(b_1, b_2, \cdots, b_m) \in \mathcal{L}(V, W)$ を $g^*(b_1, b_2, \cdots, b_m) = b_1 g_1 + b_2 g_2 + \cdots + b_m g_m$ とします。 $\mathcal{L}(V^k, W^k)$ のときもこの記法を使うことにします。記法については後で検討しますがとりあえず今はこの記法でやっていきます。

まず $n = m$ 、 $V = W$ の場合を考えます。

$x = x_1 e_1 + \cdots + x_n e_n$ 、 $y = y_1 e_1 + \cdots + y_n e_n$ に関する連立一次方程式は $\displaystyle \sum_{i=1}^{n} \sum_{j=1}^{n} a_{ij} g_i f_j x = y$ と表すことができます。

$\psi_n = g^*(f_1 - a_{1n} f_n, \cdots, f_{n-1} - a_{n-1,n} f_n, f_n) g^*(f_1, \cdots, f_{n-1}, \cfrac{1}{a_{nn}} f_n)$ 、
$\sigma_n = g^*(f_1, \cdots, f_{n-1}, f_n - (\cfrac{a_{n1}}{a_{nn}} f_1 + \cdots + \cfrac{a_{n,n-1}}{a_{nn}} f_{n-1}))$
とおきます。 $\psi_n$ は (1-1)、(1-2) を表したもの、 $\sigma_n$ は (1-3) を表したものとなります。

このとき帰納法の仮定により
$\displaystyle \varphi_{n-1} \psi_n \sum_{i=1}^{n} \sum_{j=1}^{n} a_{ij} g_i f_j = g^*(f_1, \cdots, f_{n-1}, h_n)$ 、
$\displaystyle h_n = g_n f_n \psi_n \sum_{i=1}^{n} \sum_{j=1}^{n} a_{ij} g_i f_j$
を満たす $\varphi_{n-1}$ が存在するとします。

$\varphi_{n} = \sigma_n \varphi_{n-1} \psi_n$ とおくと $\displaystyle \varphi_{n} \sum_{i=1}^{n} \sum_{j=1}^{n} a_{ij} g_i f_j = 1_V$ となります( $1_V$ は $V$ の恒等写像)。よって
$\begin{eqnarray*} x & = & \varphi_{n} \sum_{i=1}^{n} \sum_{j=1}^{n} a_{ij} g_i f_j x \\ & = & \sigma_n \varphi_{n-1} \psi_n \sum_{i=1}^{n} \sum_{j=1}^{n} a_{ij} g_i f_j x \\ & = & \sigma_n \varphi_{n-1} \psi_n y \\ & = & \varphi_{n} y \\ \end{eqnarray*}$
となります。

逆行列

逆行列の求め方は連立一次方程式の解法と同様となります。 $1_V$ を $V$ の恒等写像とします。 $\beta: V \to V$ を線型写像で
$\displaystyle \sum_{i=1}^{n} \sum_{j=1}^{n} a_{ij} g_i f_j \beta = 1_V$
を満たすものとします。 $\varphi_{n}$ を上と同様のものとすると
$\displaystyle \beta = \varphi_{n} \sum_{i=1}^{n} \sum_{j=1}^{n} a_{ij} g_i f_j \beta = \varphi_{n} 1_V = \varphi_{n}$
となります。 $\varphi_{n}$ を行列で表したものは行列 $(a_{ij})$ の逆行列となります。

行列式

$\displaystyle \alpha = \sum_{i=1}^{n} \sum_{j=1}^{n} a_{ij} g_i f_j$ とすると行列式の定義より
$\displaystyle \bigwedge_{i=1}^{n} g_i f_i \sum_{i=1}^{n} \sum_{j=1}^{n} a_{ij} g_i f_j = \bigwedge_{i=1}^{n} g_i f_i \alpha = (\det \alpha ) \bigwedge_{i=1}^{n} g_i f_i$
となります。

$\varphi_{n}$ を上と同様のものとすると行列式の性質から
$\displaystyle \bigwedge_{i=1}^{n} g_i f_i = \bigwedge_{i=1}^{n} g_i f_i \varphi_n \sum_{i=1}^{n} \sum_{j=1}^{n} a_{ij} g_i f_j = (\det \alpha ) (\det \varphi_n) \bigwedge_{i=1}^{n} g_i f_i$
となって $\det \alpha = \cfrac{1}{\det \varphi_n}$ となります。

$\det g^*(f_1, \cdots, f_{n-1}, \cfrac{1}{a_{nn}} f_n) = \cfrac{1}{a_{nn}}$ 、
$\det g^*(f_1 - a_{1n} f_n, \cdots, f_{n-1} - a_{n-1,n} f_n, f_n) = 1$
より $\det \psi_n = \cfrac{1}{a_{nn}}$ 、
$\det g^*(f_1, \cdots, f_{n-1}, f_n - (\cfrac{a_{n1}}{a_{nn}} f_1 + \cdots + \cfrac{a_{n,n-1}}{a_{nn}} f_{n-1})) = 1$
より $\det \sigma_n = 1$ となります。

$\varphi_{n} = \sigma_n \cdots \sigma_1 \psi_1 \cdots \psi_n$ なので
$\det \varphi_{n} = (\det \sigma_n) \cdots (\det \sigma_1) (\det \psi_1) \cdots (\det \psi_n) = (\det \psi_1) \cdots (\det \psi_n)$
となります。 $\alpha _k= \psi_{k+1} \psi_{k+2} \cdots \psi_{n} \alpha$ とおいて $\displaystyle \alpha_k = \sum_{i=1}^{k} \sum_{j=1}^{k} a(k, i, j) g_i f_j$ とすると帰納的に $a(k, i, j)$ を
$a(k-1, i, j) = \cfrac{a(k, i, j) a(k, k, k) - a(k, i, k) a(k, k, j)}{a(k, k, k)}$
によって決めることができます。
$\det \alpha = a(1,1,1) a(2,2,2) \cdots a(n,n,n)$
となります。

掃き出し法の多重線型性・交代性

$d(\alpha) = a(1,1,1) a(2,2,2) \cdots a(n,n,n)$ と定義すると
$a(k-1, i, j) = \cfrac{a(k, i, j) a(k, k, k) - a(k, i, k) a(k, k, j)}{a(k, k, k)}$
より $a(k, i, k) = b(i) + c(i)$ とすると
$\hspace{1em} \begin{eqnarray*} a(k-1, i, j) & = & \cfrac{a(k, i, j) ( b(k) + c(k) ) - ( b(i) + c(i) ) a(k, k, j)}{ a(k, k, k) } \\ & = & \cfrac{a(k, i, j) b(k) - b(i) a(k, k, j)}{ a(k, k, k) } + \cfrac{a(k, i, j) c(k) - c(i) a(k, k, j)}{ a(k, k, k) } \\ \end{eqnarray*}$
$a(k, i, k) = cb(i)$ とすると
$\hspace{1em} \begin{eqnarray*} a(k-1, i, j) & = & \cfrac{a(k, i, j) cb(k) - cb(i) a(k, k, j)}{ cb(k) } \\ & = & \cfrac{a(k, i, j) b(k) - b(i) a(k, k, j)}{ b(k) } \end{eqnarray*}$
$a(k, i, k) = a(k, i, l)$ とすると
$\hspace{1em} \begin{eqnarray*} a(k-1, i, l) & = & \cfrac{a(k, i, l) a(k, k, k) - a(k, i, k) a(k, k, l)}{a(k, k, k)} \\ & = & \cfrac{a(k, i, k) a(k, k, k) - a(k, i, k) a(k, k, k)}{a(k, k, k)} = 0 \end{eqnarray*}$
が成り立ちます。これは任意の列で成り立つので $d$ は

(多重線型性)
- 任意の $u_1, \cdots, u_{k-1}, u_{k+1}, \cdots, u_n, v, w \in \mathcal{L}(K, V)$ に対して $d(g^*(u_1, \cdots, u_{k-1}, v + w, u_{k+1}, \cdots, u_n))$ $= d(g^*(u_1, \cdots, u_{k-1}, v, u_{k+1}, \cdots, u_n)) + d(g^*(u_1, \cdots, u_{k-1}, w, u_{k+1}, \cdots, u_n))$
- 任意の $u_1, \cdots, u_{k-1}, v, u_{k+1}, \cdots, u_n, v \in \mathcal{L}(K, V)$ 、任意の $a \in K$ に対して $d(g^*(u_1, \cdots, u_{k-1}, a v, u_{k+1}, \cdots, u_n))$ $= a d(g^*(u_1, \cdots, u_{k-1}, v, u_{k+1}, \cdots, u_n))$
(交代性)
- 任意の $u_1, \cdots, u_{k-1}, u_{k+1}, \cdots, u_{l-1}, u_{l+1}, \cdots, u_n, v \in \mathcal{L}(K, V)$ 、 $k \ne l$ に対して $d(g^*(u_1, \cdots, u_{k-1}, v, u_{k+1}, \cdots, u_{l-1}, v, u_{l+1}, \cdots, u_n)) = 0$