【お知らせ】プログラミング記事の投稿はQiitaに移行しました。

掃き出し法と逆行列

掃き出し法によって逆行列を求める過程を、連立方程式と対比して説明します。

シリーズの記事です。

  1. 一次変数変換と行列の積
  2. 単位行列と逆行列
  3. 掃き出し法と逆行列 ← この記事
  4. 行列の積の性質
  5. 行列の演算
  6. ケイリー・ハミルトンの定理
  7. 零行列と冪零行列
  8. 冪零行列と二重数
  9. 零因子ペアの生成
  10. 三種類の二元数
  11. 分解型四元数と同型対応
  12. 分解型四元数と幾何代数
  13. 行列表現と外積と行列式

目次

掃き出し法

方程式を連立させたまま3つの手順で式を変形して解く方法を掃き出し法(またはガウスの消去法)と呼びます。

  1. 式の両辺を定数倍
  2. 他の式を足す
  3. 式の順番の入れ替え(今回は未使用)

通常は行列の形だけで計算しますが、何をやっているのか説明するため連立方程式を併記します。

次の式 $(1)$ を $x',y'$ について解きます。解く対象が左辺に来るように配置します。行列表記では $=$ の部分を縦線で区切ります。右半分が単位行列になっていることに注目してください。この形がスタートです。

