本記事は数学の徹底解説シリーズに含まれます。
初学者の分かりやすさを優先するため，多少正確でない表現が混在することがあります。もし致命的な間違いがあればご指摘いただけると助かります。
LU分解の存在と必要十分条件
正方行列$A\in M_{n}(\mK)$に対し，単下三角行列$L$と上三角行列$U$を用いた次の$LU$分解を考える。
A &= LU
\end{align}
ただし，$\mK$は複素数空間$\mC$または実数空間$\mR$を表し，$M_{n}(\mK)$は$\mK$上の$n$次正方行列全体の集合を表す。このとき，次の二つは同値である
- 正則行列$A$の$LU$分解が存在する
- すべての首座小行列式が$0$でない
コレスキー分解はLU分解の特別なケースであり，首座小行列式と行列の符号に密接な関係があることを組み合わせれば，コレスキー分解と正定値の繋がりが腑に落ちるはずです。
証明
必要性と十分性に分けて証明します。
必要性
$A$の$LU$分解が存在するならばすべての首座小行列式が$0$でないことを証明します。まず，$A,L,U$を$k$次首座小行列とそれ以外のブロックに区分けします。
A &=
\begin{bmatrix}
A_{k} & \ast \\
\ast & \ast
\end{bmatrix},\quad
L =
\begin{bmatrix}
L_{k} & O \\
\ast & \ast
\end{bmatrix},\quad
U =
\begin{bmatrix}
U_{k} & \ast \\
O & \ast
\end{bmatrix}
\end{align}
ただし，$1\leq k\leq n$とします。$LU$分解の等式$A=LU$において$k$次首座小行列に着目すると，
A_{k} &= L_{k}U_{k}\label{首座}
\end{align}
が得られます。ここで，正則行列の首座小行列もまた正則になることに注意すると，正則行列の積と正則性の関係より$L_{k},U_{k}$はそれぞれ正則になります。正則行列の行列式は0でないことから，$L_{k},U_{k}$の行列式は$0$ではないことが分かります。したがって，式($\ref{首座}$)の両辺の行列式をとると
\det(A_{k}) &= \det(L_{k})\det(U_{k}) \neq 0
\end{align}
が得られます。以上より，$A$のすべての首座小行列式が$0$でないことが示されました。
十分性
すべての首座小行列式が$0$でないならば$A$の$LU$分解が存在することを証明します。帰納法に基づき，Gaussの消去法の前進消去を行うことで$LU$分解の形が出現することを利用します。以下では，$A=(a_{i,j})$とします。
まず，$1$次首座小行列式が$0$でないとき，すなわち$a_{11}\neq 0$のときを考えます。このとき，
J &=
\begin{bmatrix}
1 &&&\ast\\
-a_{21}/a_{11}&1\\
\vdots&&\ddots\\
-a_{n1}/a_{nn}&O&&1
\end{bmatrix}
\end{align}
で定義される下三角行列を左から掛けることにより，Gaussの消去法の前進消去を行うことができます。すなわち，
JA &=
\begin{bmatrix}
a_{11}&\ast\\
O&\ast
\end{bmatrix}
\end{align}
のように第$1$行より下を掃き出せることが分かりました。次に，$k$次首座小行列式が$0$でないとき，第$k$行より下を掃き出すことができると仮定します。すなわち，ある下三角行列$J$が存在して
JA &=
\begin{bmatrix}
u_{11}&&\ast&\ast\\
&\ddots\\
O&&u_{k}\\
O&&&B
\end{bmatrix}\label{仮定}
\end{align}
が成り立つと仮定します。このとき，$JA$の$k+1$次首座小行列式は
[JA]_{k+1} &= J_{k+1}A_{k+1} =
\begin{bmatrix}
u_{11}&&\ast&\ast\\
&\ddots\\
O&&u_{k}\\
O&&&u_{k+1,k+1}
\end{bmatrix}
\end{align}
となります。ただし，$u_{k+1,k+1}$は$B$の$(1,1)$成分を表します。仮定より$\det(A_{k+1})\neq 0$であることに注意すると，両辺の行列式をとることにより
\det([JA]_{k+1}) &= \det(J_{k+1})\det(A_{k+1}) = \det(A_{k+1}) = u_{11}\cdots u_{k+1,k+1} \neq 0
\end{align}
が得られますので，$u_{k+1,k+1}\neq 0$が分かります。ただし，積の行列式の性質と三角行列の行列式の性質を利用しました。したがって，$u_{k+1,k+1}$を基準にして第$k+1$行よりも下を掃き出せることが分かりました。以上より，$1\leq k\leq n$なる任意の$k$に対して式($\ref{仮定}$)が成り立つことが示されました。$J$によって$A$が掃き出された後の行列を$U$とおくと，次が成り立ちます。
JA &= U \label{掃き出された後}
\end{align}
さて，$J$は単下三角行列でしたので，単三角行列の逆行列も単三角行列になることから，$J$の逆行列を$L$とおくと$L$も単下三角行列となります。したがって，式($\ref{掃き出された後}$)の左から$L$を掛けると
A &= LU
\end{align}
が得られます。ゆえに，$A$の$LU$分解が存在することが示されました。
コメント