エレファント・コンピューティング調査報告

極限に関する順序を論理プログラミングの手法を使って指定することを目指すブロクです。

中間報告(5)

このブログは、論理プログラミングに実行順序を指定する機能を追加してサーバーで動作するような無限に動作するプログラムを記述することを一つの目標としています。この方法についていろいろな案を考えていきたいと思います。

前回の中間報告以降更新したもの

エレファントな整数論

素因数分解の一意性の説明のところまで終わった状況です。今後はこの説明の中の数学的帰納法の部分について記法を考えていきます。できればプログラミング言語で使えるようにしたいと考えています。

ある定義を変数を使った不等式のような形で書いて、単一化のように不等式の両辺が一致する代入を考えることで、この代入で数学的帰納法を表すことができると考えられます。今後はこの方法について考えていきます。数学的帰納法についてもう少し考えてみる予定です。

エレファントな線形代数

連立一次方程式の解法や行列のランクなどは行列の行の順序に依存しないので、行列を使わなくても説明できる部分が多いのではないかということでやっていたのですが、行列を使わないと説明が難しい部分がけっこうあるということがわかってきました。

今後は行列を使わなくても良い部分について上記の不等式の方法で記述することを考えていきます。

前回の中間報告以降更新していないもの

エレファントな関数論

コーシーの積分定理の証明について調査中です。今後はこれが不等式の方法で記述できるかどうか調べていきたいと思います。リウヴィルの定理、解析接続についてもうまく記述できるかどうかを考えていきたいと思います。

エレファントなポアンカレ予想

「エレファントな線形代数」で行列のランクの説明を書こうとしていますが、これができれば、ホモロジーの計算の記述をしようと考えています。

論理プログラミング的リーマン予想

「エレファントな関数論」で解析接続の記述ができれば、それを使ってリーマン予想の記述をしようと考えています。

半環上のフラクタル代数

Prologの実行順序を説明しようとしています。

論理プログラミング

無限に続く入出力を、論理プログラミングを使って極限として記述する方法を考えています。

フラクタル代数言語 Fractal

論理プログラミング言語であるPrologのような言語に、実行順序を指定する機能を追加する方法を考えています。

斜めの線を使わない圏論

極限、随伴を不等式の方法で説明することはできないか調べてみる予定です。

関数プログラミング

関数プログラミングの実行順序について調べようとしています。

群論の計算

不等式の方法で説明できる部分がないか調べてみる予定です。

今後の予定

P≠NP予想、リー代数についても不等式の方法で説明できるものがあるのか少し調べてみましたが、今のところは何もできていません。そのほかのいろいろな事例についても考えてみる予定です。

エレファントな線形代数(5)

行列式

「現代数学のエレファント」の記事で行列式を使って説明を書いていましたが、計算が長くなりすぎるため中断していました。しかし行列式を使わないとうまく説明できないことがあるので、もう一度説明していきます。

線型写像

 V を体  K 上の  n 次元ベクトル空間、 W を体  K 上の  m 次元ベクトル空間とします。 f: V \to W

  • 任意の  u, v \in V に対して  f(u + v) = f(u) + f(v)
  • 任意の  v \in V、任意の  a \in K に対して  f(av) = af(v)

を満たすとき、 V から  W への線型写像と呼びます。 V から  W への線型写像の全体を  \mathbf{Lin}(V, W) と書くことにします。 \mathbf{Lin}(V, W) に和とスカラー倍を

  •  f, g \in \mathbf{Lin}(V, W) に対して  (f + g)(v) = f(v) + g(v) \ (v \in V)
  •  f \in \mathbf{Lin}(V, W) a \in K に対して  (af)(v) = f(av) \ (v \in V)

と定義すると  K 上の  mn 次元ベクトル空間となります。

外積

まず外積の説明を書いていきます。外積に関しては以前書いたものとほとんど同じです。

 V を体  K 上の  n 次元ベクトル空間、 \{e_1, e_2, \cdots , e_n\} を基底とします。
 E_k = \{e_{ { i_{1} } }\wedge e_{ {i_{2} }}\wedge \cdots \wedge e_{ { i_{k} } }\mid 1\leq i_{1} < i_{2} < \cdots  < i_{k}\leq n\}
を基底とする K 上のベクトル空間(に以下のような演算を定義したもの)を  k-次外冪と呼び  \bigwedge^k(V) と書きます(この定義はWikipediaによる)。 \bigwedge^k(V) の次元は二項係数  \binom{n}{k} となります。

