[行列解析6.1]問題集

6.1.問題集

6.1.P1　

次の\(n\)-by-\(n\)system反復アルゴリズムを用いて線形方程式
\(Ax=y\) を解くことを考える。

ここで \(A\) と \(y\) は与えられている。

(i) \(B=I-A\) とおき，systemを
\(x=Bx+y\) の形に書き換える。
(ii) 初期ベクトル \(x^{(0)}\) を選ぶ。
(iii) \(m=0,1,2,\dots\) に対し \(x^{(m+1)}=Bx^{(m)}+y\) を計算し，
\(x^{(m)}\to x\) を期待する。

(a) \(e^{(m)}=x^{(m)}-x\) とおくと，
\(e^{(m)}=B^{m}(x^{(0)}-x)\) が成り立つことを示せ。
(b) したがって \( \rho(I-A) \lt 1 \) ならば，初期近似 \(x^{(0)}\) の選び方に依らず \(x^{(m)}\to x\) と収束することを結論せよ。
(c) ゲルシュゴリンの定理を用いて，本アルゴリズムが動作するための行列 \(A\) に対する簡明かつ明示的な十分条件を与えよ。

6.1.P2　

次を示せ：

\bigcap_{S\ \text{nonsingular}} G(S^{-1} A S) = \sigma(A),

ここで交差はすべての正則行列 \(S\) についてとるものとする（すなわち，任意の相似変換によるゲルシュゴリン集合の交わりはスペクトルに等しい）。

6.1.P3　

\(A=[a_{ij}]=[a_1\ \dots\ a_n]\in M_n\) とする。式 (6.1.5) を用いて次を示せ：

\left| \det A \right| \le \prod_{j=1}^n \left( \sum_{i=1}^n |a_{ij}| \right) = \prod_{j=1}^n \|a_j\|_1,

同様の不等式が行に関しても成り立つことを示し，(5.6.P10) のアプローチと比較せよ。

6.1.P4　

\(A\in M_n\) とし，(6.1.2) で定義された集合 \(G(A)\) を考える。本文中で「すべての固有値が \(G(A)\) に含まれる」という主張が (6.1.10a) を含意することを示した。逆の含意、つまり (6.1.10a) から固有値が \(G(A)\) に含まれることを証明せよ。

6.1.P5　

行列 \(A\in M_n\) の n 個のゲルシュゴリン円板が互いに互いに素（互いに交わらない）であるとする。次を示せ。
(a) \(A\) が実行列ならば，\(A\) のすべての固有値は実数である。
(b) \(A\in M_n\) が主対角成分を実数にもち，かつその特性多項式の係数がすべて実数であるなら，\(A\) のすべての固有値は実数である。

6.1.P6　

\(A=[a_{ij}]\in M_n\) とし，ある \(i\) に対して \( |a_{ii}| \gt R_i \) が \(k\) 個の異なる値で成り立つとする。このとき主小行列（principal submatrices）の性質を用いて \( \operatorname{rank} A \ge k \) を示せ。

6.1.P7　

\(A\in M_n\) が冪等行列（idempotent）であり \(A\neq I\) であると仮定する。すると \(A\) は厳密な対角優位（あるいは既約に厳密な対角優位）であり得ないことを示せ（参照：(6.2.25), (6.2.27)）。

6.1.P8　

\(A=[a_{ij}]\in M_n\) が厳密対角優位、すなわちすべての \(i=1,\dots,n\) に対して \( |a_{ii}| \gt R_i \) であるとする。このとき少なくとも一つの \(k\in\{1,\dots,n\}\) について \( |a_{kk}| \gt C_k \) が成り立つことを示せ。

R_i(A)=\sum_{j\ne i}|a_{ij}| \\\qquad i=1,\dots,n

C_j(A)=\sum_{i\ne j}|a_{ij}|\\ \qquad j=1,\dots,n

6.1.P9　

\(A=[a_{ij}]\in M_n\) を厳密対角優位とする。すなわち \( |a_{ii}| \gt R_i \) がすべての \(i\) で成り立つとする。 \(D=\mathrm{diag}(a_{11},\dots,a_{nn})\) とおくとき，なぜ \(D\) が正則であるかを説明し，さらに \( \rho(I-D^{-1}A) \lt 1 \) が成り立つことを示せ。

6.1.P10　

\(A=[a_{ij}]=[a_1\ \dots\ a_n]\in M_n\) とする。次の下界を示せ：

