ベイジアン研究所

プログラミング言語(アルゴリズム的な話が中心)やガジェットの紹介をしています。時々心理学の話も。

【線形代数学入門】行列の掃き出し

1. 記事の目的
以下の記事で、行列の基本変形に関して述べた。本記事では行列を用いて連立方程式を解く際の、行列の操作である掃き出しについて解説する。掃き出しの操作としては、行列の基本変形を繰り返して行われるものである。

2. 行列の掃き出し
(m,n)型行列A(p,q)成分が0でないとき、次の一連の操作を考える。
(1) p行を(p,q)成分で割って、(p,q)成分を1にする((左1)の操作)。
(2) p以外のすべてのiに対して、第i行から第p行の(i,p)成分倍を引く((左3)の操作)。

(1)、(2)の操作によりAは図1のA^{\prime}に変形される。

f:id:camelsan:20210206101029p:plain
図1 第q列の掃き出し
これを(p,q)をかなめとし、左から第q列を掃き出すという。

さらに次の操作を行う。
(3) q以外の全てのjに対し、第j列から第q列の(p,j)成分倍を引く。

(3)の操作により、A^{\prime}は図2のA^{\prime\prime}に変形される。

f:id:camelsan:20210206101736p:plain
図2 第p行の掃き出し

3. 正則行列に関する定理
掃き出しを利用することで、正則行列に関する、次の定理を証明することができる。

n次正方行列Aに対し、XA=Eとなるn次行列Xが存在すれば、Aは正則である。
(Aが正則であるかを判定するには、AX=XA=Eとなる行列Xが存在するか否かを調べる必要があったが、XA=EとなるXを見つけるだけで良いことになる、というのがこの定理の意味することである。)
証明nに関する数学的帰納法により証明する。n1のとき、AXは共に通常の数となり、交換できるので、成立する。
n>1とし、n-1次行列に対しては主張が正しいと仮定する。行列に(1,1)成分を考える。その成分が0でないときは良い。0のとき、Aは零行列ではないので(零行列とすると、AX=Eより、E=0となり矛盾)、どこかの成分は0ではない成分がある。よって、行や列を入れ替えることで(基本変形を繰り返す)、(1,1)成分に0でない成分を移動させる。(1,1)をかなめとし、第1列と第1行を掃き出すとAは次の行列Bに変形される。

\begin{pmatrix}1&^{t}\textbf{0}\\ \textbf{0}&A_1\end{pmatrix}

ここで、^{t}\textbf{0}=(0,\dots,0)を表す。
行列の基本変形とは、基本行列を掛けることなので、ある正則行列PQを適当に取ると(P, Qは基本行列をいくつか欠けたもの)

PAQ=B=\begin{pmatrix}1&^{t}\textbf{0}\\ \textbf{0}&A_1\end{pmatrix}

が成り立つ。

ここで、X_1A_1=EとなるX_1が存在することを証明する。XA=Eより、この式にPAQという項が現れるようにしたい。左からQ^{-1}、右からQを掛けると、

Q^{-1}XAQ=QQ^{-1}=E

P^{-1}P=Eより、

E=Q^{-1}XEAQ=Q^{-1}XP^{-1}PAQ

ここで出現する、未知の行列である、[texQ^{-1}XP^{-1}]について考える。Q^{-1}XP^{-1}PAQと同じ形に区分けする。即ち、

Q^{-1}XP^{-1}=\begin{pmatrix}u&^{t}\textbf{z}\\ \textbf{y}&X_1\end{pmatrix}

とする。(Q^{-1}XP^{-1})(PAQ)=Eより、

\begin{pmatrix}u&^{t}\textbf{z}\\ \textbf{y}&X_1\end{pmatrix}\begin{pmatrix}1&^{t}\textbf{0}\\ \textbf{0}&A_1\end{pmatrix}=\begin{pmatrix}1&^{t}\textbf{0}\\ \textbf{0}&E_{n-1}\end{pmatrix}

左辺を計算すると、

\begin{pmatrix}u&^{t}\textbf{z}\\ \textbf{y}&X_1\end{pmatrix}\begin{pmatrix}1&^{t}\textbf{0}\\ \textbf{0}&A_1\end{pmatrix}=\begin{pmatrix}u&^{t}\textbf{z}A_1\\ \textbf{y}&X_1A_1\end{pmatrix}

より、

\begin{pmatrix}u&^{t}\textbf{z}A_1\\ \textbf{y}&X_1A_1\end{pmatrix}=\begin{pmatrix}1&^{t}\textbf{0}\\ \textbf{0}&E_{n-1}\end{pmatrix}

従って、

X_1A_1=E_{n-1}

よって、帰納法の仮定より、A_1は正則である。従って以下の記事の区分けされた行列に関する逆行列の定理(左上と右下の行列が正則であれば、元の行列も正則)より

B=\begin{pmatrix}1&^{t}\textbf{0}\\ \textbf{0}&A_1\end{pmatrix}

も正則である。PAQ=Bより、A=P^{-1}AQ^{-1}であるから、Aも正則である(正則行列同士をかけても正則)。

camelsan.hatenablog.com

4. 参考文献
[1] 線形代数学入門