これらのベクトル空間の直和(すべての  E_k を基底とする  2^n 次元ベクトル空間)
 \displaystyle \textstyle \bigwedge (V)=\bigwedge ^{0}(V)\oplus \bigwedge ^{1}(V)\oplus \bigwedge ^{2}(V)\oplus \cdots \oplus \bigwedge ^{n}(V)
(に以下のような演算を定義したもの)を外積代数と呼びます(この定義はWikipediaによる)。ここで  \bigwedge^0(V) = K \bigwedge^1(V) = V とします。

 \bigwedge (V) に演算
 \wedge \colon \bigwedge (V) \times \bigwedge (V) \to \bigwedge (V)
を定義します。

まず  V \times V に制限した演算を考えます。
 \wedge_1 \colon V \times V \to \bigwedge^2 (V)
 \displaystyle \left(\sum_{i=1}^{n} a_i e_i\right) \wedge_1 \left(\sum_{j=1}^{n} b_j e_j\right) =
\sum_{i=1}^{n} \sum_{j=i+1}^{n} (a_i b_j - a_j b_i) (e_i \wedge e_j)
と定義すると
 \displaystyle \left(\sum_{i=1}^{n} a_i e_i\right) \wedge_1 \left(\sum_{j=1}^{n} b_j e_j\right) =
\sum_{i=1}^{n} \sum_{j=1}^{n} a_i b_j (e_i \wedge e_j)
を満たします。

  • (多重線型性)
    • 任意の  u, v, w \in V に対して  (u + v) \wedge_1 w = (u \wedge_1 w) + (v \wedge_1 w)
    • 任意の  u, v, w \in V に対して  u \wedge_1 (v + w) = (u \wedge_1 w) + (v \wedge_1 w)
    • 任意の  u, v \in V、任意の  a \in K に対して  au \wedge_1 v = u \wedge_1 av = a(u \wedge_1 v)
  • 任意の  v \in V に対して  v \wedge_1 v = 0

が成り立ちます。

 \wedge_k \colon \bigwedge^k (V) \times V \to \bigwedge^{k+1} (V) k=1 のときは  \wedge_1 k \ge 2 のときは
 (e_{ { i_{1} } }\wedge e_{ {i_{2} }}\wedge \cdots \wedge e_{ { i_{k} } }) \wedge_k e_j
 = \begin{cases}
    - ( (e_{ { i_{1} } } \wedge e_{ {i_{2} }} \wedge \cdots \wedge e_{ { i_{k-1} } }) \wedge_{k-1} e_j) \wedge e_{ { i_{k} } } & (i_k > j のとき) \\
    0 & (i_k = j \ のとき) \\
    e_{ { i_{1} } } \wedge e_{ {i_{2} }} \wedge \cdots \wedge e_{ { i_{k} } } \wedge e_j & (i_k < j のとき) \\
\end{cases}
帰納的に定義することができます。

これを繰り返して  \wedge_{k,l} \colon \bigwedge^k (V) \times \bigwedge^l (V) \to \bigwedge^{k+l} (V) を定義することができます。

  • (結合性)
    • 任意の  x \in \bigwedge^k (V) y \in \bigwedge^l (V) z \in \bigwedge^m (V) に対して  (x \wedge_{k,l} y) \wedge_{k+l,m} z = x \wedge_{k,l+m} (y \wedge_{l,m} z)
  • (多重線型性)
    • 任意の  x, y \in \bigwedge^k (V) z \in \bigwedge^l (V) に対して  (x + y) \wedge_{k,l} z = (x \wedge_{k,l} z) + (y \wedge_{k,l} z)
    • 任意の  x \in \bigwedge^k (V) y, z \in \bigwedge^l (V) に対して  x \wedge_{k,l} (y + z) = (x \wedge_{k,l} y) + (x \wedge_{k,l} z)
    • 任意の  x \in \bigwedge^k (V) y \in \bigwedge^l (V)、任意の  a \in K に対して  ax \wedge_{k,l} y = x \wedge_{k,l} ay = a(x \wedge_{k,l} y)

が成り立ちます。

 \wedge_{*} \colon \bigwedge (V) \times \bigwedge (V) \to \bigwedge (V)
 \displaystyle \left(\sum_{i=1}^{n} x_i \right) \wedge_* \left(\sum_{j=1}^{n} y_j \right) =
