LU分解

要点：$\ell_k$ は第 $k$ 成分までが $0$ なので、$j\le k$ なら $e_j^{\top}\ell_k=0$ である。積を展開すると、この形の因子を含む項がすべて消える。

消去の手順：$A^{(1)}:=A$ とおく。$k=1,\dots,n-1$ について、第 $k$ 段を次のように行う。第 $k$ 列の第 $k$ 行以下の成分 $a^{(k)}_{ik}$（$i\ge k$）に $0$ でないものがあれば、その 1 つ $a^{(k)}_{r_kk}$ を選ぶ（部分ピボット選択ではその規則で選ぶ）。すべて $0$ なら $r_k:=k$ とする。第 $k$ 行と第 $r_k$ 行を入れ替える置換行列を $P_k$（$r_k=k$ なら $P_k=I_n$）とし、$B:=P_kA^{(k)}$ とおく。$b_{kk}\ne0$ なら $\ell_k$ の第 $i$ 成分（$i>k$）を $b_{ik}/b_{kk}$ とし、$b_{kk}=0$（このとき $b_{ik}=0$ がすべての $i>k$ で成り立つ）なら $\ell_k:=0$ とする。$M_k:=I_n-\ell_ke_k^{\top}$、$A^{(k+1)}:=M_kB$ とおく。
形が保たれること：$A^{(k)}$ の第 $1$ 列から第 $k-1$ 列で対角より下の成分が $0$ であるとする。入れ替える 2 つの行の番号は $k$ 以上なので、どちらの行も第 $1$ 列から第 $k-1$ 列の成分が $0$ であり、$B$ も同じ形である。$M_k$ を掛けると第 $i$ 行（$i>k$）から第 $k$ 行の（$\ell_k$ の第 $i$ 成分）倍が引かれるが、第 $k$ 行は第 $1$ 列から第 $k-1$ 列が $0$ なので、それらの列は変わらない。第 $k$ 列の第 $i$ 成分は $b_{ik}-\frac{b_{ik}}{b_{kk}}b_{kk}=0$ になる（$\ell_k=0$ の場合ははじめから $0$）。よって $A^{(k+1)}$ の第 $1$ 列から第 $k$ 列は対角より下が $0$ である。帰納法により $U:=A^{(n)}$ は上三角行列であり、
$$ U=M_{n-1}P_{n-1}M_{n-2}P_{n-2}\cdots M_1P_1A $$
が成り立つ。
置換を右へ集める：$Q_k:=P_{n-1}P_{n-2}\cdots P_{k+1}$（$Q_{n-1}:=I_n$）、$P:=P_{n-1}\cdots P_1=Q_1P_1$、$\widetilde M_k:=Q_kM_kQ_k^{-1}$ とおく。$Q_{k-1}=Q_kP_k$ なので $Q_k^{-1}Q_{k-1}=P_k$ であり、
$$ \widetilde M_{n-1}\widetilde M_{n-2}\cdots\widetilde M_1P=M_{n-1}(Q_{n-1}^{-1}Q_{n-2})M_{n-2}(Q_{n-2}^{-1}Q_{n-3})\cdots M_1(Q_1^{-1}Q_1P_1)=M_{n-1}P_{n-1}\cdots M_1P_1 $$
である。$Q_k^{-1}=P_{k+1}\cdots P_{n-1}$ で、$P_j$（$j>k$）は番号が $j$ 以上、したがって $k$ より大きい 2 つの行を入れ替えるので、lem-lu-gauss の 3 を $P_{k+1},\dots,P_{n-1}$ について順に使うと、$\widetilde M_k=I_n-\widetilde\ell_ke_k^{\top}$（$\widetilde\ell_k:=Q_k\ell_k$）は第 $k$ 列の Gauss 変換である。よって $\widetilde M_{n-1}\cdots\widetilde M_1PA=U$ であり、lem-lu-gauss の 1 により
$$ PA=\widetilde M_1^{-1}\cdots\widetilde M_{n-1}^{-1}U=LU,\qquad L:=I_n+\sum_{k=1}^{n-1}\widetilde\ell_ke_k^{\top} $$
となる。lem-lu-gauss の 2 により $L$ は単位下三角行列で、その第 $k$ 列の対角より下は $\widetilde\ell_k$、すなわち乗数を後の入れ替えで並べ替えたものである。これで 1 が示された。
2：$\det L=1$ なので $\det P\det A=\det U=u_{11}\cdots u_{nn}$ であり、$\det P=\pm1$ で $\det P^{-1}=\det P$ である。$A$ が正則であることと $\det A\ne0$、したがって $\det U\ne0$ とは同値である。
3：部分ピボット選択では $b_{kk}$ が第 $k$ 列の第 $k$ 行以下で絶対値が最大なので、$b_{kk}\ne0$ のとき乗数は $\lvert b_{ik}/b_{kk}\rvert\le1$ を満たす。$\ell_k=0$ の場合も同じである。$\widetilde\ell_k$ の成分は $\ell_k$ の成分の並べ替えなので、$\lvert l_{ij}\rvert\le1$ である。$\square$

