線型代数の声を聴く

線型代数の概念が、なぜそう定義されるのか — その声に耳を澄ます。

逆行列を求める — 拡大行列の右半分に現れるもの

連立方程式 行列の代数

この記事でわかるようになること

  • 逆行列を計算する アルゴリズム $[A \mid I_n] \to [I_n \mid A^{-1}]$ を、自分の手で動かせる
  • このアルゴリズムが、前回 2.4.1 (3) ⇒ (5) の 証明そのものを実装したものだ と言える
  • アルゴリズムが「正則性の判定」と「逆行列の計算」を同時にやってくれる理由を説明できる
  • 第 2 章で積み上げた装置 — 行基本変形・簡約化・階数・解の運命・正則性 — が、すべてひとつの計算手続きの異なる側面だ、と俯瞰できる

前提知識

  • 2.4.1「正則行列と逆行列」(定理 2.4.2、特に (3) ⇒ (5) の構成)
  • 2.3.1「解の有無と一意性」(行基本変形が「列を混ぜない」観察)
  • 2.2.2「簡約化と階数」

現在地

  • 第2章「連立1次方程式」(全10章中)
    • 2.1 基本変形
    • 2.2 簡約な行列
    • 2.3 連立1次方程式を解く
    • 2.4 正則行列(全2記事)
      • 2.4.1 正則行列と逆行列
      • 2.4.2 逆行列を求める ← いまここ

問い

前回 2.4.1 で、正方行列 $A$ が 正則 であることと、$A$ に逆行列 $A^{-1}$ が存在することは同じことだ、と確かめた。

ただし、そこで残された宿題がある。「逆行列が存在する」と知ったあとで、実際にどう $A^{-1}$ を計算するのか?

本記事の答えは、目を見張るほど直接的だ。$n \times n$ の正則行列 $A$ に対して、$n \times 2n$ の拡大行列を作って簡約化するだけ。簡約化が完了すると、左半分は当然 $I_n$ になっているが、それと 同時に 右半分には逆行列 $A^{-1}$ がそのままの形で現れている。

$$ [A \mid I_n] \;\longrightarrow\; [I_n \mid A^{-1}] $$

なぜこんなことが可能なのか?どうやって手を動かすのか?— それを順に見ていく。

アルゴリズムの種は 2.4.1 で蒔かれていた

実は、前回 2.4.1 の (3) ⇒ (5) の証明で、私たちは既に逆行列の作り方を手に入れていた。思い出そう。仮定 (3) のもと、

$$ A\boldsymbol{c}_j = \boldsymbol{e}_j \quad (j = 1, 2, \ldots, n) $$

をそれぞれ解いて得た解たちを横に並べた

$$ C = [\,\boldsymbol{c}_1 \; \boldsymbol{c}_2 \; \cdots \; \boldsymbol{c}_n\,] $$

は、$AC = I_n$ を満たし、定理 2.4.1 によって $C = A^{-1}$ となる — というのが (3) ⇒ (5) の中身だった。

つまり $A^{-1}$ は、各単位ベクトルを右辺にとった $n$ 本の連立方程式の解を、列ベクトルとして横に並べたもの。それだけ。

問題は、計算の手間。素朴には $n$ 本の連立方程式を別々に解くことになる。一本ごとに拡大係数行列を作って簡約化していたら、左側の $A$ への行操作が $n$ 回繰り返されてしまう — 同じ計算を何度もやらされる。

同時並列で進める — 一回の簡約化で $n$ 本まとめて

ここで効くのが、行基本変形が 「列を混ぜない」 という事実(2.3.1 で見た)。各 $j$ について、

$$ [A \mid \boldsymbol{e}_j] \;\longrightarrow\; \cdots \;\longrightarrow\; [I_n \mid \boldsymbol{c}_j] $$

の簡約化を進めるとき、左側の $A$ に施される行操作は $j$ に依存しない。つまり、$n$ 本の簡約化はすべて同じ行操作で実行できる。

同じ操作を $n$ 回繰り返すのは無駄。最初から $n$ 本の右辺をすべて並べてしまえばよい。

