【お知らせ】プログラミング記事の投稿はQiitaに移行しました。

冪零行列を使って冪乗を求める

正則行列を非正則行列と冪零行列の和に分割して冪乗を求めます。

【注意】結果はあまり簡単ではなく、実用性には期待しないでください。

シリーズの記事です。

  1. 行列の分割とケイリー・ハミルトンの定理
  2. 冪零行列を使って冪乗を求める ← この記事
  3. 四元の半群

前回の記事で試行錯誤した方法のうち、冪零行列を使う方法が使えそうだったので今回の記事を書きました。

以下の記事を書いている際に思い付いたことが発端です。

目次

概要

二次正方行列でケイリー・ハミルトンの定理を使って行列の冪乗を下げるには、正則行列では2乗の形を作る必要があります。

例えば4乗を計算する際、2乗が2回表れます。

\begin{aligned} A&=\begin{pmatrix}a&b\\c&d\end{pmatrix} \\ \operatorname{tr}(A)&=a+d \\ \operatorname{det}(A)&=ad-bc \end{aligned}
\begin{aligned} A^4 &=(\underbrace{A^2}_{\text{1回目}})^2 \\ &=(\operatorname{tr}(A)A-\operatorname{det}(A)I)^2 \\ &=\operatorname{tr}(A)^2 \underbrace{A^2}_{\text{2回目}} -2\operatorname{tr}(A)\operatorname{det}(A)A +\operatorname{det}(A)^2I \\ &=\operatorname{tr}(A)^2 (\operatorname{tr}(A)A-\operatorname{det}(A)I) -2\operatorname{tr}(A)\operatorname{det}(A)A +\operatorname{det}(A)^2I \\ &=(\operatorname{tr}(A)^3-2\operatorname{tr}(A)\operatorname{det}(A))A -(\operatorname{tr}(A)^2\operatorname{det}(A)-\operatorname{det}(A)^2)I \end{aligned}

一方、非正則行列では任意の冪乗が簡単に計算できます。

A^n=\operatorname{tr}(A)^{n-1}A\quad(n≧1,\ \operatorname{det}(A)=0)

正則行列を非正則行列の和に分割して計算を試みます。

行列の分割

行列 $A$ を非正則行列 $B$ と 冪零行列 $C$ の和に分割します。

A=\begin{pmatrix}a&b\\c&d\end{pmatrix} ,\ B=\begin{pmatrix}a&b\\c'&d\end{pmatrix} ,\ C=\begin{pmatrix}0&0\\c''&0\end{pmatrix}
A=B+C

$B$ と $C$ やその積は次のように計算します。

b=\operatorname{tr}(B),\ c=\operatorname{tr}(BC)=\operatorname{tr}(CB) \\ B^2=bB,\ C^2=0, \ BCB=cB,\ CBC=cC

次の関係が成り立ちます。

B^n=b^{n-1}B,\ C^n=0, \ (BC)^n=c^{n-1}BC,\ (CB)^n=c^{n-1}CB\quad(n≧2)

例として4乗を計算します。交換則が成り立たない($BC≠CB$)ため、二項展開ではなく全ての組み合わせを列挙します。

\begin{aligned} A^4 &=(B+C)^4 \\ &=\underbrace{BBBB}_{b^3B}+\underbrace{BBBC}_{b^2BC}+\underbrace{BBCB}_{bcB}+\underbrace{BBCC}_0 \\ &\ +\underbrace{BCBB}_{bcB}+\underbrace{BCBC}_{cBC}+\underbrace{BCCB}_0+\underbrace{BCCC}_0 \\ &\ +\underbrace{CBBB}_{b^2CB}+\underbrace{CBBC}_{bcC}+\underbrace{CBCB}_{cCB}+\underbrace{CBCC}_0 \\ &\ +\underbrace{CCBB}_0+\underbrace{CCBC}_0+\underbrace{CCCB}_0+\underbrace{CCCC}_0 \\ &=b^3B+b^2BC+bcB+bcB+cBC+b^2CB+bcC+cCB \\ &=(b^3+2bc)B+bcC+(b^2+c)BC+(b^2+c)CB \end{aligned}

