ジョルダン標準形 アルゴリズム

ウィキペディア

ジョルダン標準形

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2023/07/08 15:16 UTC 版)

アルゴリズム

n次正方行列 A のジョルダン標準形は次のように計算できる。以下では n次単位行列を I で表す。

入力

n次正方行列 A

出力

P⁻¹AP がジョルダン標準形となる n次正則行列 P

アルゴリズム

1. 行列 A の相異なる固有値 λ₁, …, λ_s を求める
2. A_i = A − λ_i I とおく
3. rank A_i ^k_i = rank A_i ^k_i+1 となる最小の自然数 k_i を求める
4. W_i,j = im A_i ^j ∩ ker A_i とおく
5. 部分空間の増大列 W_i,ki−1 ⊂ … ⊂ W_i,1 ⊂ W_i,0 = ker A_i に沿って ker A_i の基底 b_i,1, …, b_i,ti を求める
6. b_i,j ∈ W_i,di,j − W_i,di,j+1 となる自然数 d_i,j を求める
7. 連立一次方程式 A_i ^d_i,j x_i,j = b_i,j の解 x_i,j を求める
8. e_i,j = A_i ^j x_i,j とおく
9. P_i,j = [e_i,di,j, …, e_i,1, e_i,0] とおく
10. P = [P_1,1, …, P_1,t1, …, P_s,1, …, P_s,ts] を出力

標準形の存在証明

定理

任意の線形変換 f に対しジョルダン基底は存在する。

証明は線形空間の次元 $n=\dim V$ についての帰納法で、n = 1 なら全ての基底がジョルダン基底だからOK、n − 1 までOKとして、$n=\dim V$ とする。次の明らかな補題が証明の鍵である。

補題

$\{e_{i,j}\}$ が f のジョルダン基底なら、$f-\lambda 1_{V}$ のジョルダン基底でもある。ここで λ はスカラー。

この補題により $\operatorname {rank} f=r<n$ の場合に示せばよい。このとき $V'=\operatorname {im} f,\ f'=f|_{V'}$ とすると、帰納法の仮定で、f' のジョルダン基底 $\{e_{ij}\}$ が取れる。番号を $\lambda _{1}=\lambda _{2}=\dotsb =\lambda _{s}=0$、i > s なら λ_i ≠ 0 となるようにとる。$e_{1,1},e_{2,1},\dotsc ,e_{s,1}$ は $\ker f$ の元で線形独立だから、これらに $b_{1},b_{2},\dotsc ,b_{n-r-s}$ を加えて $\ker f$ の基底を作る。また V の元 $c_{1},c_{2},\dotsc ,c_{s}$ を $f(c_{i})=e_{i,n_{i}}$ となるようにとる。このとき n 個のベクトル $\{e_{i,j}\}\cup \{b_{i}\}\cup \{c_{i}\}$ が線形独立であることは容易に分かり、これらは V の基底である。$c_{i}=e_{i,n_{i}+1},\ b_{i}=e_{k+i,1}$ と番号づけると、これが f のジョルダン基底となる。[証明終わり]

$V=K^{n}$ で f が行列 $A=(a_{1},a_{2},\dotsc ,a_{n})$ で表されるとき、 $\operatorname {rank} A=r$ なら、$a_{1},a_{2},\dotsc ,a_{r}$ が線形独立としてよい。このとき $A={\begin{bmatrix}A_{1,1}&A_{1,2}\\A_{2,1}&A_{2,2}\end{bmatrix}}$ は行変形で ${\begin{bmatrix}E_{r}&R\\0&0\end{bmatrix}}$ と簡約化される。

命題

上のとき、$a_{1},a_{2},\dotsc ,a_{r}$ は V' の基底であるが、この基底に関する f' の表現行列は $A_{1,1}+RA_{2,1}$ である。

命題の証明は略するが、これを用いると上のジョルダン基底の存在証明は、同時に行列のジョルダン標準形と変換行列を求めるアルゴリズムにもなっている。