[行列解析3.5]問題集

3.5問題集

演習 3.5.P1.

これまで、\( L \) が下三角行列で \( U \) が上三角行列である \( A = LU \) の分解について議論してきた。ここで、因子が異なる場合もあることに注意しながら、\( A = UL \) 分解の平行理論について議論せよ。

演習 3.5.P2.

\( A \) が \( A = QR \) の形で与えられ、\( Q \) がユニタリ行列、\( R \) が上三角行列である場合（2.1.14）、どのようにして方程式 \( Ax = b \) を解くか説明せよ。

演習 3.5.P3.

\( A, B \in M_n \) をユニット三角相似（unit triangularly equivalent）であるというのは、ある単位下三角行列 \( L \) と単位上三角行列 \( U \) が存在して \( A = L B U \) と表されることを意味する。次の事項を説明せよ：

(a) ユニット三角相似は \( M_n \) および \( GL(n, \mathbb{C}) \) 上で同値関係である理由。

(b) \( P, D, P', D' \in M_n \) が与えられ、\( P \) と \( P' \) が置換行列、\( D \) と \( D' \) が非特異対角行列の場合、次の条件が成り立つことを示せ：

P D = P' D' \quad \text{ならばかつそのときのみ} \quad P = P' \text{かつ} D = D'

(d) \( M_n \) の二つの一般化置換行列は、一致する場合に限りユニット三角相似である。

(e) n×n の一般化置換行列は、\( GL(n, \mathbb{C}) \) 上のユニット三角相似の同値関係に対する標準行列集合を形成する。

演習 3.5.P4.

\( A \in M_n \) の先頭主小行列式（leading principal minors）がすべて非零である場合、タイプ3の基本行操作（diagonal 以下の成分を 0 にする）を用いて、どのように \( A \) の LU 分解を得るか説明せよ。

演習 3.5.P5（ランチョス三重対角化アルゴリズム）.

\( A \in M_n \) と \( x \in \mathbb{C}^n \) が与えられている。次を定義する：

X = [x, Ax, A^2 x, \dots, A^{n-1} x]

列ベクトルの集合 \( X \) はクライロフ列（Krylov sequence）を形成すると言われる。ここで、\( X \) は非特異と仮定する。

(a) \( X^{-1}AX \) が \( A \) の特性多項式に対する随伴行列（companion matrix, 3.3.12）であることを示せ。

(b) \( R \in M_n \) が任意の非特異上三角行列であり、\( S = X R \) とするとき、\( S^{-1} A S \) が上ヘッセンベルグ行列（upper Hessenberg form）であることを示せ。

Y = [y, A^* y, (A^*)^2 y, \dots, (A^*)^{n-1} y]

ここで \( Y \) は非特異であり、かつ \( Y^* X \) が \( L D U \) と書けるとする。ここで \( L \) は下三角、\( U \) は上三角かつ非特異、\( D \) は対角かつ非特異である。このとき、非特異上三角行列 \( R \) と \( T \) が存在して、\((X R)^{-1} = T^* Y^* \) かつ \( T^* Y^* A X R \) が三重対角かつ \( A \) に相似であることを示せ。

(d) \( A \in M_n \) がエルミート行列（Hermitian）である場合、この考え方を用いて \( A \) に相似な三重対角エルミート行列を生成するアルゴリズムを説明せよ。

演習 3.5.P6.

\( M_n \) の与えられた行列の \( (n,n) \) 成分が、LU 分解の存在、L が非特異な場合、U が非特異な場合に影響を与えない理由を説明せよ。

演習 3.5.P7.

行列 \( C_n = [1 / \max\{i,j\}] \in M_n(\mathbb{R}) \) が次の LU 分解を持つことを示せ：

C_n = L_n L_n^T

ここで下三角行列 \( L_n \) の要素は \( l_{ij} = 1 / \max\{i,j\} \) （\( i \ge j \)）である。結論として、\(\det L_n = (1/n!)^2 \) である。

演習 3.5.P8.

(3.5.6) の条件「\( A[\{1, \dots, j\}] \) が全て非特異」は、「\( A[\{j, \dots, n\}] \) が全て非特異」に置き換え可能であることを示せ。

演習 3.5.P9.

\( A \in M_n(\mathbb{R}) \) を次の対称三重対角行列（0.9.10）とする：

