行列の(シューア)三角化　左下半分を０にする【線形代数】

対角化は便利ですが，いつでもできるとは限りません．

一方で三角化であればどんな正方行列でもいつでもできます．

もっというといつでもユニタリ行列で三角化できます

今回はそのことを証明したいと思います．

1. 上三角行列

まず行列の三角化の目標となる上三角行列とはどんな行列かというと，

こんな感じです．

それではこの形に持っていくお作法を書いていきたいと思います．

2. 行列の三角化

それでは三角化していきたいと思います．

まず目標を確認するために定理の形で三角化を見直しておきます．

それでは証明します．

行列の大きさ\(n\)についての帰納法を用います

\(n = 1\)のケースを示す

まず\(n = 1\)のケースですが，これは\(M = (M_{11})\)という状況ですから，\(i > j\)をみたす\(M_{ij}\)がありません．ということで常に上三角行列になっているのでOKです．

\(n = k\)で成り立つことを仮定して\(n = k+1\)でも成り立つことを示す

あとは\(k \times k\)行列が上三角化できるときに，\((k+1)\times (k+1)\)行列も上三角化できることを示せばよいです．

\((k+1)\times (k+1)\)行列\(M\)の固有値と固有ベクトルを１ペア考えます．それを\(\alpha,\ u\)とします．つまり\[Mu = \alpha u\]です．

ではこの固有ベクトル\(u\)と線形独立なベクトルを\(k\)本集めます．それを\(v_1,\cdots,v_k\)としましょう．これらを並べた行列

\[Q = (u, v_1, \cdots, v_k)\]

は正則ですので，逆行列を持ちます．そこでこの行列\(Q\)で\(M\)を変換した行列を\(A=Q^{-1}MQ\)とおきます．\(A\)の第１列を調べてみましょう．\(e_1=(1,0,\cdots,0)^T\)（標準基底）とします．\(Qe_1 = u\)ですから逆に\(e_1 = Q^{-1}u\)でもあることに注意して，

\begin{align*}
A e_1 &= Q^{-1}MQe_1 \\
&= Q^{-1}Mu \\
&= Q^{-1}\alpha u \\
&= \alpha e_1
\end{align*}

となります．

よって\(A\)の第１列は\(\alpha e_1\)となっていることが分かりました．よって

\begin{align*}
A=
\left( \begin{array}{c|ccc} \alpha & & A_{[1, 2:]} & \\
\hline 0 & & & \\
\vdots & & A_{[2:, 2:]} & \\
0 & & & \end{array} \right)
\end{align*}

という形になっています．\(A_{[1, 2:]}\)は\(A\)の１行目の２列目以降の行ベクトル，\(A_{[2:, 2:]}\)は\(A\)の２行目以降２列目以降の行列という意味で用いています．

すると\(A_{[2:, 2:]}\)は\(k \times k\)行列なので帰納法の仮定が使えて，上三角化できます．変換に使う行列は\(\tilde{R}\)と名付けることにして，\(\tilde{R}^{-1} A_{[2:, 2:]} \tilde{R}\)は上三角です．では

\begin{align*}
R=
\left( \begin{array}{c|ccc} 1 & 0 & \dots & 0 \\
\hline 0 & & & \\
\vdots & & \tilde{R} & \\
0 & & & \end{array} \right)
\end{align*}

として，\(P = QR\)としましょう．\(Q\)も\(R\)も正則行列ですから，\(P\)も正則です．この\(P\)が\(M\)を上三角化します．見てみましょう．

\begin{align*}
P^{-1} M P &= R^{-1} A R\\
&= \left( \begin{array}{c|ccc} 1 & 0 & \dots & 0 \\
\hline 0 & & & \\
\vdots & & \tilde{R}^{-1} & \\
0 & & & \end{array} \right)
\left( \begin{array}{c|ccc} \alpha & & A_{[1, 2:]} & \\
\hline 0 & & & \\
\vdots & & A_{[2:, 2:]} & \\
0 & & & \end{array} \right)
\left( \begin{array}{c|ccc} 1 & 0 & \dots & 0 \\
\hline 0 & & & \\
\vdots & & \tilde{R} & \\
0 & & & \end{array} \right) \\
&= \left( \begin{array}{c|ccc} \alpha & & A_{[1, 2:]}\tilde{R} & \\
\hline 0 & & & \\
\vdots & & \tilde{R}^{-1} A_{[2:, 2:]} \tilde{R} & \\
0 & & & \end{array} \right)
\end{align*}

よって上三角化できました．

アルゴリズムだけまとめさせていただくと，

3. シューア三角化

間違い探しのようですが，

というのもあります．先ほどとの違いは変換に使う行列の制限をもっと強くして，正則のみならずユニタリまで要求していることです．

証明は全く同じで，さきほどの証明で

\[Q = (u, v_1, \cdots, v_k)\]

という正則な行列をとりましたが，この行列をとるときに，シュミットの直交化の１手間を加えて，\(u, v_1, \cdots, v_k\)がすべて直交するようにとって正規化すればユニタリな行列が作れるのでOKです．

アルゴリズムの中だとステップ2.でベクトルが正規直交するようにとればよいですね．

シューア三角化はそこそこいろいろな場面で見かけますので最後にまとめさせていただくと，