\sum_{i=1}^{n} \sum_{j=1}^{n} (x_i \wedge_{i,j} y_j)
( x_i \in \bigwedge^i (V) y_j \in \bigwedge^j (V))と定義すると

  • (結合性)
    • 任意の  x, y, z \in \bigwedge (V) に対して  (x \wedge_{*} y) \wedge_{*} z = x \wedge_{*} (y \wedge_{*} z)
  • (多重線型性)
    • 任意の  x, y, z \in \bigwedge (V) に対して  (x + y) \wedge_{*} z = (x \wedge_{*} z) + (y \wedge_{*} z)
    • 任意の  x, y, z \in \bigwedge (V) に対して  x \wedge_{*} (y + z) = (x \wedge_{*} y) + (x \wedge_{*} z)
    • 任意の  x, y \in \bigwedge (V)、任意の  a \in K に対して  ax \wedge_{*} y = x \wedge_{*} ay = a(x \wedge_{*} y)

が成り立ちます。

 \wedge_* \wedge と書くと  \bigwedge (V) に演算
 \wedge \colon \bigwedge (V) \times \bigwedge (V) \to \bigwedge (V)
が定義できます。

  • (結合性)
    • 任意の  x, y, z \in \bigwedge (V) に対して  (x \wedge y) \wedge z = x \wedge (y \wedge z)
  • (多重線型性)
    • 任意の  x, y, z \in \bigwedge (V) に対して  (x + y) \wedge z = (x \wedge z) + (y \wedge z)
    • 任意の  x, y, z \in \bigwedge (V) に対して  x \wedge (y + z) = (x \wedge y) + (x \wedge z)
    • 任意の  x, y \in \bigwedge (V)、任意の  a \in K に対して  ax \wedge y = x \wedge ay = a(x \wedge y)
  • 任意の  v \in V に対して  v \wedge v=0

が成り立ちます。

この演算を外積と呼びます。外積によって  \bigwedge (V) は体  K 上の単位的結合代数となります。

行列式

 V を体  K 上の  n 次元ベクトル空間、 \{e_1, e_2, \cdots , e_n\} を基底、 \varphi: V \to V線型写像とします。
 \bigwedge^{n}(V) 1 次元で  e_{1} \wedge \cdots \wedge e_{n} が基底となります。

 \bigwedge^{n} \varphi : \bigwedge^{n} (V) \to \bigwedge^{n} (V) \left( \bigwedge^{n} \varphi \right) ( e_{1} \wedge \cdots \wedge e_{n} ) = \varphi (e_{1}) \wedge \cdots \wedge \varphi (e_{n}) とすると  \bigwedge^{n} \varphi 線型写像となります。

 \bigwedge^{n} : \mathbf{Lin}(V, V) \to \mathbf{Lin}(\bigwedge^{n} (V), \bigwedge^{n} (V)) \bigwedge^{n}(\varphi) = \bigwedge^{n} \varphi となる写像とすると、 \bigwedge^{n}線型写像となります。

よって  a \in K が存在して  \left( \bigwedge^{n} \varphi \right) ( e_{1} \wedge \cdots \wedge e_{n} ) = a( e_{1} \wedge \cdots \wedge e_{n} ) となります。この  a \varphi行列式と呼び  \det \varphi と書きます。

偶置換・奇置換

群論の計算(9)」で書いた内容ですが、ここにも書いておきます。この議論はもう少し簡単になるかもしれません。

置換  \sigma \in S_n に対して  \sigma で順序が逆になる  (i, j) の組の数、すなわち
 T_\sigma = \{ (i, j) | i = 1, 2, \cdots, n , j =  i+1, i+2, \cdots , n, \sigma(i) > \sigma(j) \}
の元の数  t_\sigma \sigma の転倒数と呼びます。

 j = i+1 として  \mu = (ij)  \tau = \sigma \mu とおきます。 \tau の転倒数、すなわち
 T_\tau = \{ (i, j) | i = 1, 2, \cdots, n , j =  i+1, i+2, \cdots , n, \tau(i) > \tau(j) \}
の元の数を  t_\tau とおきます。

  •  \tau(i) = \sigma ( \mu (i)) = \sigma(j)
  •  \tau(j) = \sigma ( \mu (j)) = \sigma(i)
  •  \tau(k) = \sigma(k) \ (k \ne i, k \ne j)

が成り立つので

  •  (i, j) \not \in T_\sigma のときは  T_\tau = T_\sigma \cup \{ (i, j) \}  t_\tau = t_\sigma + 1
  •  (i, j) \in T_\sigma のときは  T_\tau = T_\sigma \setminus \{ (i, j) \}  t_\tau = t_\sigma - 1

となります。

これをバブルソートの手順のように繰り返して、 n を保存する置換を作ります。 \sigma(i) = n のとき
 \xi = \sigma (i,i+1) (i+1,i+2) \cdots (n-1,n)
