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

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

解が一意的となるように書き直したいと思います。

有理数全体の体 $\mathbb{Q}$ に $\alpha_{11}, \cdots, \alpha_{1n}, \cdots, \alpha_{n1}, \cdots, \alpha_{nn}, \beta_1, \cdots, \beta_n$ を付け加えて拡大した体を $K$ とします。

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

$W = K^n$ とし、ベクトル空間 $W^+ = W \times K$ の部分空間全体の集合を $\mathcal{P}$ とします。
$\mathcal{E} = \{ Kw \mid w \in W^+ \} \subseteq \mathcal{P}$ とおきます。 $\mathcal{E}$ の元 $K(a_1, a_2, \cdots, a_n, b)$ が一次方程式 $a_1 x_1 + a_2 x_2 + \cdots + a_n x_n = b$ を表すとします。

$h: \mathcal{E} \times V \to \{0, 1\}$ ( $1$ は「真」を、 $0$ は「偽」を表すとします)を、 $e = K(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$ とおきます。

$\mathcal{E}' \subseteq \mathcal{E}$ に対して $\mathcal{E}'$ の元すべての $W^+$ の部分空間としての和を $\sum \mathcal{E}'$ と書くことにします。

(1) 任意の $e_1, e_2 \in \mathcal{E}$ 、 $i \in \{1, 2, \cdots, n\}$ に対して、 $W^+$ の部分空間として $e \subseteq (e_1 + e_2) \cap \sum \mathcal{Q}^*_i$ となる $e \in \mathcal{E}$ が一意的に存在します。

[証明] $w_1$ を $a_{11} x_1 + a_{12} x_2 + \cdots + a_{1n} x_n = b_1$ 、 $w_2$ を $a_{21} x_1 + a_{22} x_2 + \cdots + a_{2n} x_n = b_2$ とすると、
$h(K(c_1 w_1 + c_2 w_2), u_i) = 1 \iff c_1 a_{1i} + c_2 a_{2i} = 0$
となります。

$w = w_1 - \cfrac{a_{1i}}{a_{2i}} w_2$ は $h(Kw, u_i) = 1$ を満たし、 $w \in K w_1 + K w_2$ より $K w \subseteq K w_1 + K w_2$ となります。

逆に $w = c_1 w_1 + c_2 w_2$ 、 $h(Kw, u_i) = 1$ とすると $w = c_1 (w_1 - \cfrac{a_{1i}}{a_{2i}} w_2) \in K (w_1 - \cfrac{a_{1i}}{a_{2i}} w_2)$ となります。よって $K w = K (w_1 - \cfrac{a_{1i}}{a_{2i}} w_2)$ となるので、このような $K w$ は一意的となります。[証明終わり]

$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$ と書くことにします。 $E \twoheadrightarrow R$ となる $R$ が存在することを $E \twoheadrightarrow_\exists R$ と書くことにします。

$E_0 \subseteq \mathcal{E}$ を
$\left\{ \begin{matrix} \alpha_{11} x_1 + \alpha_{12} x_2 + \cdots + \alpha_{1n} x_n = \beta_1 \\ \alpha_{21} x_1 + \alpha_{22} x_2 + \cdots + \alpha_{2n} x_n = \beta_2 \\ \vdots \\ \alpha_{n1} x_1 + \alpha_{n2} x_2 + \cdots + \alpha_{nn} x_n = \beta_n \\ \end{matrix} \right.$
に対応する一次方程式の集合、 $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$ はベクトル空間の直和)となります。

$\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$ とおきます。

$e_1, e_2 \in \mathcal{E}$ 、 $i \in \{1, 2, \cdots, n\}$ に対して $e \subseteq (e_1 + e_2) \cap \sum \mathcal{R}^*_i$ となる $e \in \mathcal{E}$ を $d(e_1, e_2, v_i)$ と書くことにします。

$E_{i+1} = \{ d(e', e_i, v_{i+1}) \mid e' \in E'_{i+1} \}$ とおきます。

(2) $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_1, e_2 \in \mathcal{R}^*_j$ とすると $d(e_1, e_2, v_i) \subseteq e_1 + e_2$ であることから $d(e_1, e_2, v_i) \in \mathcal{R}^*_j$ となります。よって $E_{i} \subseteq \mathcal{R}^*_j$ ならば $E_{i+1} \subseteq \mathcal{R}^*_j$ となります。

よって主張が成り立ちます。[証明終わり]

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

[証明] $e' \in E'_i$ をとり、 $e'$ を $Kw'$ 、 $e_i$ を $Kw''$ 、 $d(e', e_i, v_i)$ を $Kw$ とおくと。 $w \in Kw' + Kw''$ となります。 $w = aw' + bw''$ となる $a, b \in K$ が存在します。 $x = aw'$ 、 $y = bw''$ とおくと、 $w = x + y$ となります。 $e' \in E'_i$ をとると
$\begin{eqnarray*} v \in S(e') \cap S(e_i) & \iff & h(e', v) = h(e_i, v) = 1 \\ & \iff & h(Kx, v) = h(Ky, v) = 1 \\ & \iff & h(Kw, v) = h(Ky, v) = 1 \\ & \iff & h(d(e', e_i, v_i), v) = h(e_i, v) = 1 \\ & \iff & v \in S(d(e', e_i, v_i)) \cap S(e_i) \end{eqnarray*}$
となります。よって $S(E'_i) \cap S(e_i) = S(E_i) \cap S(e_i)$ となります。[証明終わり]

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

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

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

[証明] (2) より $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 \}$ 、 $r_{j} \in \mathcal{R}^*_{j}$ 、 $E_i = E_{i+1} + \{ e_{i+1} \}$ ならば $E_{i} \twoheadrightarrow R_{i}$ となる $R_{i}$ が存在します。

[証明] $S(E_{i+1}) = S(R_{i+1})$ かつ $R_{i+1} \subseteq \mathcal{R}$ 、 $R_{i+1} = \{ r_{i+2}, \cdots, r_n \}$ ( $r_{j} \in \mathcal{R}^*_{j}$ )とします。

$d(e_i, r_j, v_j)$ を $e_i -_d (r_j, v_j)$ をと書くことにします。 $e_i \in \mathcal{R}^*_{i}$ 、 $r_j \in \mathcal{R}_{j}$ のとき $e_i -_d (r_j, v_j) \in \mathcal{R}^*_{i} \cap \mathcal{R}^*_{j}$ となるので
$r_{i+1} = e_{i+1} -_d (r_{j+2}, v_{j+2}) -_d (r_{j+3}, v_{j+3}) -_d \cdots -_d (r_{n-2}, v_{n-2}) -_d (r_{n-1}, v_{n-1}) \\ \in \mathcal{R}^*_{i+2} \cap \mathcal{R}^*_{i+3} \cap \cdots \cap \mathcal{R}^*_{n-1}$
となります。(2)より $r_{i+1} \in \mathcal{R}^*_1 \cap \mathcal{R}^*_2 \cap \cdots \cap \mathcal{R}^*_i$ となるので $r_{i+1} \in \mathcal{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_\exists R_0$

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