行列の冪乗 - crypto-writeup-public

特に正方行列 $A$ に対して $A^n$ を求める計算。

[** $A$ が対角化可能な場合]

$A$ を対角化して対角行列 $D = P^{-1}AP$ を求める

対角行列 $D$ のn乗は対角成分をそれぞれn乗していくだけなので簡単。両辺 $n$ 乗すると

$D^n = (P^{-1}AP)^n = P^{-1}AP \cdot P^{-1}AP \cdot \dots \cdot P^{-1}AP$

$= P^{-1}A^nP$

したがって、 $A^n = PD^nP^{-1}$

[** $A$ が対角化不可能な場合]

$A$ は対角化不可能な場合もある。この場合はジョルダン標準形を求める。やることは大体対角化と同じで、

$J = P^{-1}AP$

となるようにジョルダン標準形 $J$ と $P, P^{-1}$ を求めて、それぞれn乗すると

$J^n = P^{-1}A^nP$

となるので

$A^n = PJ^nP^{-1}$

違うのは対角行列ではなくジョルダン標準形に対してn乗の演算を行うことになる点で、これは次のような上三角行列になる

$\begin{pmatrix} \lambda^{n} & \binom{n}{1}\lambda^{n-1} & \binom{n}{2}\lambda^{n-2} & \cdots & \binom{n}{n}\lambda^0 \ & \lambda^{n} & \binom{n}{1}\lambda^{n-1} \ & & \ddots & \ddots & \ & & & & \lambda^{n} \end{pmatrix}$