( (ij) をここでは  (i,j) と書いています)とおくと、 \xi(n) = n となります。よって  n-1 の場合に帰着させることができます。 n-1 以下にさらにバブルソートの手順のように行うと  e = \sigma \mu_1 \mu_2 \cdots \mu_m という形にすることができます。ここで  e は恒等写像 \mu_i は互換となります。 \sigma = \mu_m \mu_{m-1} \cdots \mu_1 となるので  \sigma は互換の積の形で表すことができます。

よって任意の置換は互換の積の形で表すことができます。

次に互換  \lambda = (ij) ( i \lt j)を考えます。 \lambda は上記の手順と同様に
 (i, i+1) (i+1, i+2) \cdots (j -1, j)
 i の位置を  j の位置に移動して
 (j-2, j-1) (j-3, j-2) \cdots (i, i+1)
 j-1 の位置を  i の位置に移動したと考えることができます。よって  \lambda は奇数個の隣接する互換の積として表すことができます。

よって  \sigma = \lambda_1 \lambda_2 \cdots \lambda_l ( \lambda_i は互換)とすると

  •  \sigma の転倒数が偶数ならば  l は偶数
  •  \sigma の転倒数が奇数ならば  l は奇数

となります。

よって置換を互換の積として表したとき、互換の個数が偶数なのか奇数なのかは置換によって決まっていることがわかります。偶数の互換の積として表される置換を偶置換、奇数の互換の積として表される置換を奇置換と呼びます。

行列式の成分による表示

 \varphi: V \to V線型写像とします。 n n 列の行列  A i j 列成分を  a_{ij}
 \displaystyle \varphi(e_i) = \sum_{j=1}^{n} a_{ij} e_j = a_{i1} e_1 + a_{i2} e_2 + \cdots + a_{in} e_n
を満たすものとします。

 J = \{1, 2, \cdots, n\} とおきます。 e_j \wedge e_j = 0 より  e_{j_1} \wedge \cdots \wedge e_{j_n} \ne 0 k \ne l ならば  j_k \ne j_l となります。よって  e_{j_1} \wedge \cdots \wedge e_{j_n} \ne 0 のとき  \sigma: J \to J \sigma(k) = j_k とすると  \sigma全単射となります。 J から  J への全単射全体の集合を  S_n とすると  \sigma \in S_n となります。よって
 \begin{eqnarray*}
 & & \{(j_1, \cdots, j_n) \in J^n \mid e_{j_1} \wedge \cdots \wedge e_{j_n} \ne 0\} \\
 & = & \{(j_1, \cdots, j_n) \in J^n \mid \sigma \in S_n \ が存在して \ (j_1, \cdots, j_n) = (\sigma(1), \cdots, \sigma(n)) \} \\
 & = & \{ (\sigma(1), \cdots, \sigma(n)) \mid \sigma \in S_n \} \\
\end{eqnarray*}
 \begin{eqnarray*}
 & & \left( {\bigwedge}^{n} \varphi \right) ( e_{1} \wedge \cdots \wedge e_{n} ) \\
 & = & \varphi (e_{1}) \wedge \cdots \wedge \varphi (e_{n}) \\
 & = & \left( \sum_{j=1}^{n} a_{1j} e_j \right) \wedge \cdots \wedge \left( \sum_{j=1}^{n} a_{nj} e_j \right) \\
 & = & \sum_{j_1=1}^{n}\cdots \sum_{j_n=1}^{n} a_{1j_1} \cdots a_{nj_n} (e_{j_1} \wedge \cdots \wedge e_{j_n}) \\
 & = & \sum_{(j_1, \cdots, j_n) \in J^n} a_{1j_1} \cdots a_{nj_n} (e_{j_1} \wedge \cdots \wedge e_{j_n}) \\
 & = & \sum_{\sigma \in S_n} a_{1\sigma(1)} \cdots a_{n\sigma(n)} (e_{\sigma(1)} \wedge \cdots \wedge e_{\sigma(n)}) \\
 & = & \sum_{\sigma \in S_n} (\operatorname {sgn} \sigma ) a_{1\sigma(1)} \cdots a_{n\sigma(n)} (e_1 \wedge \cdots \wedge e_n) \\
\end{eqnarray*}
となります。ここで  \operatorname {sgn} \sigma
 e_{\sigma(1)} \wedge \cdots \wedge e_{\sigma(n)} = (\operatorname {sgn} \sigma ) (e_1 \wedge \cdots \wedge e_n)
