行列の n 乗の求め方｜対角化・ケイリー・ハミルトン・ジョルダン標準形

$A$ を n 回掛ける計算は、n が大きくなるとすぐに手に負えなくなります。 $100$ 乗を定義どおりに求めれば、 $99$ 回の行列の積が必要です。

行列の構造を先に調べておけば、この作業は固有値を n 乗するだけの計算に化けます。対角化できる行列なら、次の式で終わりです。

$A^{n} = P D^{n} P^{- 1}$

対角化できない行列にも道はあります。ジョルダン標準形に直すか、固有多項式で割った余りを使えば、n がどれだけ大きくても項の数は増えません。

HTML

CSS

JavaScript

<svg viewBox="0 0 460 230" width="100%" style="max-width:460px;display:block;margin:0 auto">
	<text x="230" y="22" font-size="11" fill="#9a9a9a" text-anchor="middle">遠回りに見える下の道のほうが、計算はずっと軽くなります</text>
	<rect x="80" y="60" width="54" height="30" fill="none" stroke="#c8c8c8" stroke-width="1"></rect>
	<text x="107" y="80" font-size="13" fill="#1f1f1f" text-anchor="middle">A</text>
	<rect x="326" y="60" width="54" height="30" fill="none" stroke="#c8c8c8" stroke-width="1"></rect>
	<text x="353" y="80" font-size="13" fill="#1f1f1f" text-anchor="middle">A<tspan font-size="9" dy="-5">n</tspan></text>
	<rect x="80" y="150" width="54" height="30" fill="#1b81e0" fill-opacity="0.06" stroke="#c8c8c8" stroke-width="1"></rect>
	<text x="107" y="170" font-size="13" fill="#1b81e0" text-anchor="middle">D</text>
	<rect x="326" y="150" width="54" height="30" fill="#1b81e0" fill-opacity="0.06" stroke="#c8c8c8" stroke-width="1"></rect>
	<text x="353" y="170" font-size="13" fill="#1b81e0" text-anchor="middle">D<tspan font-size="9" dy="-5">n</tspan></text>
	<line x1="140" y1="75" x2="318" y2="75" stroke="#9a9a9a" stroke-width="1"></line>
	<polygon points="322,75 313,71 313,79" fill="#9a9a9a"></polygon>
	<text x="229" y="68" font-size="11" fill="#9a9a9a" text-anchor="middle">n - 1 回の積</text>
	<line x1="107" y1="96" x2="107" y2="144" stroke="#1b81e0" stroke-width="1"></line>
	<polygon points="107,148 103,139 111,139" fill="#1b81e0"></polygon>
	<text x="114" y="124" font-size="11" fill="#1b81e0">P<tspan font-size="8" dy="-4">-1</tspan></text>
	<line x1="140" y1="165" x2="318" y2="165" stroke="#1b81e0" stroke-width="1"></line>
	<polygon points="322,165 313,161 313,169" fill="#1b81e0"></polygon>
	<text x="229" y="158" font-size="11" fill="#1b81e0" text-anchor="middle">対角成分を n 乗するだけ</text>
	<line x1="353" y1="144" x2="353" y2="96" stroke="#1b81e0" stroke-width="1"></line>
	<polygon points="353,92 349,101 357,101" fill="#1b81e0"></polygon>
	<text x="360" y="124" font-size="11" fill="#1b81e0">P</text>
	<text x="230" y="212" font-size="11" fill="#9a9a9a" text-anchor="middle">どちらの道をたどっても、同じ行列に着きます</text>
</svg>

対角化できるときは固有値を n 乗するだけ

$A = P D P^{- 1}$ と書けたとします。 $A^{2} = P D P^{- 1} P D P^{- 1}$ の中央で $P^{- 1} P$ が消えるので、 $A^{2} = P D^{2} P^{- 1}$ になります。

同じ打ち消しが何度でも起きます。だから $A^{n} = P D^{n} P^{- 1}$ が成り立ち、 $D^{n}$ は対角成分をそれぞれ n 乗するだけで求まります。