$$ [A \mid \boldsymbol{e}_1 \; \boldsymbol{e}_2 \; \cdots \; \boldsymbol{e}_n] = [A \mid I_n] $$

(単位ベクトルを横に束ねたものは、定義どおり単位行列に他ならない。)

この $n \times 2n$ 行列を 一度 簡約化すると、左半分には $A$ の簡約化が現れ、右半分には同じ行操作を各単位ベクトルにそれぞれ施した結果が並ぶ。

$A$ が正則であれば、左半分は単位行列で、右半分は (3) ⇒ (5) で構成した解たちを横に並べたもの — すなわち $A^{-1}$ そのもの。

$$ [A \mid I_n] \;\longrightarrow\; [I_n \mid A^{-1}] $$

これが 逆行列計算アルゴリズムの全貌。一行に圧縮できるほど簡潔である。

観察:アルゴリズムの仕組みを一言で言い換えると、「$A$ を単位行列に変える行基本変形を見つけて、その同じ操作を単位行列のほうに施す」。$A$ から単位行列への動きの 裏側 で、単位行列から $A^{-1}$ への動きが、何の追加計算もなく勝手に進行している — これが掃き出し型アルゴリズムの精神である。

例題:3 次正則行列の逆行列

具体例で動かしてみよう。

$$ A = \begin{bmatrix} 1 & 1 & 0 \\\\ 1 & 2 & 1 \\\\ 0 & 1 & 2 \end{bmatrix} $$

を考える。$3 \times 6$ の拡大行列を作る。

$$ [A \mid I_3] = \begin{bmatrix} 1 & 1 & 0 & \mid & 1 & 0 & 0 \\\\ 1 & 2 & 1 & \mid & 0 & 1 & 0 \\\\ 0 & 1 & 2 & \mid & 0 & 0 & 1 \end{bmatrix} $$

第 2 行に第 1 行の $-1$ 倍を加える(第 1 列を整える)。

$$ \;\longrightarrow\; \begin{bmatrix} 1 & 1 & 0 & \mid & 1 & 0 & 0 \\\\ 0 & 1 & 1 & \mid & -1 & 1 & 0 \\\\ 0 & 1 & 2 & \mid & 0 & 0 & 1 \end{bmatrix} $$

第 1 行に第 2 行の $-1$ 倍を加え、さらに第 3 行から第 2 行を引く(第 2 列を整える)。

$$ \;\longrightarrow\; \begin{bmatrix} 1 & 0 & -1 & \mid & 2 & -1 & 0 \\\\ 0 & 1 & 1 & \mid & -1 & 1 & 0 \\\\ 0 & 0 & 1 & \mid & 1 & -1 & 1 \end{bmatrix} $$

第 1 行に第 3 行を加え、第 2 行から第 3 行を引く(第 3 列を整える)。

$$ \;\longrightarrow\; \begin{bmatrix} 1 & 0 & 0 & \mid & 3 & -2 & 1 \\\\ 0 & 1 & 0 & \mid & -2 & 2 & -1 \\\\ 0 & 0 & 1 & \mid & 1 & -1 & 1 \end{bmatrix} $$

簡約化が完了。左半分が $I_3$ に整ったので $A$ は正則で、右半分が逆行列。

$$ A^{-1} = \begin{bmatrix} 3 & -2 & 1 \\\\ -2 & 2 & -1 \\\\ 1 & -1 & 1 \end{bmatrix} $$

念のため $A A^{-1}$ を計算してみると、各 $(i, j)$ 成分が確かに単位行列の対応する値($i = j$ で $1$、$i \neq j$ で $0$)になっていることが確かめられる(計算は読者に委ねる)。

注意 — 簡約化が単位行列に到達しなかったら

簡約化を進めて、左半分が単位行列にならない(零行が出現する)場合はどうか。

定理 2.4.2 により、$A$ の簡約化が単位行列でない ⟺ $\mathrm{rank}(A) < n$ ⟺ $A$ は正則ではない、だった。だから:

アルゴリズムを実行して左半分が単位行列に整わなければ、$A$ は正則ではない(逆行列は存在しない)。

裏返すと、アルゴリズム自体が正則性の判定も同時にやってくれる。「簡約化したら左半分が単位行列に整ったか」を見るだけで、$A$ が正則であるかを判定でき、正則であればその場で $A^{-1}$ も手に入る。判定と計算が一つの手続きで同時に終わる — これが掃き出し法の経済性である。

第 2 章を振り返る

ここで第 2 章は終わる。一段引いて、私たちが歩いてきた道を眺めてみよう。

第 1 章で、行列を「数の長方形」として手にとった。それは静的なオブジェクトに見えた。

第 2 章では、その行列に対する 行基本変形 という操作を導入し、そこから 簡約化 という終着点、そこから読める 階数 という量、それらの組み合わせで決まる 連立方程式の解の運命(三通りに分かれる)、特殊形である 同次方程式と過小決定系、そして特殊状況での 正則性と逆行列 へと、たった一つの装置を一筋に上ってきた。

驚くべきは、すべての道具が「行基本変形 → 簡約化」というたった一つの装置から派生していること。階数も、解の有無の判定も、自由度の本数も、正則性の判定も、逆行列の構成も — すべてが同じ計算手続きの異なる側面である。

これが、線型代数が「数の代数」を超えて 構造の代数 であることの、最初の証拠になる。「行列とは何か」という第 1 章の問いに、第 2 章は 「行列とは、こういう統一的な装置で読み解ける構造体である」 と答え返した、と言ってよい。

次回予告 — 第 3 章「行列式」、そして第 4 章「ベクトル空間」へ

しかし、肝心な「なぜ装置が機能するのか」が、まだ宙ぶらりんに残っている。

  • 簡約化の 一意性(2.2.2 の定理 2.2.1)はなぜ成り立つのか?(本格証明は持ち越したまま)
  • 階数は「行から見ても列から見ても同じ」のはずだが、なぜ?
  • 定理 2.4.1(片側 $\Rightarrow$ 両側)はなぜ正方行列に固有なのか?

これらの答えは、おもに 第 4 章「ベクトル空間」 で整える 線型独立 という代数的・幾何的な概念にある。線型独立の言葉が手に入ると、本章で受け入れてきたいくつもの主張に 本当の理由 が一斉につく — 簡約化の一意性、行から見た階数と列から見た階数の一致、定理 2.4.1 が正方行列に固有である理由、すべてが線型独立をめぐる風景の一部として決着する。

その手前に立つ 第 3 章「行列式」 では、正方行列にもう一つの数 — 行列式 $\det A$ — を持たせる。行列式は正則性のもう一つの判定法を与え(「$A$ が正則 ⟺ $\det A \neq 0$」)、また連立 1 次方程式の解を クラメルの公式 という閉じた式で書き表す道具にもなる。本章で歩いた「行基本変形 → 簡約化」というアルゴリズム的アプローチに対する、もう一つの顔 である。

第 2 章は、これらすべての風景を見るための 入口の章 だった、と言ってよいかもしれない。

未回収の問い

  • 正則性の判定には他にも 行列式(determinant)という古典的な道具がある。簡約化を経由せず、行列の成分から直接「正則かどうか」を計算できる量だが、これは本シリーズでは第 3 章「行列式」で正面から扱う(本記事の次回予告で予告したとおり)
  • 大きな行列の逆行列を計算するときの 計算量と数値安定性。理論上は本章のアルゴリズムで十分だが、実用では LU 分解などのより洗練された方法が用いられる(本シリーズの主目的は理論なので、応用は深入りしない)
  • 定理 2.4.1(片側 $\Rightarrow$ 両側)の本格証明 — 第 4 章「ベクトル空間」へ送ったまま。線型独立性の言葉を整えてから決着する

← 前の記事:2.4.1 正則行列と逆行列 — 五つの顔をもつひとつの性質
→ 次の記事:3.1.1 置換 — 並べ替えを「ひとつの動き」として捉え直す