を満たすものとします。 \operatorname {sgn} \sigma = 1 または  \operatorname {sgn} \sigma = -1 となります。 \operatorname {sgn} \sigma = 1 のとき  \sigma を偶置換、 \operatorname {sgn} \sigma = -1 のとき  \sigma を奇置換となります。「偶置換・奇置換」の議論より
 \operatorname {sgn} \sigma \tau = (\operatorname {sgn} \sigma)(\operatorname {sgn} \tau)
が成り立ちます。

よって  \tau = \sigma^{-1} と考えると
 \displaystyle \sum_{\sigma \in S_n} (\operatorname {sgn} \sigma ) a_{1\sigma(1)} \cdots a_{n\sigma(n)} (e_1 \wedge \cdots \wedge e_n) =  \sum_{\tau \in S_n} (\operatorname {sgn} \tau ) a_{\tau(1)1} \cdots a_{\tau(n)n} (e_1 \wedge \cdots \wedge e_n)
が成り立ちます。(*1)

行列の基本変形

行列の基本変形について、Wikipediaに従って行列の形で書いていきます。

 E単位行列 I_{ij} (i,j) 成分が  1 でそれ以外の成分が  0 であるような行列とします。以下のような  (n, n) 行列を基本行列と呼びます。

 A (n, n) 行列とするとき

  •  A P(i, j) を左からかけると、 i 行と  j 行が交換される。
  •  A Q(i, c) を左からかけると、 i 行が  c 倍される。
  •  A T(i, j, c) を左からかけると、  i 行に  j 行の  c 倍が加わる。
  •  \det P(i, j) = 1
  •  \det Q(i, c) = c
  •  \det T(i, j, c) = 1

が成り立ちます。

行列の基本変形と掃き出し法

 K' = K(x_{11}, \cdots, x_{1n}, \cdots, x_{n1}, \cdots, x_{nn}) X = \begin{pmatrix}
x_{11} & x_{12} & \cdots & x_{1n} \\
x_{21} & x_{22} & \cdots & x_{2n} \\
\vdots & \vdots & \ddots & \vdots \\
x_{n1} & x_{n2} & \cdots & x_{nn} \\
\end{pmatrix} とします。

 Y = \begin{pmatrix}
y_{11} & y_{12} & \cdots & y_{1n} \\
y_{21} & y_{22} & \cdots & y_{2n} \\
\vdots & \vdots & \ddots & \vdots \\
y_{n1} & y_{n2} & \cdots & y_{nn} \\
\end{pmatrix} v_i = \begin{pmatrix} y_{i1} & y_{i2} & \cdots & y_{in} \end{pmatrix} のとき  Y = [ v_1, v_2, \cdots, v_n ] と書くことにします。

 [ v_1, v_2, \cdots, v_k ] + [ u_1, u_2, \cdots, u_l ] = [ v_1, v_2, \cdots, v_k, u_1, u_2, \cdots, u_l ] とします。

 v = \begin{pmatrix} y_{1} & y_{2} & \cdots & y_{n} \end{pmatrix} u = \begin{pmatrix} z_{1} & z_{2} & \cdots & z_{n} \end{pmatrix} のとき  v \stackrel{i}{\to} u = v - \cfrac{y_i}{z_i} u [ v_1, v_2, \cdots, v_k ] \stackrel{i}{\to} u = [ v_1 \stackrel{i}{\to} u, v_2 \stackrel{i}{\to} u, \cdots, v_k \stackrel{i}{\to} u ] とします。

 X に対して  X_i v_{ij} = \begin{pmatrix} x[i,j,1] & x[i,j,2] & \cdots & x[i,j,n] \end{pmatrix} を以下のように決めます。

  •  X_1 = [ v_{11}, v_{12}, \cdots, v_{1n} ] = X
  •  X_k = [ v_{k1}, v_{k2}, \cdots, v_{kn} ] = [ v_{k1}, \cdots, v_{ki} ] + [ v_{ik}, \cdots, v_{in} ] \stackrel{i}{\to} v_{ii}  (k=i+1)

 X_k = T \left(k, i, -\cfrac{x[i,k,i]}{x[i,i,i]} \right) \cdots T \left(n, i, -\cfrac{x[i,n,i]}{x[i,i,i]} \right) X_i となります。

よって  \det X = \det X_1 = \det X_2 = \cdots = \det X_n = x[1,1,1] x[2,2,2] \cdots x[n,n,n] となります。

 A = \begin{pmatrix}