$P$ の列は固有ベクトル、 $D$ の対角成分は対応する固有値です。指数が変わっても $P$ は変わらないので、一度求めれば $n = 5$ でも $n = 1 0^{9}$ でも同じものを使えます。

例：対称行列を対角化して n 乗する

次の行列を考えます。

$A = (3113)$

固有値は $4$ と $2$ 、固有ベクトルは $(1, 1)$ と $(1, - 1)$ です。これを列に並べたものが $P$ になります。

$P = (11 1 - 1), P^{- 1} = \frac{1}{2} (11 1 - 1)$

$P D^{n} P^{- 1}$ を計算すると、成分は $2$ つの固有値の n 乗の和と差だけで書けます。

$A^{n} = \frac{1}{2} (4^{n} + 2^{n} 4^{n} - 2^{n} 4^{n} - 2^{n} 4^{n} + 2^{n})$

$n = 3$ を入れると $(36, 28; 28, 36)$ です。 $A$ を 3 回掛けた結果と一致します。

ケイリー・ハミルトンで次数を落とす

固有多項式を $φ$ とすると $φ (A) = O$ が成り立ちます。 $x^{n}$ を $φ (x)$ で割った余りを $r (x)$ とすれば、割り算の商の部分がまるごと消えて $A^{n} = r (A)$ が残ります。

$k$ 次の行列なら、余りは $k - 1$ 次以下です。つまり n がどれだけ大きくても、 $A^{n}$ は $I$ から $A^{k - 1}$ までの一次結合に収まります。

係数を求めるのに割り算そのものを実行する必要はありません。固有値を代入すれば $r (λ) = λ^{n}$ という等式が立ち、これを固有値の個数だけ集めれば連立方程式になります。固有値が重なっているときは、微分した式も足して本数をそろえます。

例：余りの多項式から n 乗を書く

固有値が離れた行列で試します。

$A = (1322)$

固有多項式は $x^{2} - 3 x - 4$ で、固有値は $4$ と $- 1$ です。余りを $r (x) = α x + β$ と置き、 $r (4) = 4^{n}$ と $r (- 1) = (- 1)^{n}$ を連立させます。

$α β = \frac{4 ^{n} - ( - 1 ) ^{n}}{5} = \frac{4 ^{n} + 4 ( - 1 ) ^{n}}{5}$

$n = 3$ なら $α = 13$ 、 $β = 12$ です。 $13 A + 12 I$ を計算すると $(25, 26; 39, 38)$ となり、 $A^{3}$ に一致します。

対角化を経由していない点が、この方法の強みです。固有ベクトルを求めなくても、固有値さえ分かれば n 乗が書けます。

対角化できないときはジョルダン標準形

固有ベクトルの本数が足りない行列は、どう基底を選んでも対角にはなりません。それでも $A = P J P^{- 1}$ の形までは必ず持ち込めるので、 $A^{n} = P J^{n} P^{- 1}$ が使えます。

あとはジョルダン細胞 $J$ の n 乗が分かれば済みます。細胞は $J = λ I + N$ と分けられ、 $N$ は対角のすぐ上だけが $1$ の行列です。

$N$ はべき乗するたびに $1$ の並びが右上へずれ、細胞の大きさだけ掛けると $O$ になります。 $λ I$ とは可換なので、二項定理をそのまま当てはめられます。

$J^{n} = k = 0 \sum m - 1 (k n) λ^{n - k} N^{k}$

$m$ は細胞の大きさです。 $N^{m} = O$ で和が打ち切られるため、n をいくら大きくしても足す項は $m$ 個のままです。

例：3 次のジョルダン細胞の n 乗

固有値 $λ$ の 3 次の細胞を n 乗すると、対角の上に二項係数が並びます。

$J^{n} = λ^{n} 00 n λ^{n - 1} λ^{n} 0 (2 n) λ^{n - 2} n λ^{n - 1} λ^{n}$

