LU分解可能であるための必要十分条件
正方行列 $A$ を下三角行列 $L$ と 上三角行列 $U$ との積によって、
行列が LU分解可能であるための必要十分条件は、 全ての主座小行列の行列式が0でないことである (主座小行列については証明で定義を述べる)。
最終更新 2016年 6月19日
証明
主座小行列
$n$ 次正方行列を


このような行列の行列式が全て $0$ ではないこと、すなわち、

「全ての主座小行列の行列式が $0$ でない」$\hspace{5mm} \Longrightarrow \hspace{5mm}$ 「LU分解可能」 の証明
$k$ 次のベクトル $\mathbf{c}_{k}$ と $\mathbf{b}$ を


$ |A_{k}| \neq 0 $ $(k=1,\cdots, n)$ と仮定すると、 $A_{k}$ は逆行列 $A_{k}^{-1}$ を持つ (証明は行列式が0でない行列は逆行列を持つを参考)。 よって、$(2)$ の両辺に $A^{-1}_{k}$ を掛けることにより、 解 $\mathbf{c}_{k}$ が

そこで、 $\mathbf{c}_{k}$ の各成分を用いて、 $n$ 次の上三角行列 $C$ を




一般に、下三角行列の行列式は、対角成分の積になるので、 上式の行列式をとると、

これより、$|C| \neq 0$ であるので、 $C$ には逆行列 $C^{-1}$ が存在する。 そこで、 $(4)$ の両辺に $C^{-1}$ を掛けると、

$(3)$ より、$C$ は上三角行列である。 一般に、上三角行列の逆行列もまた、上三角行列になるので、 $C^{-1}$ は、


最後に、 $(5)$ の右辺の上三角行列 $C^{-1}$ の対角成分が $0$ でないこと証明する。 $C^{-1}$ は逆行列 $C$ を持つ。 一般に、 逆行列を持つ行列の行列式は 0 でないので、 $C^{-1}$ の行列式は 0 でない。 すなわち、

一方で、 $C^{-1}$ は上三角行列であるので、 行列式は対角成分の積で与えられる。 よって、


以上から、 行列 $A$ は、 (対角成分が$0$でない)下三角行列と上三角行列の積に分解できることが示された。
「LU分解可能」$\hspace{5mm} \Longrightarrow \hspace{5mm}$「全ての主座小行列の行列式が $0$ でない 」 の証明
行列 $A$ が


$L$ と $U$ の各成分をそれぞれ $l_{ij}$, $u_{ij}$ と表すと、 $A$ の 各成分 $a_{st}$ は、 $(6)$ から、

ここで、 $L$ が下三角行列であるため、


これらを踏まえて、 $A$ の $k$ 行 $k$ 列成分よりも左上にある成分に着目する。 すなわち、



これらより、 $(7)$ は、第 $k$ 項までの和のみによって表される。 すなわち、

この式は、 $A$ の $k$ 行 $k$ 列から左上にある各成分は、 $L$ の $k$ 行 $k$ 列から左上にある成分と、 $L$ の $k$ 行 $k$ 列から左上にある成分の積によって表されることを意味している。 すなわち、

左辺は、$A$ の主座小行列であり、右辺は、$L$ の主座小行列と $U$ の主座小行列の積になっている。 そこで、 それぞれの主座小行列を



$L_{k}$ と $U_{k}$ がそれぞれ下三角行列と上三角行列であることから、 行列式は対角成分の積になる。 よって、 $(11)$ から


一方で、 $u_{ii} \neq 0 $ $(i=1,2,\cdots,n)$ であるので、
