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

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

前回の議論では何が解となるのか明確には書いていなかったので、わかるように書き直したいと思います。

連立一次方程式
$(*) \left\{ \begin{matrix} e_1(x_1, x_2, \cdots, x_n) & \iff & \alpha_{11} x_1 + \alpha_{12} x_2 + \cdots + \alpha_{1n} x_n = \beta_1 \\ e_2(x_1, x_2, \cdots, x_n) & \iff & \alpha_{21} x_1 + \alpha_{22} x_2 + \cdots + \alpha_{2n} x_n = \beta_2 \\ \vdots & & \vdots \\ e_n(x_1, x_2, \cdots, x_n) & \iff & \alpha_{n1} x_1 + \alpha_{n2} x_2 + \cdots + \alpha_{nn} x_n = \beta_n \\ \end{matrix} \right.$
を、有理数全体の体 $\mathbb{Q}$ に $\alpha_{11}, \cdots, \alpha_{1n}, \cdots, \alpha_{n1}, \cdots, \alpha_{nn}, \beta_1, \cdots, \beta_n$ を付け加えて拡大した体 $K$ で考えます。逆行列を行列式で表すことができることから、連立一次方程式の解は $K$ の元で表すことができます。

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

$W = K^n$ とし、一次方程式 $a_1 x_1 + a_2 x_2 + \cdots + a_n x_n = b$ を $(a_1, a_2, \cdots, a_n, b) \in W \times K$ と表します。一次方程式全体の集合を $\mathcal{E} = W \times K$ とおきます。 $\mathcal{E}$ は $K$ 上のベクトル空間となります。

$h: \mathcal{E} \times V \to \{0, 1\}$ ( $1$ は「真」を、 $0$ は「偽」を表すとします)を、 $e = (a_1, a_2, \cdots, a_n, b) \in \mathcal{E}$ と $v = x_1 u_1 + x_2 u_2 + \cdots + x_n u_n \in V$ に対して、 $a_1 x_1 + a_2 x_2 + \cdots + a_n x_n = b$ のとき $h(e, v) = 1$ 、 $a_1 x_1 + a_2 x_2 + \cdots + a_n x_n \ne b$ のとき $h(e, v) = 0$ とします。

$i = 1, 2, \cdots, n$ に対して、 $\mathcal{Q}^*_i = \{ r \in \mathcal{E} \mid h(r, u_i) = 1 \}$ 、 $\displaystyle \mathcal{Q}_i = \bigcap_{j \in \{1, 2, \cdots, n\} \setminus \{ i \}} \mathcal{Q}^*_j$ 、 $\mathcal{R} = \mathcal{Q}_1 \cup \mathcal{Q}_2 \cup \cdots \cup \mathcal{Q}_n$ とおきます。

(1) 任意の $e_1, e_2 \in \mathcal{E}$ 、 $i \in \{1, 2, \cdots, n\}$ に対して $(e_1 + K e_2) \cap \mathcal{Q}^*_i = K e$ となる $e \in \mathcal{E}$ が存在します。

[証明] $e_1$ を $a_{11} x_1 + a_{12} x_2 + \cdots + a_{1n} x_n = b_1$ 、 $e_2$ を $a_{21} x_1 + a_{22} x_2 + \cdots + a_{2n} x_n = b_2$ とするとき、 $e = e_1 - \cfrac{a_{1i}}{a_{2i}} e_2$ は $e(u_i)$ を満たします。[証明終わり]

$e \in \mathcal{E}$ に対して $S(e) = \{ v \in V \mid h(e, v) = 1 \}$ 、 $E \subseteq \mathcal{E}$ に対して $\displaystyle S(E) = \bigcap_{e \in E} S(e)$ とします。 $S(e)$ 、 $S(E)$ は $V$ の部分空間となります。

$S(E) = S(R)$ かつ $R \subseteq \mathcal{R}$ となる $R$ を $E$ の解とします。このとき $E \twoheadrightarrow R$ と書くことにします。 $R$ は一意的にはなりませんがここではこの形で議論を進めます。

$E_0$ を連立一次方程式(*)とします。 $U_0 = U$ とします。

$E_i = E'_{i+1} + \{ e_i \}$ 、 $U_i = U_{i+1} + \{ v_i \}$ ( $+$ は集合の直和)とします。

$\displaystyle V_i = \sum_{u \in U_i} K u$ とおくと $V_i = V_{i+1} \oplus K v_{i+1}$ ( $\oplus$ はベクトル空間の直和)となります。

$E''_i = \{ e \in E'_i + K e_i \mid h(e, v_i) = 1 \}$
$\displaystyle = \bigcup_{e' \in E'_i} \{ e \in e' + K e_i \mid h(e, v_i) = 1 \}$ とおきます。
$E''_i$ の元の中から $e \in \{ e \in e' + K e_i \mid h(e, v_i) = 1 \}$ で $e \ne 0$ であるものを一つずつ集めた集合を $E_i$ とおきます。

$\mathcal{R}^*_i = \{ r \in \mathcal{E} \mid h(r, v_i) = 1 \}$ 、 $\displaystyle \mathcal{R}_i = \bigcap_{j \in \{1, 2, \cdots, n\} \setminus \{ i \}} \mathcal{R}^*_j$ とおきます。

(2) $S(E'_i) \cap S(e_i) = S(E_i) \cap S(e_i)$

[証明] $e' \in E'_i$ をとると(1)より $(e' + K e_i) \cap \bar{\mathcal{R}}_i = K e$ となる $e \in \mathcal{E}$ が存在します。 $a e = e' + c e_i$ となる $a, c \in K$ が存在します。
$h(e', v) = h(e_i, v) = 1 \iff h(e' + c e_i, v) = h(e_i, v) = 1 \iff h(ae, v) = h(e_i, v) = 1$
より $S(E'_i) \cap S(e_i) = S(E_i) \cap S(e_i)$ となります。[証明終わり]

(3) $S(E_i) = S(E_{i+1}) \cap S(e_{i+1})$

[証明] (2)より $S(E_i) = S(E'_{i+1}) \cap S(e_{i+1}) = S(E_{i+1}) \cap S(e_{i+1})$ となります。[証明終わり]

(4) $E_{i} \subseteq \mathcal{R}^_1 \cap \mathcal{R}^_2 \cap \cdots \cap \mathcal{R}^*_i$

[証明] $E_{i}$ の定義より $E_{i} \subseteq \mathcal{R}^*_i$ となって $E_{i}, E_{i+1}, \cdots \subseteq \mathcal{R}^*_i$ となるので成り立ちます。[証明終わり]

(5) $E_{n-1} \subseteq \mathcal{R}$

[証明] (4) り $E_{n-1} \subseteq \mathcal{R}^*_1 \cap \mathcal{R}^*_2 \cap \cdots \cap \mathcal{R}^*_{n-1}$ となるので成り立ちます。[証明終わり]

(6) $E_{i+1} \twoheadrightarrow R_{i+1}$ 、 $R_{i+1} = \{ r_{i+2}, \cdots, r_n \}$ ならば $E_{i} \twoheadrightarrow R_{i}$ 、 $R_{i} = R_{i+1} + \{ r_{i+1} \}$ となる $R_{i}$ が存在します。

[証明] $S(E_{i+1}) = S(R_{i+1})$ かつ $R_{i+1} \subseteq \mathcal{R}$ とします。 $E_i = E_{i+1} + \{ e_{i+1} \}$ であり、 $r_{i+1} \in (e_{i+1} + V_{i+1}) \cap \mathcal{R}^*_{i+1} \cap \cdots \cap \mathcal{R}^*_{n-1}$ かつ $r_{i+1} \ne 0$ となる $r_{i+1}$ が存在します。 $R_i = R_{i+1} + \{ r_{i+1} \}$ とおくと $S(E_{i}) = S(R_{i})$ かつ $R_{i} \subseteq \mathcal{R}$ となります。[証明終わり]

(7) $E_{0} \twoheadrightarrow R_0$ となる $R_0$ が存在します。

[証明] (6)より
$\begin{eqnarray*} & & E_0 \twoheadrightarrow R_0 \mathop{となる} R_0 \mathop{が存在する} \\ & \Longleftarrow & E_1 \twoheadrightarrow R_1 \mathop{となる} R_1 \mathop{が存在する} \\ & \Longleftarrow & \\ & \vdots & \\ & \Longleftarrow & E_{n-1} \twoheadrightarrow R_{n-1} \mathop{となる} R_{n-1} \mathop{が存在する} \\ \end{eqnarray*}$
となります。最後の項は(5)より $R_{n-1} = E_{n-1}$ とおけば成り立ちます。[証明終わり]