\tag{1} \left\{\begin{aligned} ax'+by'&=x \\ cx'+dy'&=y \end{aligned}\right. \qquad \left(\begin{array}{cc|cc} a&b&1&0 \\ c&d&0&1 \end{array}\right)

足すと $y'$ が消えるように、定数を掛けて係数を調整します。

\left\{\begin{aligned} adx'+bdy'&=dx \\ -bcx'-bdy'&=-by \\ \end{aligned}\right. \qquad \left(\begin{array}{cc|cc} ad&bd&d&0 \\ -bc&-bd&0&-b \end{array}\right)

1番目の式に2番目の式を足すと $y'$ が消えます。

\left\{\begin{aligned} (ad-bc)x'&=dx-by \\ -bcx'-bdy'&=-by \\ \end{aligned}\right. \qquad \left(\begin{array}{cc|cc} ad-bc&0&d&-b \\ -bc&-bd&0&-b \end{array}\right)

1番目の式に $1/(ad-bc)$ を掛けると、$x'$ の解が得られます。

\left\{\begin{aligned} x'&=\frac{dx-by}{ad-bc} \\ -bcx'-bdy'&=-by \\ \end{aligned}\right. \qquad \left(\begin{array}{cc|cc} 1&0&\frac{d}{ad-bc}&-\frac{b}{ad-bc} \\ -bc&-bd&0&-b \end{array}\right)

足すと $x'$ が消えるように、2番目の式に $1/bc$ を掛けます。

\left\{\begin{aligned} x'&=\frac{dx-by}{ad-bc} \\ -x'-\frac{d}{c}y'&=-\frac 1 c y \\ \end{aligned}\right. \qquad \left(\begin{array}{cc|cc} 1&0&\frac{d}{ad-bc}&-\frac{b}{ad-bc} \\ -1&-\frac d c&0&-\frac 1 c \end{array}\right)

2番目の式に1番目の式を足すと $x'$ が消えます。

\left\{\begin{aligned} x'&=\frac{dx-by}{ad-bc} \\ -\frac{d}{c}y'&=\frac{cdx-ady}{c(ad-bc)} \\ \end{aligned}\right. \qquad \left(\begin{array}{cc|cc} 1&0&\frac{d}{ad-bc}&-\frac{b}{ad-bc} \\ 0&-\frac d c&\frac{cd}{c(ad-bc)}&-\frac{ad}{c(ad-bc)} \end{array}\right)

2番目の式に $-c/d$ を掛けると、$y'$ の解が得られます。

\left\{\begin{aligned} x'&=\frac{dx-by}{ad-bc} \\ y'&=\frac{-cx+ay}{ad-bc} \end{aligned}\right. \qquad \left(\begin{array}{cc|cc} 1&0&\frac{d}{ad-bc}&-\frac{b}{ad-bc} \\ 0&1&-\frac{c}{ad-bc}&\frac{a}{ad-bc} \end{array}\right)

行列表記の左半分が単位行列になっていることに注目してください。この形がゴールです。

簡単な例

具体的な例で計算してみます。

\begin{aligned} &\left\{\begin{aligned} 2x'+7y'&=x \\ x'+3y'&=y \end{aligned}\right. &&\left(\begin{array}{cc|cc} 2&7&1&0 \\ 1&3&0&1 \end{array}\right) \\ &\left\{\begin{aligned} 6x'+21y'&=3x \\ -7x'-21y'&=-7y \end{aligned}\right. &&\left(\begin{array}{cc|cc} 6&21&3&0 \\ -7&-21&0&-7 \end{array}\right) \\ &\left\{\begin{aligned} -x'&=3x-7y \\ -7x'-21y'&=-7y \end{aligned}\right. &&\left(\begin{array}{cc|cc} -1&0&3&-7 \\ -7&-21&0&-7 \end{array}\right) \\ &\left\{\begin{aligned} x'&=-3x+7y \\ -7x'-21y'&=-7y \end{aligned}\right. &&\left(\begin{array}{cc|cc} 1&0&-3&7 \\ -7&-21&0&-7 \end{array}\right) \\ &\left\{\begin{aligned} x'&=-3x+7y \\ -x'-3y'&=-y \end{aligned}\right. &&\left(\begin{array}{cc|cc} 1&0&-3&7 \\ -1&-3&0&-1 \end{array}\right) \\ &\left\{\begin{aligned} x'&=-3x+7y \\ -3y'&=-3x+6y \end{aligned}\right. &&\left(\begin{array}{cc|cc} 1&0&-3&7 \\ 0&-3&-3&6 \end{array}\right) \\ &\left\{\begin{aligned} x'&=-3x+7y \\ y'&=x-2y \end{aligned}\right. &&\left(\begin{array}{cc|cc} 1&0&-3&7 \\ 0&1&1&-2 \end{array}\right) \end{aligned}

逆行列の公式で求めた結果と一致します。

\begin{pmatrix}2&7\\1&3\end{pmatrix}^{-1} =\frac1{2×3-7×1} \begin{pmatrix}3&-7\\-1&2\end{pmatrix} =\begin{pmatrix}-3&7\\1&-2\end{pmatrix}

※ 今回のケースでは公式で求めた方が簡単ですが、行列のサイズが大きくなると簡単な公式はなくなるため、掃き出し法が活躍します。

連立方程式

$x,y$ が具体的な値であれば、中学校で習うような連立方程式を解くことになります。

先ほどの例に $x=1,y=2$ を代入した連立方程式を解きます。右辺が値になったため、行列表記の右半分が1列になります。

\begin{aligned} &\left\{\begin{aligned} 2x'+7y'&=1 \\ x'+3y'&=2 \end{aligned}\right. &&\left(\begin{array}{cc|c} 2&7&1 \\ 1&3&2 \end{array}\right) \\ &\left\{\begin{aligned} 6x'+21y'&=3 \\ -7x'-21y'&=-14 \end{aligned}\right. &&\left(\begin{array}{cc|c} 6&21&3 \\ -7&-21&-14 \end{array}\right) \\ &\left\{\begin{aligned} -x'&=-11 \\ -7x'-21y'&=-14 \end{aligned}\right. &&\left(\begin{array}{cc|c} -1&0&-11 \\ -7&-21&-14 \end{array}\right) \\ &\left\{\begin{aligned} x'&=11 \\ -7x'-21y'&=-14 \end{aligned}\right. &&\left(\begin{array}{cc|c} 1&0&11 \\ -7&-21&-14 \end{array}\right) \\ &\left\{\begin{aligned} x'&=11 \\ -x'-3y'&=-2 \end{aligned}\right. &&\left(\begin{array}{cc|c} 1&0&11 \\ -1&-3&-2 \end{array}\right) \\ &\left\{\begin{aligned} x'&=11 \\ -3y'&=9 \end{aligned}\right. &&\left(\begin{array}{cc|c} 1&0&11 \\ 0&-3&9 \end{array}\right) \\ &\left\{\begin{aligned} x'&=11 \\ y'&=-3 \end{aligned}\right. &&\left(\begin{array}{cc|c} 1&0&11 \\ 0&1&-3 \end{array}\right) \end{aligned}

逆行列による解に $x=1,y=2$ を代入した値と一致します。

\left\{\begin{aligned} x'&=-3x+7y=-3×1+7×2=11 \\ y'&=x-2y=1-2×2=-3 \end{aligned}\right.

逆行列による連立方程式の解法につながりますが、詳細は機会を改めます。

生成プログラム

計算例は Haskell で生成した組み合わせから適当に選びました。

Prelude> let n=[1..10] in [(a,b,c,d)|a<-n,b<-n,c<-n,d<-n,a*d-b*c==(-1),a/=c,b/=d,d`mod`c==0]
[(2,3,1,1),(2,5,1,2),(2,7,1,3),(2,9,1,4),(3,4,1,1),(3,7,1,2),(3,10,1,3),(4,5,1,1),(4,9,1,2),(5,6,1,1),(6,7,1,1),(7,8,1,1),(8,9,1,1),(9,10,1,1)]

a*d-b*c==(-1)d`mod`c==0 により計算途中で分数が出ません。