a_{11} & a_{12} & \cdots & a_{1n} \\
a_{21} & a_{22} & \cdots & a_{2n} \\
\vdots & \vdots & \ddots & \vdots \\
a_{n1} & a_{n2} & \cdots & a_{nn} \\
\end{pmatrix} K の元を成分とする行列とします。 x \in K' X の各元に  A の各元をそれぞれ代入したものを  x \mid (X=A) と書くことにします。

 1 = \det X \mid (X=E) = x[1,1,1] x[2,2,2] \cdots x[n,n,n] \mid (X=E) となるので  \det X \ne 0 となります。 \det X \ne 0 である行列  X正則行列と呼びます。

 \sigma, \tau \in S_n とします。 X に対して
 X^{\sigma,\tau} = \begin{pmatrix}
x_{\sigma(1)\tau(1)} & x_{\sigma(1)\tau(2)} & \cdots & x_{\sigma(1)\tau(n)} \\
x_{\sigma(2)\tau(1)} & x_{\sigma(2)\tau(2)} & \cdots & x_{\sigma(2)\tau(n)} \\
\vdots & \vdots & \ddots & \vdots \\
x_{\sigma(n)\tau(1)} & x_{\sigma(n)\tau(2)} & \cdots & x_{\sigma(n)\tau(n)} \\
\end{pmatrix} とおきます。(*1)の結果より  \det X^{\sigma,\tau} =  (\operatorname{sgn} \sigma) (\operatorname{sgn} \tau) \det X となります。

 A K の元を成分とする行列、 \det A^{\sigma,\tau} \det X^{\sigma,\tau} と同様に  A の行を  \sigma、列を  \tau で置換した行列とします。 \det A \ne 0 ならば
 \det A^{\sigma,\tau} = \det X^{\sigma,\tau} \mid (X=A) = (\operatorname{sgn} \sigma) (\operatorname{sgn} \tau) \det X \mid (X=A) = (\operatorname{sgn} \sigma) (\operatorname{sgn} \tau) \det A \ne 0
となります。

エレファントな線形代数(4)

順序に依存する掃き出し法