$λ = 2$ 、 $n = 4$ で確かめます。 $2^{4} = 16$ 、 $4 \cdot 2^{3} = 32$ 、 $6 \cdot 2^{2} = 24$ が並ぶはずです。

実際に $2$ 回続けて二乗すると $(16, 32, 24; 0, 16, 32; 0, 0, 16)$ が得られ、公式と食い違いません。

対角成分は $λ^{n}$ のままで、上へ行くほど n の多項式が掛かります。 $∣ λ ∣ < 1$ でも n の多項式が一時的に効くのは、この形が理由です。

可換な分解なら二項定理が使える

複素数の範囲で考えれば、どの正方行列も $A = S + N$ と分けられます。 $S$ は対角化でき、 $N$ はべき零で、しかも $S N = N S$ を満たすように取れます。ジョルダン・シュヴァレー分解、フランスではダンフォール分解と呼ばれる分け方です。

この分解が便利なのは、可換だからです。 $(S + N)^{n}$ に二項定理が使え、 $N$ のべき零性が和を有限で止めてくれます。

可換でなければ話は変わります。 $(S + N)^{2} = S^{2} + S N + N S + N^{2}$ の中央 $2$ 項は、順序が入れ替えられないかぎり $2 S N$ にまとまりません。

特別な形は計算せずに分かる

分解を持ち出すまでもない行列もあります。射影行列のようにべき等な行列は $A^{2} = A$ を満たすので、 $A^{n} = A$ が n に依らず成り立ちます。

対合、つまり $A^{2} = I$ を満たす行列なら、偶数乗が $I$ 、奇数乗が $A$ と交互に現れます。鏡映がその例です。回転行列は $R (θ)^{n} = R (n θ)$ で、角を n 倍するだけで済みます。

階数が $1$ の行列も簡単です。 $A = u v^{⊤}$ と書ければ、 $v^{⊤} u$ というスカラーが繰り返し出てくるので $A^{n} = (v^{⊤} u)^{n - 1} A$ となります。

例：階数 1 の行列の n 乗

成分がすべて $1$ の 3 次行列を $J$ とします。これは $u = v = (1, 1, 1)^{⊤}$ として $J = u v^{⊤}$ と書けます。

$v^{⊤} u = 3$ なので、n 乗は $J^{n} = 3^{n - 1} J$ です。 $J^{2}$ の各成分が $3$ になることを確かめれば、あとは同じ倍率が掛かり続けます。

固有値の言葉でも読めます。 $J$ の固有値は $3$ と $0$ （重複 $2$ ）で、生き残るのは $3^{n}$ の分だけです。

例：隣接行列の n 乗が経路の数を数える

グラフの隣接行列 $A$ について、 $A^{n}$ の $(i, j)$ 成分は $i$ から $j$ へ n 歩で行く道順の数になります。同じ頂点を何度通ってもかまいません。積の定義が、途中の頂点をすべて足し上げる形になっているからです。

三角形、つまり 3 頂点の完全グラフで見ます。隣接行列は $A = J - I$ で、 $J$ と $I$ は可換ですから二項定理が使えます。

$J^{k} = 3^{k - 1} J$ を代入して整理すると、次の形にまとまります。

$A^{n} = (- 1)^{n} I + \frac{2 ^{n} - ( - 1 ) ^{n}}{3} J$

$n = 3$ なら $A^{3} = - I + 3 J$ で、対角成分は $2$ 、それ以外は $3$ です。ある頂点から自分へ 3 歩で戻る道は右回りと左回りの $2$ 通り、隣の頂点へ着く道は $3$ 通りあります。

数え上げの答えが行列の計算から出てくるところが、この応用のおもしろさです。

繰り返し二乗法で積の回数を減らす

固有値が汚い、あるいは数値計算で固有ベクトルを信用したくない場面もあります。そのときは指数のほうを分解します。

$A^{2 k} = (A^{k})^{2}$ を使うと、二乗を繰り返すだけで指数が倍々に増えます。n を $2$ 進法で書き、 $1$ が立っている位の分だけ掛け合わせれば $A^{n}$ が得られます。