\text{全主対角成分は } +2, \text{第一上三角と下三角成分は } -1

次の行列を考える：

L = \begin{bmatrix} 1 & & & \\ -1/2 & 1 & & \\ 0 & -2/3 & 1 & \\ \vdots & & \ddots & \ddots \\ 0 & \dots & - (n-1)/n & 1 \end{bmatrix}, \quad U = \begin{bmatrix} 2 & -1 & & \\ 0 & 3/2 & -1 & \\ \vdots & & \ddots & \ddots \\ 0 & \dots & 0 & n+1/n \end{bmatrix}

このとき \( A = L U \) かつ \(\det A = n+1 \) である。A の固有値は次の通りである：

\lambda_k = 4 \sin^2 \frac{k \pi}{2(n+1)}, \quad k = 1, \dots, n

注意：\( n \to \infty \) のとき \(\lambda_1(A) \to 0\)、\(\lambda_n(A) \to 4\)、そして \(\det A = \lambda_1 \cdots \lambda_n \to \infty\) である。

演習 3.5.P10.

\( A \in M_n \) が対称で、すべての先頭主小行列が非特異である場合、非特異下三角行列 \( L \) が存在して \( A = L L^T \) であることを示せ。つまり、LU 分解において \( U = L^T \) となる。

演習 3.5.P11.

置換行列 \( P = [p_{ij}] \in M_n \) を考える。これは 1, …, n の置換 \(\pi_1, …, \pi_n\) に対応し、\( p_{\pi_j,j} = 1 \)（その他の成分は 0）である。3.5.9 の記法を用い、

\text{rank } P[0,j] = 0, \quad j = 1, \dots, n

を定義する。次を示せ：

\pi_j = \min \{ k \in \{1, \dots, n\} : \text{rank } P[k,j] = \text{rank } P[k,j-1] + 1 \}, \quad j = 1, \dots, n

結論として、\( n^2 \) 個の数 \(\text{rank } P[k,j], k,j = 1,\dots,n\) により \( P \) は一意に決まる。

演習 3.5.P12.

\( P \in M_n \) を次のように分割する：

P = \begin{bmatrix} P_{11} & P_{12} \\ P_{21} & P_{22} \end{bmatrix}, \quad P^{-1} = \begin{bmatrix} P_{11}^T & P_{12}^T \\ P_{21}^T & P_{22}^T \end{bmatrix}

補零定理（law of complementary nullities, 0.7.5）を証明するために、次の関係を示せ：nullity \( P_{11} \) = \( P_{11} \) の零列数 = \( P_{21} \) の 1 の数 = \( P_{22} \) の零行数 = nullity \( P_{22}^T \)。

演習 3.5.P13.

補零定理（law of complementary nullities, 0.7.5）に関する次のアプローチの詳細を示せ。この方法は、LPU 分解を用いて、一般の場合を（簡単な）置換行列の場合から導くものである。

(a) \( A \in M_n \) を非特異行列とする。\( A \) と \( A^{-1} \) を次のように適合的に分割する：

A = \begin{bmatrix} A_{11} & A_{12} \\ A_{21} & A_{22} \end{bmatrix}, \quad A^{-1} = \begin{bmatrix} B_{11} & B_{12} \\ B_{21} & B_{22} \end{bmatrix}

補零定理は次を主張する：

\text{nullity } A_{11} = \text{nullity } B_{22}

これは我々が証明すべき内容である。

(b) \( A = L P U \) を LPU 分解とする。このとき、

A^{-1} = U^{-1} P^T L^{-1}

も LPU 分解である。両方の分解における置換行列の因子は一意に決まる。P を前問と同様に、A の分割に適合するように分割する。

\text{nullity } A_{11} = \text{nullity } P_{11} = \text{nullity } P_{22}^T = \text{nullity } B_{22}

参考文献.

演習 3.5.P5 は [Ste] から適応したもので、LU 分解の数値応用に関する追加情報を得ることができる。

LPU および LPDU 分解、三角相似（triangular equivalence）に関する議論は、L. Elsner, "On some algebraic problems in connection with general eigenvalue algorithms," Linear Algebra Appl. 26 (1979) 123–138 から適応したものである。

この文献では、対称または反対称行列に対する下三角合同（A = L B L^T, L は下三角かつ非特異）についても議論している。