3.5.11定理
定理 3.5.11
（LPU分解）．任意の \( A \in M_n \) に対して、置換行列 \( P \in M_n \)、単位下三角行列 \( L \in M_n \)、および上三角行列 \( U \in M_n \) が存在して、次が成り立つ：
A = L P U
さらに、もし \( A \) が非特異であれば、因子 \( P \) は一意的に定まる。
証明.
整数 \(1, \ldots, n\) の順列 \(\pi_1, \ldots, \pi_n\) を帰納的に次のように構成する。まず
A^{(0)} = [a^{(0)}_{ij}] = A
とし、添字集合を
I_1 = \{ i \in \{1, \ldots, n\} : a^{(0)}_{i1} \neq 0 \}
と定める。もし \( I_1 \) が空でなければ、\(\pi_1\) を \( I_1 \) の最小の整数とする。もし \( I_1 \) が空ならば、\(\pi_1\) を任意の \( i \in \{1, \ldots, n\}\) として次のステップへ進む。
もし \( I_1 \) が空でなければ、\( A^{(0)} \) の \(\pi_1\) 行を用いた 3 型の基本行操作により、列 1 の \( a^{(0)}_{\pi_1,1} \) 以外のすべての非零成分 \( a^{(0)}_{i1} \)（ただし \( i \gt \pi_1 \)）を消去する。この操作後の行列を \( A^{(1)} \) とし、ある単位下三角行列 \( L_1 \) に対して
A^{(1)} = L_1 A^{(0)}
が成り立つことに注意する。
一般に、\( 2 \leq k \leq n \) とし、\(\pi_1, \ldots, \pi_{k-1}\) および \( A^{(k-1)} = [a^{(k-1)}_{ij}] \) が構成されていると仮定する。このとき
I_k = \{ i \in \{1, \ldots, n\} : i \neq \pi_1, \ldots, \pi_{k-1}, \; a^{(k-1)}_{i k} \neq 0 \}
と定める。もし \( I_k \) が空でなければ、\(\pi_k\) をその最小の整数とする。もし空であれば、\(\pi_1, \ldots, \pi_{k-1}\) 以外の任意の \( i \) を \(\pi_k\) として次のステップへ進む。
もし \( I_k \) が空でなければ、\( A^{(k-1)} \) の \(\pi_k\) 行を用いた 3 型の基本行操作により、列 \( k \) における成分 \( a^{(k-1)}_{\pi_k,k} \) の下にあるすべての非零成分 \( a^{(k-1)}_{i k} \)（ただし \( i \gt \pi_k \)）を消去する。この操作後の行列を \( A^{(k)} \) とし、ある単位下三角行列 \( L_k \) に対して
A^{(k)} = L_k A^{(k-1)}
が成り立つ。なお、この消去操作は \( A^{(k-1)} \) の列 \( 1, \ldots, k-1 \) の成分を変化させない（なぜなら \( a^{(k-1)}_{\pi_k,j} = 0 \) が \( j=1, \ldots, k-1 \) に対して成り立つから）ことに注意する。
この手続きを \( n \) ステップ繰り返すと、順列 \(\pi_1, \ldots, \pi_n\) と行列
A^{(n)} = [a^{(n)}_{ij}] = L A
が得られる。ただし \( L = L_n \cdots L_1 \) は単位下三角行列である。さらに、\( a^{(n)}_{ij} \) は \( i \gt \pi_j \) または \( i \lt \pi_j \) かつ \( i \notin \{\pi_1, \ldots, \pi_{j-1}\} \) のとき 0 となる。
ここで \( \mathcal{L} = L^{-1} \) とすると、\( A = \mathcal{L} A^{(n)} \) であり、\(\mathcal{L}\) は単位下三角行列である。さらに、\( P = [p_{ij}] \in M_n \) を
p_{\pi_j, j} = 1 \quad (j=1, \ldots, n), \quad \text{その他の成分はすべて } 0
で定めると、\( P \) は置換行列となる。このとき \( P^T A^{(n)} = U \) は上三角行列であり、
A = \mathcal{L} P U
が成り立つ。
もし \( A \) が非特異であれば、\( \mathcal{L} \) と \( U \) はともに非特異である。直前の練習問題により、任意の \( p,q \in \{1, \ldots, n\} \) に対して
\mathrm{rank}\, A[p,q] = \mathrm{rank}\, P[p,q]
が成り立ち、これらの階数が置換行列 \( P \) を一意に定めることになる（(3.5.P11) を参照）。∎
練習問題.
上の証明における構成が、なぜ \( P^T A^{(n)} \) を上三角行列にするのかを説明せよ。
コメント