エレファントな線形代数(1) - エレファント・コンピューティング調査報告

連立一次方程式

拡大された掃き出し法の記法

連立一次方程式
$(*) \left\{ \begin{matrix} e_1(x_1, x_2, \cdots, x_n) & \iff & a_{11} x_1 + a_{12} x_2 + \cdots + a_{1n} x_n = b_1 \\ e_2(x_1, x_2, \cdots, x_n) & \iff & a_{21} x_1 + a_{22} x_2 + \cdots + a_{2n} x_n = b_2 \\ \vdots & & \vdots \\ e_m(x_1, x_2, \cdots, x_n) & \iff & a_{m1} x_1 + a_{m2} x_2 + \cdots + a_{mn} x_n = b_m \\ \end{matrix} \right.$
を、 $a_{11}, \cdots, a_{1n}, \cdots, a_{m1}, \cdots, a_{mn}, b_1, \cdots, b_m$ を文字と考えて、有理数全体の体 $\mathbb{Q}$ に付け加えて拡大した体 $K$ で考えます。「現代数学のエレファント」の記事でこの連立一次方程式を掃き出し法で解く方法を書こうとしましたが、記述が複雑になりすぎたため中断していました。ここではこの掃き出し法について、記述を簡単にすることを考えていきます。逆行列を行列式で表すことができることから、連立一次方程式の解は $K$ の元で表すことができます。以下ではまず $m = n$ の場合を考えます。

$e'_i(x_1, x_2, \cdots, x_n) \iff e_i(x_1, x_2, \cdots, x_n) - \cfrac{a_{i1}}{a_{11}} e_1(x_1, x_2, \cdots, x_n)$ ( $e_i(x_1, x_2, \cdots, x_n)$ の各項から $e_1(x_1, x_2, \cdots, x_n)$ の各項の $\cfrac{a_{i1}}{a_{11}}$ 倍を引いた方程式)とおくと
$\left\{ \begin{matrix} e_1(x_1, x_2, \cdots, x_n) & \iff & a_{11} x_1 & + & a_{12} x_2 + \cdots + a_{1n} x_n = b_1 \\ e'_2(x_1, x_2, \cdots, x_n) & \iff & & & a'_{22} x_2 + \cdots + a'_{2n} x_n = b'_2 \\ \vdots & & & & \vdots \\ e'_n(x_1, x_2, \cdots, x_n) & \iff & & & a'_{n2} x_2 + \cdots + a'_{nn} x_n = b'_n \\ \end{matrix} \right.$
となります( $a'_{ij} = a_{ij} - \cfrac{a_{i1}}{a_{11}} a_{1j}$ 、 $b'_{i} = b_{i} - \cfrac{a_{i1}}{a_{11}} b_{1}$ )。

$\left\{ \begin{matrix} e'_2(x_1, x_2, \cdots, x_n) & \iff & a'_{22} x_2 + \cdots + a'_{2n} x_n = b'_2 \\ \vdots & & \vdots \\ e'_n(x_1, x_2, \cdots, x_n) & \iff & a'_{n2} x_2 + \cdots + a'_{nn} x_n = b'_n \\ \end{matrix} \right.$
を満たす $(x_2, \cdots, x_n)$ と、 $f_i: V_i \to K$ 、 $f_i(x_{i+1}, \cdots, x_n) = x_i$ が存在すると仮定します $(i = 2, \cdots, n)$ 。 $n = 1$ のときは成り立っています。

$f_1: V_1 \to K$ を、 $x_1 = f_1(x_{2}, \cdots, x_n)$ のとき $a_{11} x_1 + a_{12} x_2 + \cdots + a_{1n} x_n = b_1$ を満たすもの、
$x_1 = f_1(x_{2}, \cdots, x_n) = - \left( \cfrac{a_{12}}{a_{11}} x_2 + \cdots + \cfrac{a_{1n}}{a_{11}} x_n \right) + \cfrac{b_{1}}{a_{11}}$
とおくと、 $(x_1, x_2, \cdots, x_n)$ は $e_1(x_1, x_2, \cdots, x_n)$ を満たします。

また $(x_1, x_2, \cdots, x_n)$ は $e'_i(x_1, x_2, \cdots, x_n)$ を満たす $(i = 2, \cdots, n)$ ので、
$e_i(x_1, x_2, \cdots, x_n) \iff e'_i(x_1, x_2, \cdots, x_n) + \cfrac{a_{i1}}{a_{11}} e_1(x_1, x_2, \cdots, x_n)$
を満たします $(i = 2, \cdots, n)$ 。

よって任意の $i = 1, 2, \cdots, n$ に対して $e_i(x_1, x_2, \cdots, x_n)$ となります。これは $(x_1, x_2, \cdots, x_n)$ が連立一次方程式 (*) の解であることを表します。

掃き出し法の順序に依存しない記法

上記の手順を $i = 1, 2, \cdots, n$ の順序に依存しない手順にすることを考えます。

$V = K^n$ 、 $U = \{u_1, u_2, \cdots, u_n\}$ を $V$ の基底とします。

一次方程式 $e: V \times K \to \{0, 1\}$ ( $1$ は「真」を、 $0$ は「偽」を表すとします)を、ある $a_1, a_2, \cdots, a_n, b \in K$ に対して $x_1 u_1 + x_2 u_2 + \cdots + x_n u_n \in V$ 、 $b \in K$ に $a_1 x_1 + a_2 x_2 + \cdots + a_n x_n = b$ を対応させる写像とします。

一次方程式 $e$ の解を $S(e) = \{ v \in V \mid e(v) \}$ 、一次方程式の有限集合 $E$ の解を $\displaystyle S(E) = \bigcap_{e \in E} S(e)$ とします。 $S(e)$ 、 $S(E)$ は $V$ の部分空間となります。

$E = E_1 + \{e_1\}$ ( $+$ は集合の直和)、 $U = U_1 + \{v_1\}$ とします。 $\displaystyle V_1 = \sum_{u \in U_1} K u$ とおくと $V = V_1 \oplus K v_1$ ( $\oplus$ はベクトル空間の直和)となります。

任意の $e \in E_1$ に対して
$e'(v) \iff e(v) + e_1(c_1v) \iff e'(v + K v_1)$
となる $c_1 \in K$ が存在します。ここで $e(v) + e'(v')$ は $e(v)$ の各項と $e'(v')$ の各項を足した方程式、 $V$ の部分集合 $X$ に対して $e(X)$ は任意の $v \in X$ に対して $e(v)$ であることを表すとします。 $E'_1$ を $e'$ 全体の集合とします。

$S(E_1) \cap S(e_1) = S(E'_1) \cap S(e_1)$

[証明]
$e(v) \land e_1(v) \iff ( e(v) + e_1(cv) ) \land e_1(v) \iff e'(v) \land e_1(v)$
より成り立ちます。[証明終わり]

$S(E'_1) = S(E'_1) + K v_1$

[証明] 任意の $e \in E_1$ に対して $e' \in e + Ke_1$ が存在して任意の $v \in V$ に対して
$v \in S(e') \iff v + K v_1 \subseteq S(e') \iff v \in S(e') + K v_1$
となります。よって
$\displaystyle S(E'_1) = \bigcap_{e' \in E'_1} S(e') = \bigcap_{e' \in E'_1} (S(e') + K v_1) \supseteq S(E'_1) + K v_1$
となって $S(E'_1) = S(E'_1) + K v_1$ となります。[証明終わり]

$S(E'_1) \cap V_1 \ne \varnothing \implies (S(E'_1) + K v_1) \cap S(e_1) \ne \varnothing$

[証明] $U_1 = \{ v_2, \cdots, v_n \}$ とします。 $i = 1, 2, \cdots, n$ に対して、 $f_i: V \to K$ を $f_i(v_i) =1$ 、 $i \ne j$ のとき $f_i(v_j) =0$ とします。任意の $v \in V$ に対して $v = f_1(v) v_1 + f_2(v) v_2 + \cdots + f_n(v) v_n$ となります。

$e_1(v)$ を $a_1 f_1(v) + a_2 f_2(v) + \cdots + a_n f_n(v) = b$ とします。 $v' \in S(E'_1) \cap V_1$ とし、 $c = \cfrac{-(a_2 f_2(v') + \cdots + a_n f_n(v')) + b}{a_1}$ 、 $v = c v_1 + f_2(v') v_2 + \cdots + f_n(v') v_n$ とおきます。 $a_1 f_1(v) = a_1 c = -(a_2 f_2(v') + \cdots + a_n f_n(v')) + b$ 、 $i = 2, \cdots, n$ に対して $a_i f_i(v) = a_i f_i(v')$ となるので $a_1 f_1(v) + a_2 f_2(v) + \cdots + a_n f_n(v) = b$ となり $e_1(v)$ が成り立ちます。[証明終わり]

よって $S(E'_1) \cap V_1 \ne \varnothing$ と仮定すると( $n = 1$ のときは成り立ちます)、
$S(E) = S(E_1) \cap S(e_1) = S(E'_1) \cap S(e_1) = (S(E'_1) + K v_1) \cap S(e_1) \ne \varnothing$
となります。

これは $v \in S(E)$ に対して $f_1(v), f_2(v), \cdots, f_n(v)$ が連立一次方程式 $E$ の解となることを表します。