必要な積の回数は $O (lo g n)$ です。素朴な方法の $n - 1$ 回とは、n が大きいほど差が開きます。

例：13 乗を 5 回の積で作る

$13$ を $2$ 進法で書くと $1101$ 、つまり $13 = 8 + 4 + 1$ です。

まず二乗を 3 回繰り返して $A^{2}$ 、 $A^{4}$ 、 $A^{8}$ を作ります。次に $A^{8}$ と $A^{4}$ と $A$ を掛け合わせれば、積は $2$ 回で足ります。

合計 5 回です。定義どおりなら 12 回なので、半分以下に減りました。 $n = 1 0^{9}$ でも $41$ 回で届きます。

HTML

CSS

JavaScript

<svg viewBox="0 0 460 200" width="100%" style="max-width:460px;display:block;margin:0 auto">
	<text x="230" y="22" font-size="11" fill="#9a9a9a" text-anchor="middle">二乗を積み上げると、指数は倍々に増えていきます</text>
	<rect x="30" y="52" width="54" height="30" fill="#1b81e0" fill-opacity="0.08" stroke="#c8c8c8" stroke-width="1"></rect>
	<text x="57" y="72" font-size="13" fill="#1b81e0" text-anchor="middle">A</text>
	<rect x="140" y="52" width="54" height="30" fill="none" stroke="#c8c8c8" stroke-width="1"></rect>
	<text x="167" y="72" font-size="13" fill="#9a9a9a" text-anchor="middle">A<tspan font-size="9" dy="-5">2</tspan></text>
	<rect x="250" y="52" width="54" height="30" fill="#1b81e0" fill-opacity="0.08" stroke="#c8c8c8" stroke-width="1"></rect>
	<text x="277" y="72" font-size="13" fill="#1b81e0" text-anchor="middle">A<tspan font-size="9" dy="-5">4</tspan></text>
	<rect x="360" y="52" width="54" height="30" fill="#1b81e0" fill-opacity="0.08" stroke="#c8c8c8" stroke-width="1"></rect>
	<text x="387" y="72" font-size="13" fill="#1b81e0" text-anchor="middle">A<tspan font-size="9" dy="-5">8</tspan></text>
	<line x1="90" y1="67" x2="132" y2="67" stroke="#9a9a9a" stroke-width="1"></line>
	<polygon points="136,67 127,63 127,71" fill="#9a9a9a"></polygon>
	<text x="111" y="44" font-size="10" fill="#9a9a9a" text-anchor="middle">2 乗</text>
	<line x1="200" y1="67" x2="242" y2="67" stroke="#9a9a9a" stroke-width="1"></line>
	<polygon points="246,67 237,63 237,71" fill="#9a9a9a"></polygon>
	<text x="221" y="44" font-size="10" fill="#9a9a9a" text-anchor="middle">2 乗</text>
	<line x1="310" y1="67" x2="352" y2="67" stroke="#9a9a9a" stroke-width="1"></line>
	<polygon points="356,67 347,63 347,71" fill="#9a9a9a"></polygon>
	<text x="331" y="44" font-size="10" fill="#9a9a9a" text-anchor="middle">2 乗</text>
	<text x="230" y="120" font-size="12" fill="#1f1f1f" text-anchor="middle">13 = 8 + 4 + 1</text>
	<text x="140" y="148" font-size="13" fill="#1b81e0">A<tspan font-size="9" dy="-5">8</tspan></text>
	<text x="186" y="148" font-size="13" fill="#1b81e0">A<tspan font-size="9" dy="-5">4</tspan></text>
	<text x="232" y="148" font-size="13" fill="#1b81e0">A</text>
	<text x="262" y="148" font-size="13" fill="#9a9a9a">=</text>
	<text x="290" y="148" font-size="13" fill="#1b81e0">A<tspan font-size="9" dy="-5">13</tspan></text>
	<text x="230" y="182" font-size="11" fill="#9a9a9a" text-anchor="middle">色のついた 3 つを掛け合わせます</text>
</svg>

n を大きくしたときのふるまい