\operatorname{rank} A \ge \sum_{i:\,a_i\neq 0} \frac{|a_{ii}|}{\|a_i\|_1},

ここで \(a_i\) は第 \(i\) 列ベクトル（または文脈に応じて行ベクトル）を表し，\(\|a_i\|_1=\sum_j |a_{ij}|\) と定義する。すなわち，各対角要素の絶対値を対応する 1-ノルムで正規化した値の和がランクの下界を与えることを示せ。

6.1.P11　

\(A=[a_{ij}]=[a_1\ \dots\ a_n]\in M_n\) とする。次を示せ。

\operatorname{rank} A \ge \sum_{i:\,a_i\neq 0} \frac{|a_{ii}|^2}{\|a_i\|_2^2},

ここで \(a_i\) は第 \(i\) 列ベクトルであり，\(\|a_i\|_2\) はその 2-ノルム（ユークリッドノルム）である。

6.1.P12　

\(A\in M_n\) とする。もし \(A\) が Toeplitz（テプリッツ）行列、あるいはより一般にパース対称（persymmetric）でありかつすべての主対角成分が等しいならば，\(G(A)=G(A^T)\) であることを示せ。

（注）パース対称とは，行列が反対角に関して対称になる性質を指す。テプリッツ行列は各対角上の要素が一定である行列であり，自然にこの条件を満たす。

6.1.P13　

\(A=[a_{ij}]\in M_n(\mathbb{R})\) が厳密対角優位であるとする。すなわち各 \(i\) について \( |a_{ii}| \gt R_i \) が成り立つとする。このとき \(\det A\) は対角要素の積 \(a_{11}\cdots a_{nn}\) と同符号であることを示せ。

6.1.P14　

\(A=[a_{ij}]\in M_n\) とする。次の各項を示せ／説明せよ。

(a) ある \(i,j\) に対して \( |a_{ii}-a_{jj}| \gt R_i + R_j \) が成り立つならば，行 \(i\) と行 \(j\) に対応するゲルシュゴリン円板は互いに交わらないことを説明せよ。

(b) すべての互いに異なる \(i,j\) について \( |a_{ii}-a_{jj}| \gt R_i + R_j \) が成り立つなら，\(A\) は \(n\) 個の異なる固有値をもつことを説明せよ。

6.1.P15　

\(A=[a_{ij}]\in M_n\) が対角優位であるとする。次を示せ／説明せよ。

(a) \(\rho(A)\le 2\max_i |a_{ii}|\) が成り立つことを示せ。
(b) もし \(A\) が厳密対角優位なら，\(\rho(A)\lt 2\max_i |a_{ii}|\) が成り立つことを説明せよ。

6.1.P16　

「ガウスの消去法は厳密対角優位性を保つ」という格言を検討する問題である。\(n\ge 2\) とし，\(A\in M_n\) が厳密対角優位であると仮定する。

(a) \(A\) の先頭からのすべての主小行列（leading principal submatrices）が非特異であることを説明せよ。
(b) 行列を次のように分割する：

A = \begin{pmatrix} a & y^{T} \\ x & B \end{pmatrix},

ここで \(x,y\in \mathbb{C}^{n-1}\) である。第1列に対してガウス消去を行うと，

A' = \begin{pmatrix} a & y^{T} \\ 0 & C \end{pmatrix}, \\ C = B - a^{-1} x y^{T}

