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

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

エレファントな線形代数(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
となります。