固有値の絶対値の最大値をスペクトル半径といい、 $ρ (A)$ と書きます。 $ρ (A) < 1$ なら $A^{n}$ は零行列へ近づき、 $ρ (A) > 1$ なら発散します。

境目の $ρ (A) = 1$ では、細胞の大きさが効いてきます。絶対値 $1$ の固有値がすべて対角化できていれば成分は有界にとどまり、大きさ $2$ 以上の細胞が付いていれば n の多項式の分だけ増えていきます。

各成分の推移確率を並べた確率行列は、必ず固有値 $1$ を持ちます。残りの固有値の絶対値が $1$ より小さければ、 $A^{n}$ は定常状態を表す行列へ落ち着きます。

例：確率行列の n 乗が定常状態へ近づく

列の和が $1$ になる次の行列を考えます。

$A = (0.9 0.1 0.5 0.5)$

トレースが $1.4$ 、行列式が $0.4$ なので、固有値は $1$ と $0.4$ です。対角化して $P D^{n} P^{- 1}$ を計算すると、n 乗は定数の行列と $0. 4^{n}$ の項に分かれます。

$A^{n} = (\frac{5}{6} \frac{1}{6} \frac{5}{6} \frac{1}{6}) + 0. 4^{n} (\frac{1}{6} - \frac{1}{6} - \frac{5}{6} \frac{5}{6})$

$n = 2$ で確かめると $(0.86, 0.70; 0.14, 0.30)$ となり、直接の計算と合います。

第 2 項は $0. 4^{n}$ の速さで消えます。どこから出発しても、比率は $5 : 1$ に落ち着くということです。

他の話題とのつながり

固有多項式で次数を落とす議論そのものは、ケイリー・ハミルトンの定理の記事が詳しく扱っています。証明や逆行列への応用はそちらを参照してください。

ジョルダン標準形の作り方と細胞の並び方はジョルダン標準形の記事、べき零行列の階数の落ち方はべき零行列の記事にあります。対角化できる条件は対角化の記事、相似変換で不変量が保たれる話は相似な行列の記事です。

指数を実数や複素数へ広げると、行列の指数関数につながります。 $e^{A t}$ の計算にも、ここで使った可換な分解がそのまま効いてきます。

よくある誤り

(A + B)^{n}

を二項展開してしまう例が絶えません。

A B = B A

が確かめられないかぎり、この展開は成り立ちません

成分ごとに n 乗するのは別の演算です。それはアダマール積の累乗であって、行列の積の累乗ではありません

対角化できない行列に

P D^{n} P^{- 1}

を当てはめようとしても、そもそも

P

が作れません。固有ベクトルの本数を先に数えてください

ジョルダン細胞の n 乗では、二項係数と一緒に

λ

の指数も下がります。

λ^{n}

を並べただけの形は誤りです

トレースについて

tr (A^{n}) = (tr A)^{n}

とするのは間違いです。正しくは固有値をそれぞれ n 乗して足したものになります

A^{n} = O

になるのはべき零行列に限られます。正則な行列は何乗しても行列式が

0

にならないので、零行列には届きません

スペクトル半径が

1

未満でも、途中で成分が大きく膨らむことがあります。最終的に

0

へ向かうことと、単調に小さくなることは別です

実行列の n 乗を複素固有値で計算しても、答えは実行列です。共役の組が打ち消し合うので、虚部は最後に消えます

参考文献

Matrixpotenz - Wikipedia（ドイツ語）

Jordan normal form - Wikipedia

Exponentiation by squaring - Wikipedia

Matrice diagonalisable - Wikipédia（フランス語）

可对角化矩阵 - 维基百科（中国語）

行列の n 乗は、固有値を n 乗する計算に置き換えられます。対角化して求める方法、固有多項式で割った余りから書く方法、対角化できないときのジョルダン標準形と二項定理、べき等や階数 1 のような特別な形、繰り返し二乗法で積の回数を減らすやり方、n を大きくしたときのふるまいまでを、計算例をつけて解説します。