要点：第 $k$ 段は除法 $n-k$ 回と、乗法・減法が各 $(n-k)^2$ 回である。

1：$\mu_k:=\max_{i,j}\lvert a^{(k)}_{ij}\rvert$ とおく。$B=P_kA^{(k)}$ は行を入れ替えただけなので成分の最大値は $\mu_k$ である。$A^{(k+1)}=M_kB$ の成分は、第 $k$ 行以上では $B$ の成分のままで、第 $i$ 行（$i>k$）では $b_{ij}-\ell_ib_{kj}$ である。thm-lu-plu の 3 により $\lvert\ell_i\rvert\le1$ なので
$$ \lvert b_{ij}-\ell_ib_{kj}\rvert\le\lvert b_{ij}\rvert+\lvert\ell_i\rvert\lvert b_{kj}\rvert\le2\mu_k $$
である。よって $\mu_{k+1}\le2\mu_k$ であり、$\mu_1=\max\lvert a_{ij}\rvert$ から帰納法で $\mu_k\le2^{k-1}\mu_1$ を得る。$k\le n$ なので $\rho(A)\le2^{n-1}$ である。
2：$n$ についての帰納法で、次を示す。「第 $n$ 列が $c$（$c$ は複素数）で、それ以外は $W_n$ と同じ行列 $W_n(c)$ を部分ピボット選択で消去すると、行は入れ替わらず、第 $1$ 段のあと右下の $n-1$ 次の部分は $W_{n-1}(2c)$ になる。」第 $1$ 列は $1,-1,\dots,-1$ で絶対値はすべて $1$ なので、規則により番号最小の第 $1$ 行がピボットになり、入れ替えは起きない。乗数はすべて $-1$ で、各行 $i\ge2$ に第 $1$ 行 $(1,0,\dots,0,c)$ を足す。第 $2$ 列から第 $n-1$ 列は第 $1$ 行の成分が $0$ なので変わらず、第 $n$ 列は $c+c=2c$ になる。よって右下の部分は $W_{n-1}(2c)$ である。$W_n=W_n(1)$ から始めてこれを繰り返すと（最後は $W_1(2^{n-1})=(2^{n-1})$）、第 $k$ 段のあとの右下の部分は $W_{n-k}(2^k)$ であり、$u_{nn}=2^{n-1}$ である。成分の絶対値の最大は第 $k$ 段のあとで $2^k$、最後に $2^{n-1}$ で、$\max\lvert w_{ij}\rvert=1$ なので $\rho(W_n)=2^{n-1}$ である。$\square$

1：$\lvert a_{11}\rvert>\sum_{i\ge2}\lvert a_{i1}\rvert\ge0$ なので $a_{11}\ne0$ である。$j\ge2$ を固定し、$s_{ij}:=a_{ij}-a_{i1}a_{1j}/a_{11}$ とおく。三角不等式と、第 $1$ 列の対角優位から出る $\sum_{i\ge2,\,i\ne j}\lvert a_{i1}\rvert<\lvert a_{11}\rvert-\lvert a_{j1}\rvert$ により
$$ \sum_{i\ge2,\,i\ne j}\lvert s_{ij}\rvert\le\sum_{i\ge2,\,i\ne j}\lvert a_{ij}\rvert+\frac{\lvert a_{1j}\rvert}{\lvert a_{11}\rvert}\sum_{i\ge2,\,i\ne j}\lvert a_{i1}\rvert\le\sum_{i\ge2,\,i\ne j}\lvert a_{ij}\rvert+\lvert a_{1j}\rvert-\frac{\lvert a_{1j}\rvert\lvert a_{j1}\rvert}{\lvert a_{11}\rvert} $$
である。右辺の最初の 2 項の和は $\sum_{i\ne j}\lvert a_{ij}\rvert$ で、第 $j$ 列の対角優位によりこれは $\lvert a_{jj}\rvert$ より真に小さい。また $\lvert a_{jj}\rvert-\frac{\lvert a_{1j}\rvert\lvert a_{j1}\rvert}{\lvert a_{11}\rvert}\le\lvert s_{jj}\rvert$ である。よって $\sum_{i\ge2,\,i\ne j}\lvert s_{ij}\rvert<\lvert s_{jj}\rvert$ となる。
2：第 $1$ 列の対角優位から $\lvert a_{11}\rvert>\lvert a_{i1}\rvert$（$i\ge2$）なので、部分ピボット選択は第 $1$ 行を選び、乗数は $\lvert a_{i1}/a_{11}\rvert<1$ である。消去のあとの右下の部分は 1 の $S$ で、再び列について狭義の対角優位なので、同じ議論を $n$ についての帰納法で繰り返せる。行が一度も入れ替わらないので $P=I_n$ で、$L$ の成分は乗数そのものである。$U$ の対角成分は各段のピボットで $0$ でないので、thm-lu-plu の 2 により $A$ は正則である。
3：まだ消去していない部分の各列の絶対値の和が、段を進めても増えないことを示す。