線形・補論(1)

いま、未知数が n 個であるような n 個の一次式を連立して得られる連立方程式

\{\begin{matrix} a_{11} x_{1} + a_{12} x_{2} +\dots+ a_{1 n} x_{n} = b_{1} \\ a_{21} x_{1} + a_{22} x_{2} +\dots+ a_{2 n} x_{n} = b_{2} \\ ⋮ \\ a_{n 1} x_{1} + a_{n 2} x_{2} +\dots+ a_{n n} x_{n} = b_{n} \end{matrix} 行列の記法で表わすと [\begin{matrix} a_{11} & a_{12} & \dots & a_{1 n} \\ a_{21} & a_{22} & \dots & a_{2 n} \\ ⋮ & ⋮ & ⋮ \\ a_{n 1} & a_{n 2} & \dots & a_{n n} \end{matrix}] [\begin{matrix} x_{1} \\ x_{2} \\ ⋮ \\ x_{n} \end{matrix}] = [\begin{matrix} b_{1} \\ b_{2} \\ ⋮ \\ b_{n} \end{matrix}] A := [\begin{matrix} a_{11} & a_{12} & \dots & a_{1 n} \\ a_{21} & a_{22} & \dots & a_{2 n} \\ ⋮ & ⋮ & ⋮ \\ a_{n 1} & a_{n 2} & \dots & a_{n n} \end{matrix}], x := [\begin{matrix} x_{1} \\ x_{2} \\ ⋮ \\ x_{n} \end{matrix}], b := [\begin{matrix} b_{1} \\ b_{2} \\ ⋮ \\ b_{n} \end{matrix}] とすると、 与えられた方程式は A x = b \dots (1) と表される。

　ここで、

\det A \neq 0

とすると、逆行列

A^{-1}

が存在するから、(1)式の両辺に左から

A^{-1}

を掛けると

A^{-1} A x = x = A^{-1} b \dots (2)

ところで、行列

A の逆行列 A^{-1}

は、「行列式(3)行列式の余因子」でみたように余因子行列を用いて、

【逆行列の公式 (n 行 n 列の場合) 】 (\det A \neq 0) A^{-1} = \frac{1}{\det A} [\begin{matrix} {\tilde{A}}_{11} & {\tilde{A}}_{21} & \dots & {\tilde{A}}_{n 1} \\ {\tilde{A}}_{12} & {\tilde{A}}_{22} & \dots & {\tilde{A}}_{n 2} \\ ⋮ & ⋮ & ⋮ \\ {\tilde{A}}_{1 n} & {\tilde{A}}_{2 n} & \dots & {\tilde{A}}_{n n} \end{matrix}] \dots (3)

というように、具体的な形で与えられる。一般に、逆行列に対する (3) 式の公式を Cramer の公式と呼ぶ。

すると(2)式は

[\begin{matrix} x_{1} \\ x_{2} \\ ⋮ \\ x_{n} \end{matrix}] = \frac{1}{\det A} \cdot [\begin{matrix} {\tilde{A}}_{11} & {\tilde{A}}_{21} & \dots & {\tilde{A}}_{n 1} \\ {\tilde{A}}_{12} & {\tilde{A}}_{22} & \dots & {\tilde{A}}_{n 2} \\ ⋮ & ⋮ & ⋮ \\ {\tilde{A}}_{1 n} & {\tilde{A}}_{2 n} & \dots & {\tilde{A}}_{n n} \end{matrix}] [\begin{matrix} b_{1} \\ b_{2} \\ ⋮ \\ b_{n} \end{matrix}]

したがって、解

x の第 j 成分 x_{j}

は

x_{j} = \frac{1}{\det A} \cdot ({\tilde{A}}_{1 j} b_{1} + {\tilde{A}}_{2 j} b_{2} +\dots+ {\tilde{A}}_{n j} b_{n})

によって与えられるが、この式の（）の中は、行列

A の第 j

列の余因子展開

\det A = ({\tilde{A}}_{1 j} a_{1 j} + {\tilde{A}}_{2 j} a_{2 j} +\dots+ {\tilde{A}}_{n j} a_{n j})

に現われる

a_{i j} を、各 i = 1,2,3,\dots, n について b_{i}

に置き換えたものに他ならない。そこで

A_{j} := [\begin{matrix} a_{1,1} & \dots & a_{1, j-1} & b_{1} & a_{1, j+1} & \dots & a_{1, n} \\ a_{2,1} & \dots & a_{2, j-1} & b_{2} & a_{2, j+1} & \dots & a_{2, n} \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ \\ a_{n,1} & \dots & a_{n, j-1} & b_{n} & a_{n, j+1} & \dots & a_{n, n} \end{matrix}] (j = 1,2,3,\dots, n)

とすると、一意的な解

x の各成分 x_{j}

は

x_{j} = \frac{\det A_{j}}{\det A}

で与えられる。この解の公式を Cramerの公式と呼ぶこともある。

ところで、Cramerの公式は、A の逆行列

A^{-1}

を A の余因子行列を用いて具体的に与えてくれるが、行列のサイズが小さくない場合には, 実際に逆行列を求める上ではあまり実用的ではない。その理由は, あまりにたくさん行列式を計算しなければならないという点にある。
それでは、どれぐらいの計算量になるだろうか？取りあえず乗除法のみを問題にしてその数を計算してみよう。

教科書的定義に従うと

\det A = \sum_{σ \in Sn} Sgn (σ) a_{1 σ (1)} a_{2 σ (2)} \dots a_{n σ (n)} より、 \det A は n! 個の項があり、 それぞれの項が、 n -1 回の掛け算を行うことになる。 乗除の回数 \begin{matrix} \det A に関して & n! (n -1) 回 \\ 各余因子に関して & (n -1)! (n -2) 回 \\ 全余因子に関して & n^{2} (n -1)! (n -2) 回 \\ 最後の割り算 & n^{2} 回 \end{matrix} したがって、全乗除の回数は、 n! (n -1) + n^{2} (n -1)! (n -2) + n^{2} = n! (n -1) + n \cdot n! (n -2) + n^{2} = n! (n^{2} - n -1) + n^{2} n = 3 \dots 39 n = 4 \dots 280 n が増えると、飛躍的に増大する。

一方、基本変形を用いて逆行列を計算するガウスの消去法（掃き出し法）を復習を兼ねて計算してみよう。
【ガウスの消去法】
行列に対して掃き出し法を行う為には、行に関する基本変形を行列に可能な限り繰り返し行って行列の左下部分の成分を全て 0 にする

『例題』
先ず、拡大係数行列を作る。

[\begin{matrix} 2 & 1 & 3 & 4 \\ 3 & -4 & 5 & -2 \\ 1 & 2 & 1 & 3 \\ -4 & 3 & 3 & 4 \end{matrix} |\begin{matrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{matrix}] [前進消去] 基本とする行を第1行にもってくる (r1 \leftrightarrow r3 第1行と第3行を交換) [\begin{matrix} 1 & 2 & 1 & 3 \\ 3 & -4 & 5 & -2 \\ 2 & 1 & 3 & 4 \\ -4 & 3 & 3 & 4 \end{matrix} |\begin{matrix} 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 \end{matrix}] 「第一段階」 [\begin{matrix} 1 & 2 & 1 & 3 \\ 0 & -10 & 2 & -11 \\ 0 & -3 & 1 & -2 \\ 0 & 11 & 7 & 16 \end{matrix} |\begin{matrix} 0 & 0 & 1 & 0 \\ 0 & 1 & -3 & 0 \\ 1 & 0 & -2 & 0 \\ 0 & 0 & 4 & 1 \end{matrix}] \begin{matrix} r2 + r1 \cdot (-3) \\ r3 + r1 \cdot (-2) \\ r4 + r1 \cdot (4) \end{matrix} 「第二段階」 [\begin{matrix} 1 & 2 & 1 & 3 \\ 0 & -10 & 2 & -11 \\ 0 & 0 & \frac{4}{10} & \frac{13}{10} \\ 0 & 0 & \frac{92}{10} & \frac{39}{10} \end{matrix} |\begin{matrix} 0 & 0 & 1 & 0 \\ 0 & 1 & -3 & 0 \\ 1 & - \frac{3}{10} & - \frac{11}{10} & 0 \\ 0 & \frac{11}{10} & \frac{7}{10} & 1 \end{matrix}] \begin{matrix} r3 + r2 \cdot (-3/10) \\ r4 + r2 \cdot (11/10) \end{matrix} 「第三段階」 [\begin{matrix} 1 & 2 & 1 & 3 \\ 0 & -10 & 2 & -11 \\ 0 & 0 & \frac{4}{10} & \frac{13}{10} \\ 0 & 0 & 0 & -26 \end{matrix} |\begin{matrix} 0 & 0 & 1 & 0 \\ 0 & 1 & -3 & 0 \\ 1 & - \frac{3}{10} & - \frac{11}{10} & 0 \\ -23 & 8 & 26 & 1 \end{matrix}] \begin{matrix} r4 + r3 \cdot (-23) \end{matrix} [後退代入] 「第四段階」 [\begin{matrix} 1 & 2 & 1 & 3 \\ 0 & -10 & 2 & -11 \\ 0 & 0 & \frac{4}{10} & \frac{13}{10} \\ 0 & 0 & 0 & 1 \end{matrix} |\begin{matrix} 0 & 0 & 1 & 0 \\ 0 & 1 & -3 & 0 \\ 1 & - \frac{3}{10} & - \frac{11}{10} & 0 \\ \frac{23}{26} & - \frac{8}{26} & - \frac{26}{26} & - \frac{1}{26} \end{matrix}] \begin{matrix} r4 \cdot (-1/26) \end{matrix} 「第五段階」 [\begin{matrix} 1 & 2 & 1 & 3 \\ 0 & -10 & 2 & -11 \\ 0 & 0 & \frac{4}{10} & 0 \\ 0 & 0 & 0 & 1 \end{matrix} |\begin{matrix} 0 & 0 & 1 & 0 \\ 0 & 1 & -3 & 0 \\ - \frac{3}{20} & \frac{1}{10} & \frac{2}{10} & \frac{1}{20} \\ \frac{23}{26} & - \frac{8}{26} & -1 & - \frac{1}{26} \end{matrix}] \begin{matrix} r3 + r4 \cdot (-13/10) \end{matrix} 「第六段階」 [\begin{matrix} 1 & 2 & 1 & 3 \\ 0 & -10 & 2 & -11 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{matrix} |\begin{matrix} 0 & 0 & 1 & 0 \\ 0 & 1 & -3 & 0 \\ - \frac{3}{8} & \frac{1}{4} & \frac{2}{4} & \frac{1}{8} \\ \frac{23}{26} & - \frac{8}{26} & -1 & - \frac{1}{26} \end{matrix}] \begin{matrix} r3 \cdot (10/4) \end{matrix} 以下同様に [\begin{matrix} 1 & 2 & 1 & 3 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{matrix} |\begin{matrix} 0 & 0 & 1 & 0 \\ - \frac{109}{104} & \frac{15}{52} & \frac{3}{2} & \frac{7}{104} \\ - \frac{3}{8} & \frac{1}{4} & \frac{2}{4} & \frac{1}{8} \\ \frac{23}{26} & - \frac{8}{26} & -1 & - \frac{1}{26} \end{matrix}] \begin{matrix} r2 + r4 \cdot (11) \\ r2 + r3 \cdot (-2) \\ さらに-10 で割る \end{matrix} 以下同様に [\begin{matrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{matrix} |\begin{matrix} - \frac{19}{104} & \frac{5}{52} & \frac{1}{2} & - \frac{15}{104} \\ - \frac{109}{104} & \frac{15}{52} & \frac{3}{2} & \frac{7}{104} \\ - \frac{3}{8} & \frac{1}{4} & \frac{2}{4} & \frac{1}{8} \\ \frac{23}{26} & - \frac{8}{26} & -1 & - \frac{1}{26} \end{matrix}] \begin{matrix} r1 + r4 \cdot (-3) \\ r1 + r3 \cdot (-1) \\ r1 + r2 \cdot (-2) \end{matrix}

やっと、たどり着きました。
　さて、どれだけの計算量になるでしょうか？

[前進消去]の第一段階では、未知数 n に対して拡大係数行列で、2n 個の係数に掛け算をする。そして、基本とする行以外のすべての行に行なうから、
第一段階全部で 2n(n-1)
第二段階では、行と未知数がそれぞれ一つ減るから
　　第二段階　　(2n-1)(n-2)
第三段階では、同様に　(2n-2)(n-3)
よって、全部では、

2 n (n -1) + (2 n -1) (n -2) + (2 n -2) (n -3) +\dots+ (n +2) \cdot 1 (これは、次のように表わせるから) = \sum_{k = 1}^{n -1} {(n +1) + k} k = (n +1) \sum_{k = 1}^{n -1} k + \sum_{k = 1}^{n -1} k^{2} = (n +1) \frac{n (n -1)}{2} + \frac{1}{6} n (n -1) (2 n -1) = \frac{1}{6} n (5 n^{2} -3 n -2) また、後退代入では、n 組の n 元連立一次方程式を解くことになるから、 n (1 +2 +3 +\dots+ n) = \frac{n^{2} (n +1)}{2} したがって、掃き出し法での乗除回数は、 \frac{1}{6} n (5 n^{2} -3 n -2) + \frac{n^{2} (n +1)}{2} = \frac{n (8 n^{2} -2)}{6}

これらの乗除回数を比較すると

Cramer n! (n^{2} - n -1) + n^{2} Gauss \frac{1}{3} n (4 n^{2} -1) \begin{matrix} n & Cramer & Gauss \\ 2 & 6 & 10 \\ 3 & 39 & 35 \\ 4 & 280 & 84 \\ 5 & 2305 & 165 \\ 6 & 20916 & 286 \\ ⋮ & ⋮ & ⋮ \end{matrix}

この比較から分かるように、Cramer の公式は、実際に逆行列を求める上ではあまり実用的ではないということが分かる。具体的な数値が与えられているときの逆行列の計算には、基本変形を用いて逆行列を計算する方がずっと効率がよい。しかし、Cramer の公式は、逆行列を成分で形式的に表現できる、ということが重要であって、それによって、逆行列に対する理解をより深めることができることは、「行列式（3）余因子」でみた。

線形代数・補論(1)

≪行列の基本変形とはなにか、行列語を理解する≫