4項が残りました。もっと高次の冪乗でも最終的に残るのはこの4項です。これが多いか少ないかは微妙な所ですが、いきなり冪乗が展開できるのが特徴です。

漸化式

すべての組み合わせを計算するのは大変です。詳細は次回の記事に譲りますが、係数の関係から漸化式が立てられます。

\begin{aligned} a_{1,0}&=0,&a_{1,1}&=1,&a_{1,n}&=a_{1,n-2}c+a_{1,n-1}b \\ &&a_{2,1}&=1,&a_{2,n}&=a_{1,n-2}c \\ &&&&a_{3,n}&=a_{1,n-1} \\ &&&&a_{4,n}&=a_{1,n-1} \end{aligned}

$a_1,a_2,a_3,a_4$ は $B,C,BC,CB$ の係数を表し、コンマ付きの添え字は冪乗の世代を表します。$a_3=a_4$ より $BC+CB$ としてまとめられ、項が3つに減ります。

これにより係数がフィボナッチ数列のように計算できます。5乗までを展開してみます。

\begin{aligned} (B+C)^2&=bB+BC+CB \\ (B+C)^3&=(b^2+c)B+cC+b(BC+CB) \\ (B+C)^4&=(b^3+2bc)B+bcC+(b^2+c)(BC+CB) \\ (B+C)^5&=(b^4+3b^2c+c^2)B+(b^2c+c^2)C+(b^3+2bc)(BC+CB) \end{aligned}

漸化式を使うと順番に計算するしかなく、いきなり冪乗が展開できる特徴が失われます。また、ケイリー・ハミルトンの定理でも漸化式を使う方法があり、それに比べて特に有利な点はありません。

具体例

具体例を示します。

\begin{aligned} A&=\begin{pmatrix}1&2\\3&4\end{pmatrix} \\ B&=\begin{pmatrix}1&2\\2&4\end{pmatrix} \\ C&=\begin{pmatrix}0&0\\1&0\end{pmatrix} \\ BC+CB&=\begin{pmatrix}2&0\\4&0\end{pmatrix}+\begin{pmatrix}0&0\\1&2\end{pmatrix}=\begin{pmatrix}2&0\\5&2\end{pmatrix} \\ b&=\operatorname{tr}(B)=5 \\ c&=\operatorname{tr}(BC)=2 \\ A^4 &=(B+C)^4 \\ &=(b^3+2bc)B+bcC+(b^2+c)(BC+CB) \\ &=(5^3+2×5×2)B+5×2C+(5^2+2)(BC+CB) \\ &=145\begin{pmatrix}1&2\\2&4\end{pmatrix} +10\begin{pmatrix}0&0\\1&0\end{pmatrix} +27\begin{pmatrix}2&0\\5&2\end{pmatrix} \\ &=\begin{pmatrix}145+54&290\\290+10+135&580+54\end{pmatrix} \\ &=\begin{pmatrix}199&290\\435&634\end{pmatrix} \end{aligned}

既に $(B+C) ^ 4$ を展開した式に当てはめているので、それほど難しくはありません。ただ、任意の冪乗をその都度計算するのはなかなか大変です。

生成コード

組み合わせは Python で列挙しました。

>>> f=lambda x,y:("0"*y+bin(x)[2:])[-y:].replace("0","B").replace("1","C")
>>> g=lambda n:[f(i,n) for i in range(0,2**n)]
>>> str.join("+",g(4))
'BBBB+BBBC+BBCB+BBCC+BCBB+BCBC+BCCB+BCCC+CBBB+CBBC+CBCB+CBCC+CCBB+CCBC+CCCB+CCCC'

もうちょっと頑張って4項にまとめて係数を計算する所までできれば良かったのですが、今回はそこまではやっていません。