ここで再び順序に依存する場合を考えます。

 E = [ e_{1}, e_{2}, \cdots, e_{n} ] とし、以下のように  R = [ r_{1}, r_{2}, \cdots, r_{n} ] を決めます(順序に依存する列をこのように書くことにします)。
 \left\{ \begin{matrix}
E_1 = E & = & [ e_{11}, e_{12}, \cdots, e_{1n} ] \\
E_2 & = & [ e_{22}, e_{23}, \cdots, e_{2n} ] \\
 & \vdots \\
E_n & = & [ e_{nn} ] \\
\end{matrix} \right.
とします。

 d(e, r, v_i) e \stackrel{i}{-} r をと書くことにします。

  •  e, r \notin \mathcal{R}^*_i ならば  e \stackrel{i}{-} r が存在する
  •  e \stackrel{i}{-} r \in \mathcal{R}^*_i \cup \mathcal{O} ( \mathcal{O} e \stackrel{i}{-} r が存在しないことを表す)
  •  e, r \in \mathcal{R}^*_j ならば  e \stackrel{i}{-} r \in \mathcal{R}^*_j

とします。

 \left\{ \begin{matrix}
e_{22} & = & e_{12} \stackrel{1}{-} e_{11} & \in & \mathcal{R}^*_1 \cup \mathcal{O} \\ 
e_{23} & = & e_{13} \stackrel{1}{-} e_{11} & \in & \mathcal{R}^*_1 \cup \mathcal{O} \\ 
 & \vdots \\
e_{2n} & = & e_{1n} \stackrel{1}{-} e_{11} & \in & \mathcal{R}^*_1 \cup \mathcal{O} \\ 
\end{matrix} \right.

 \left\{ \begin{matrix}
e_{33} & = & e_{23} \stackrel{2}{-} e_{22} & \in & \mathcal{R}^*_1 \cap \mathcal{R}^*_2 \cup \mathcal{O} \\ 
e_{34} & = & e_{24} \stackrel{2}{-} e_{22} & \in & \mathcal{R}^*_1 \cap \mathcal{R}^*_2 \cup \mathcal{O} \\ 
 & \vdots \\
e_{3n} & = & e_{2n} \stackrel{2}{-} e_{22} & \in & \mathcal{R}^*_1 \cap \mathcal{R}^*_2 \cup \mathcal{O} \\ 
\end{matrix} \right.

 \begin{matrix}
 & \vdots & \\
e_{nn} & = & e_{n-1,n} \stackrel{n-1}{-} e_{n-1,n-1} & \in & \mathcal{R}^*_1 \cap \mathcal{R}^*_2 \cap \cdots \cap \mathcal{R}^*_{n-1} \cup \mathcal{O}
\end{matrix}

 \begin{array} {ccl}
r_n & = & e_{nn}  & \in & \mathcal{R}_n \cup \mathcal{O} = \mathcal{R}^*_1 \cap \mathcal{R}^*_2 \cap \cdots \cap \mathcal{R}^*_{n-1} \\
r_{n-1} & = & e_{n-1,n-1} \stackrel{n}{-} r_n & \in & \mathcal{R}_{n-1} \cup \mathcal{O} \cup \mathcal{O} \\
r_{n-2} & = & e_{n-2,n-2} \stackrel{n-1}{-} r_{n-1} \stackrel{n}{-} r_n & \in & \mathcal{R}_{n-2} \cup \mathcal{O} \\
 & \vdots & \\
r_{1} & = & e_{11} \stackrel{2}{-} r_{2} \stackrel{3}{-} r_{3} \stackrel{4}{-} \cdots \stackrel{n}{-} r_n & \in & \mathcal{R}_{1} \cup \mathcal{O}
\end{array}

掃き出し法の順序の置換

上記の数式を以下のように書くことにします。

 \begin{cases}
[ e_{i+1,i+1}, e_{i+1,i+2}, \cdots, e_{i+1,n} ] = [ e_{i,i+1}, e_{i,i+2}, \cdots, e_{i,n} ] \stackrel{i}{-} e_{ii} \\
r_{i} = e_{ii} \stackrel{i+1}{-} r_{i+1} \stackrel{i+2}{-} r_{i+2} \stackrel{i+3}{-} \cdots \stackrel{n}{-} r_n
\end{cases}

ここで  \sigma \tau \{1, 2, \cdots, n\} の置換( \sigma は行の置換、 \tau は列の置換を表す)とします。

 E^\sigma = [ e^\sigma_{1}, e^\sigma_{2}, \cdots, e^\sigma_{n} ] とし、 R^{\sigma\tau} = [ r^{\sigma\tau}_{1}, r^{\sigma\tau}_{2}, \cdots, r^{\sigma\tau}_{n} ] E^{\sigma\tau}_i = [ e^{\sigma\tau}_{i1}, e^{\sigma\tau}_{i2}, \cdots, e^{\sigma\tau}_{in} ] を以下のように決めます。
 \begin{cases}
E^{\sigma\tau}_1 = E^{\sigma} \\ 
[ e^{\sigma\tau}_{\sigma(i+1)\tau(i+1)}, e^{\sigma\tau}_{\sigma(i+1)\tau(i+2)}, \cdots, e^{\sigma\tau}_{\sigma(i+1)\tau(n)} ] \\
= [ e^{\sigma\tau}_{\sigma(i)\tau(i+1)}, e^{\sigma\tau}_{\sigma(i)\tau(i+2)}, \cdots, e^{\sigma\tau}_{\sigma(i)\tau(n)} ] \stackrel{\tau(i)}{-} e^{\sigma\tau}_{\sigma(i)\tau(i)} \\
r^{\sigma\tau}_{\sigma\tau(i)} = e^{\sigma\tau}_{\sigma(i)\tau(i)} \stackrel{\tau(i+1)}{-} r^{\sigma\tau}_{\sigma\tau(i+1)} \stackrel{\tau(i+2)}{-} r^{\sigma\tau}_{\sigma\tau(i+2)} \stackrel{\tau(i+3)}{-} \cdots \stackrel{\tau(n)}{-} r^{\sigma\tau}_{\sigma\tau(n)}
\end{cases}

 \sigma, \tau に対して  e^{\sigma\tau}_{\sigma(t)\tau(t)} が存在する最大の  t \mathrm{rank}^{\sigma\tau}(E) とします。すべての  \sigma, \tau に関して最大の  \mathrm{rank}^{\sigma\tau}(E) \mathrm{rank}(E) とします。

 \mathrm{rank}^{\sigma\tau}(E) = n のとき  [E^{\exists\sigma} \to\to R^{\exists\tau}] と書くことにします。この計算から以下のことが導けるかどうか調べます。以下では  [E^{\exists\sigma} \to\to R^{\exists\tau}] の中の  E R は順序があるリストを表し、それ以外は順序のない通常の集合を表すとします。

  •  [E^{\exists\sigma} \to\to R^{\exists\tau}] \iff E \twoheadrightarrow R
  •  \mathrm{rank}(E) = n \iff E \twoheadrightarrow_\exists R
  •  E \twoheadrightarrow R_1, E \twoheadrightarrow R_2 \implies R_1 = R_2

エレファントな線形代数(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} とおけば成り立ちます。[証明終わり]

エレファントな線形代数(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} とおけば成り立ちます。[証明終わり]

エレファントな線形代数(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 の解となることを表します。

エレファントな整数論(19)

最後の式の書き方を少し変更します。

(8)  \mathcal{P}, \mathcal{Q} を0個以上の有限個の正の素数からなる多重集合とするとき、 \prod \mathcal{P} = \prod \mathcal{Q} ならば  \mathcal{P} = \mathcal{Q} となります。

[証明]  \{| p |\} \le \mathcal{P} となる  p が存在しないとすると  \prod \mathcal{P} = 1 となります。 \prod \mathcal{P} = \prod \mathcal{Q} ならば  \prod \mathcal{Q} = 1 となって  \# \mathcal{Q} = 0 となるので  \mathcal{P} = \mathcal{Q} となります。

 \{| p |\} \le \mathcal{P} となる  p が存在するならば、(7) より  \{| p |\} \le \mathcal{Q} となります。 \mathcal{P}' = \mathcal{P} - \{| p |\} \mathcal{Q}' = \mathcal{Q} - \{| p |\} とおくと  \prod \mathcal{P} = \prod \mathcal{Q} より  \prod \mathcal{P}' = \prod \mathcal{Q}' となります。このとき  \mathcal{P}' = \mathcal{Q}' と仮定すると、 \mathcal{P} = \mathcal{P}' + \{| p |\} = \mathcal{Q}' + \{| p |\} = \mathcal{Q} となります。

よって  \mathcal{P} = \{| p_1, p_2, \cdots , p_m |\} とすると
 \begin{eqnarray*}
 &  & \left[ \ \prod \mathcal{P} = \prod \mathcal{Q} \implies \mathcal{P} = \mathcal{Q} \ \right] \\
 & \Longleftarrow & \mathcal{P} \ne_\exists \mathcal{P}_1 + \{| p_1 |\} \lor \left[ \ \mathcal{P} =_\exists \mathcal{P}_1 + \{| p_1 |\} \land \prod \mathcal{P}_1 = \prod \mathcal{Q}_1 \implies \mathcal{P} = \mathcal{Q} \ \right] \\
 & \Longleftarrow & \mathcal{P} \ne_\exists \mathcal{P}_1 + \{| p_1 |\} \lor \ \\
 & & \mathcal{P}_1 \ne_\exists \mathcal{P}_2 + \{| p_2 |\} \lor \left[ \ \mathcal{P}_1 =_\exists \mathcal{P}_2 + \{| p_2 |\} \land \prod \mathcal{P}_2 = \prod \mathcal{Q}_2 \implies \mathcal{P}_1 = \mathcal{Q}_1 \ \right] \\
 & \Longleftarrow & \mathcal{P} \ne_\exists \mathcal{P}_1 + \{| p_1 |\} \lor \mathcal{P}_1 \ne_\exists \mathcal{P}_2 + \{| p_2 |\} \lor \ \\
 & & \mathcal{P}_2 \ne_\exists \mathcal{P}_3 + \{| p_3 |\} \lor \left[ \ \mathcal{P}_2 =_\exists \mathcal{P}_3 + \{| p_3 |\} \land \prod \mathcal{P}_3 = \prod \mathcal{Q}_3 \implies \mathcal{P}_2 = \mathcal{Q}_2 \ \right] \\
 & \Longleftarrow & \\
 & \vdots & \\
 & \Longleftarrow & \mathcal{P} \ne_\exists \mathcal{P}_1 + \{| p_1 |\} \lor \cdots \lor \mathcal{P}_m \ne_\exists \mathcal{P}_{m+1} + \{| p_{m+1} |\} 
\end{eqnarray*}
となります。ここで  \mathcal{X} \ne_\exists \mathcal{Y} + \{| x |\} \mathcal{X} = \mathcal{Y} + \{| x |\} となる  \mathcal{Y} x が存在しないこと、 \mathcal{X} =_\exists \mathcal{Y} + \{| x |\} \mathcal{X} = \mathcal{Y} + \{| x |\} となる  \mathcal{Y} x が存在することを表すとします。最後の項は  \{| p |\} \le \mathcal{P}_m となる  p が存在しない場合( \# \mathcal{P}_m = 0 の場合)なので成り立ちます。よって  \prod \mathcal{P} = \prod \mathcal{Q} ならば  \mathcal{P} = \mathcal{Q} となります。[証明終わり]