このとき \(C\)（したがって \(A'\)）が厳密対角優位であることを示せ。
(c) ブロック分割

A = \begin{pmatrix} A_{11} & A_{12} \\ A_{21} & A_{22} \end{pmatrix},

ここで \(A_{11}\in M_k\) とする。シュール補行列

\(C = A_{22}-A_{21}A_{11}^{-1}A_{12}\) を考え，(a) と帰納法を用いて，ブロック単位のガウス消去後の行列

\begin{pmatrix} A_{11} & A_{12} \\ 0 & C \end{pmatrix}

が厳密対角優位であることを説明せよ。

6.1.P17　

この問題はゲルシュゴリンの定理をブロック行列に拡張するものである。

まず前提を説明する。

与えられた行列ノルム \( \!\!\;|\!|\!|\cdot|\!|\! \!\)（以下単に \( \!\;|\!|\cdot|\!|\! \) と書くこともある）を \(M_m\) に対して固定し，\(M_{mn}\) 上の対応するノルム \(N(\cdot)\) を (5.6.P55) の定義に従って用いる。

任意のブロック行列 \(A=[A_{ij}]_{i,j=1}^n \in M_{mn}\) について，次を定義する：

R_i = \sum_{j\ne i} \,\!\;|\!|\!| A_{ij} |\!|\!|\quad (i=1,\dots,n).

また \(D = A_{11}\oplus\cdots\oplus A_{nn}\) とする。

(a) \(z\in\mathbb{C}\) が \(D\) の固有値でないとき，次の因子分解が成り立つことを説明せよ：

zI - A = (zI - D)\bigl(I - (zI - D)^{-1}(A-D)\bigr).

続いて (5.6.16) に続く演習の議論を用いて，もし \(N((zI-D)^{-1}(A-D))\lt 1\) ならば \(z\) は \(A\) の固有値でないことを結論できることを示せ。また

N((zI-D)^{-1}(A-D)) \le \max_{1\le i\le n} \bigl( \!\;|\!|\!| (zI - A_{ii})^{-1} |\!|\!|\; R_i \bigr).

(b) \(z\in\mathbb{C}\) が任意の \(A_{ii}\) の固有値でなく，かつ各 \(i\) について \(\!\;|\!|\!|(zI-A_{ii})^{-1}|\!|\!|\;^{-1} \gt R_i\) が成り立つとき，\(z\) は \(A\) の固有値でないことを説明せよ。

(c) 以上より，任意の固有値は次の集合に含まれることを説明せよ：

\bigcup_{i=1}^n \sigma(A_{ii}) \cup \bigcup_{i=1}^n \left\{ z\in\mathbb{C}: \begin{aligned} & z\notin\sigma(A_{ii}),\\ & \!| \!| \!| (zI-A_{ii})^{-1} \!| \!| \!|^{-1} \le R_i \end{aligned} \right\}

この包含集合を (6.1.13) とする。

(d) 我々は行列ノルム \( \!\;|\!|\cdot|\!|\! \) に関してブロック厳密対角優位（block strictly diagonally dominant）であるとは，各対角ブロック \(A_{ii}\) が正則で，かつ \(\!\;|\!|\!|A_{ii}^{-1}|\!|\!|\;^{-1} \gt R_i\) が各 \(i\) で成り立つことをいう。

このとき (6.1.13) を用いて，そのようなノルムが存在すれば \(A\) は非特異であることを示せ。

(e) \(m=1\) の場合，ブロック厳密対角優位とは何に相当するかを述べよ。

この場合 (6.1.13) と (6.1.2) の集合は一致することを示し，そのときの (6.1.13) の導出を詳述して，本文とは異なるゲルシュゴリン定理の証明を得よ。

(f) ここで \( \!\;|\!|\cdot|\!|\! \) を \(M_m\) 上のスペクトルノルム（演算子2-ノルム）とし，各対角ブロック \(A_{ii}\) が正規（normal）で，\(\sigma(A_{ii})=\{\lambda^{(i)}_1,\dots,\lambda^{(i)}_m\}\) を固有値集合とする。このとき包含集合 (6.1.13) は次の円の和集合に表せることを示せ：

\bigcup_{i=1}^n \bigcup_{j=1}^m \left\{\, z\in\mathbb{C} : |z - \lambda^{(i)}_j| \le \sum_{k\ne i} \!\;|\!|\!| A_{ik} |\!|\!|_2 \,\right\}

これを (6.1.14) として示せ。\(m=1\) のときはこの集合が通常のゲルシュゴリン円板集合に対応する。

(g) 例を示す。

\(m=n=2\) として，次のブロックを取る：

A_{11}=A_{22}=\begin{pmatrix}0 & 1\\ 1 & 0\end{pmatrix}, \\ A_{12}=A_{21}^T=\begin{pmatrix}0 & 0\\ 0.5 & 0\end{pmatrix}

このとき \(A=[A_{ij}]_{i,j=1}^2\) は（ブロック単位で見れば）対角優位であるため非特異だが，通常の要素ごとの対角優位性は満たさない。最大列和ノルム（maximum column-sum norm）を用いてブロック対角優位性を確認せよ。さらに (6.1.2) を用いると，固有値は区間 \([-1.5,\,1.5]\) に含まれる。一方 (6.1.14) を適用すると小さい包含集合 \([-1.5,-0.5]\cup[0.5,1.5]\) を得る。実際の固有値はおよそ \(\pm 1.2808\) と \(\pm 0.7808\) である。

6.1.P18

行列 \(X = [x_1 \dots x_k] \in M_{n,k}\) が列ランク満たしているとする。このとき、非特異な行列 \(R \in M_k\) が存在し、行列 \(Y = [y_{ij}] = [y_1 \dots y_k] = XR\) が次の性質を持つことを示す：k 個の異なるインデックス \(i_1, \dots, i_k \in \{1, \dots, n\}\) が存在し、各 \(j = 1, \dots, k\) について \(y_{i_j j} = \|y_j\|_\infty\) となる。

6.1.P19

行列 \(A = [a_{ij}] \in M_n\) の固有値 \(\lambda\) の幾何学的重複度が \(k \ge 1\) であるとする。このとき、k 個の異なるインデックス \(i_1, \dots, i_k \in \{1, \dots, n\}\) が存在し、各 \(j = 1, \dots, k\) について \(\lambda \in \{ z \in \mathbb{C} : |z - a_{i_j i_j}| \le R_{i_j} \}\) が成り立つことを示す。詳細は以下の通りである：（a）\(X \in M_{n,k}\) の列は \(\lambda\)-固有空間の基底とし、\(Y = [y_1 \dots y_k] = XR\) が前問で述べた性質を満たすようにする。（b）\(AY = \lambda Y\) である。（c）(6.1.1) の証明を再訪し、各固有値対 \(\lambda, y_i\) を用いる。（d）もし \(k = n\) の場合はどうなるか。（e）なぜ \(\lambda \in \cap_{j=1}^k \{ z \in \mathbb{C} : |z - a_{i_j i_j}| \le R_{i_j} \}\) となるか。

6.1.P20

行列 \(A \in M_n\) の固有値 \(\lambda\) の幾何学的重複度が \(k \ge 1\) 以上であるとする。（a）\(\lambda\) は \(A\) の n − k + 1 個の異なるゲルシュゴリン円盤の和集合に含まれることを示す。すなわち、任意のインデックスの選択 \(1 \le i_1 \lt \dots < i_{n-k+1} \le n\) に対して

\lambda \in \bigcup_{j=1}^{n-k+1} \{ z \in \mathbb{C} : |z - a_{i_j i_j}| \le R_{i_j}(A) \}

(b) (6.1.15) で示される円盤の和集合には \(\binom{n}{k-1}\) 通りの異なる可能性がある。なぜ \(\lambda\) がそれらの交わりに含まれるかを説明せよ。（c）\(k = 1\) および \(k = n\) の場合について議論せよ。

6.1.P21

特殊な構造を持つ行列においては、(6.1.10–11) の仮定より弱い条件でも非特異性を保証できる場合がある。循環行列 \(A = [a_{ij}] \in M_n\) の場合、任意の 1 行が対角優勢であれば非特異であることを示せ。すなわち、ある \(i \in \{1, \dots, n\}\) が存在し、\(|a_{ii}| > R_i\) が成り立つ場合である。

注記と参考文献。

6.1.1 のオリジナルの参照文献はゲルシュゴリン, "Über die Abgrenzung der Eigenwerte einer Matrix", Izv. Akad. Nauk. S.S.S.R. 7 (1931) 749–754 である。

6.1.P14 はゲルシュゴリンの論文から引用している。ゲルシュゴリンの定理の歴史的観点については O. Taussky, "A recurring theorem on determinants", Amer. Math. Monthly 61 (1949) 672–676 を参照せよ。

ゲルシュゴリンの定理の一般化の解説は R. A. Brualdi and S. Mellendorf, "Sets in the complex plane containing the eigenvalues of a matrix", Amer. Math. Monthly 101 (1994) 975–985 にある。(6.1.10a) の定性的主張には定量的バージョンがあり、行列 \(A\) の最小特異値は \(\min_{1\le i \le n} \{|a_{ii}| - \frac{1}{2} (R_i + C_i)\}\) により下から抑えられる（Horn and Johnson, 1991, (3.7.17) 参照）。

R. Varga の書籍 Varga (2004) にはゲルシュゴリン円盤、その歴史および一般化について詳細に記載されている。

(6.1.12) の集合が節の最後の段落で述べた最適性を持つことの証明は R. Varga, "Minimal Gerschgorin sets", Pacific J. Math. 15 (1965) 719–729 にある。

6.1.P18 および P19 におけるゲルシュゴリン円盤と幾何学的重複度に関する結果は F. J. Hall および R. Marsli によるものである。