行列がLU分解可能であるための必要十分条件とその証明     - 理数アラカルト -

  LU分解可能であるための必要十分条件

  正方行列 $A$ を下三角行列 $L$ と 上三角行列 $U$ との積によって、 と表わすことをLU分解という。
  行列が LU分解可能であるための必要十分条件は、 全ての主座小行列の行列式が0でないことである (主座小行列については証明で定義を述べる)。

  証明

 
主座小行列
  $n$ 次正方行列を と表すとき、 主座小行列 $A_{k}$ $(k=1,2, \cdots, n)$ とは、 のように左上に位置する $A$ の部分行列のことである。 英語では、leading principle minor という。
  このような行列の行列式が全て $0$ ではないこと、すなわち、 がLU分解可能なための必要十分条件である。 それを以下のように証明する。


「全ての主座小行列の行列式が $0$ でない」$\hspace{5mm} \Longrightarrow \hspace{5mm}$ 「LU分解可能」 の証明
  $k$ 次のベクトル $\mathbf{c}_{k}$ と $\mathbf{b}$ を と定義し、 主座小行列 $A_{k}$ を係数行列とする連立一次方程式 を考える。
  $ |A_{k}| \neq 0 $ $(k=1,\cdots, n)$ と仮定すると、 $A_{k}$ は逆行列 $A_{k}^{-1}$ を持つ (証明は行列式が0でない行列は逆行列を持つを参考)。 よって、$(2)$ の両辺に $A^{-1}_{k}$ を掛けることにより、 解 $\mathbf{c}_{k}$ が と求まる。 これは、 $(2)$ 満たす $\mathbf{c}_{k}$ が唯一つ存在することを表している。
  そこで、 $\mathbf{c}_{k}$ の各成分を用いて、 $n$ 次の上三角行列 $C$ を と定義する。 $A$ と $C$ の積は、 と表せるが、 この行列の第 $k$ 列は、 $(1)$ と $(2)$ から、 となる。 すなわち、 $0$ から $k-1$ 行の成分が $0$ であり、 $k$ 行の成分が $1$ になる列ベクトルになる。 これより $AC$ は と表される下三角行列になる。
  一般に、下三角行列の行列式は、対角成分の積になるので、 上式の行列式をとると、 となる。 ここで、 積の行列式が行列式の積になること ($|AC| = |A| |C| $) を用いた。
  これより、$|C| \neq 0$ であるので、 $C$ には逆行列 $C^{-1}$ が存在する。 そこで、 $(4)$ の両辺に $C^{-1}$ を掛けると、 となる。
  $(3)$ より、$C$ は上三角行列である。 一般に、上三角行列の逆行列もまた、上三角行列になるので、 $C^{-1}$ は、 と表せる。 これより $A$ は、 と表される。 このように、行列 $A$ は下三角行列と上三角行列の積に分解できる。
  最後に、 $(5)$ の右辺の上三角行列 $C^{-1}$ の対角成分が $0$ でないこと証明する。 $C^{-1}$ は逆行列 $C$ を持つ。 一般に、 逆行列を持つ行列の行列式は 0 でないので、 $C^{-1}$ の行列式は 0 でない。 すなわち、 が成立する。
  一方で、 $C^{-1}$ は上三角行列であるので、 行列式は対角成分の積で与えられる。 よって、 が成立する。 これより、 $C^{-1}$ の個々の対角成分は 0 にならない。 すなわち、 が成立する。
  以上から、 行列 $A$ は、 (対角成分が$0$でない)下三角行列と上三角行列の積に分解できることが示された。


「LU分解可能」$\hspace{5mm} \Longrightarrow \hspace{5mm}$「全ての主座小行列の行列式が $0$ でない 」 の証明
  行列 $A$ が とLU分解できるとする。 ここで、 であり、 $u_{ii} \neq 0$ $(i=1,2,\cdots, n)$ である。
  $L$ と $U$ の各成分をそれぞれ $l_{ij}$, $u_{ij}$ と表すと、 $A$ の 各成分 $a_{st}$ は、 $(6)$ から、 と表せる。
  ここで、 $L$ が下三角行列であるため、 である。 同様に、 $U$ が上三角行列であるため、 である。
  これらを踏まえて、 $A$ の $k$ 行 $k$ 列成分よりも左上にある成分に着目する。 すなわち、 を満たす $a_{st}$ に着目する。 このとき、 $L$ が下三角行列であること $(8)$ から が成立する。 同様に、 $U$ が上三角行列であること $(9)$ から が成立する。
  これらより、 $(7)$ は、第 $k$ 項までの和のみによって表される。 すなわち、 が成立する。
  この式は、 $A$ の $k$ 行 $k$ 列から左上にある各成分は、 $L$ の $k$ 行 $k$ 列から左上にある成分と、 $L$ の $k$ 行 $k$ 列から左上にある成分の積によって表されることを意味している。 すなわち、 が成立する。
  左辺は、$A$ の主座小行列であり、右辺は、$L$ の主座小行列と $U$ の主座小行列の積になっている。 そこで、 それぞれの主座小行列を と定義すると、 $(10)$ は、 と表され、 その行列式は、 である。 ここで、積の行列式が行列式の積になる性質を用いた。
  $L_{k}$ と $U_{k}$ がそれぞれ下三角行列と上三角行列であることから、 行列式は対角成分の積になる。 よって、 $(11)$ から である。 これらより、 $|A_{k}|$ は、 である。
  一方で、 $u_{ii} \neq 0 $ $(i=1,2,\cdots,n)$ であるので、 である。 よって、 $A$ の任意の主座小行列の行列式は $0$ にならない。