漸化式の行列表示

同義語：matrix form of a linear recurrence

概要

この記事で考えること

高校では、三項間漸化式 $a_{n+2}=pa_{n+1}+qa_n$（$p,q$ は定数、$q\ne0$）を、特性方程式 $t^2=pt+q$ の解 $\alpha,\beta$ を使って解く（三項間漸化式の特性方程式）。

高校の方法の復習

$a_0=0$、$a_1=4$、$a_{n+2}=2a_{n+1}+3a_n$ とする。特性方程式 $t^2=2t+3$ の解は $3,-1$ である。数列 $a_{n+1}+a_n$ は公比 $3$ の等比数列、$a_{n+1}-3a_n$ は公比 $-1$ の等比数列なので
$$ a_{n+1}+a_n=3^n\cdot(4+0)=4\cdot3^n,\qquad a_{n+1}-3a_n=(-1)^n\cdot(4-0)=4\cdot(-1)^n $$
である。上の式から下の式を引くと $4a_n=4\cdot3^n-4\cdot(-1)^n$、すなわち $a_n=3^n-(-1)^n$ を得る（$0,4,8,28,80,\dots$）。

この方法は正しいが、「$t^2=pt+q$ という方程式はどこから来たのか」は説明されていない。この記事の答えは、特性方程式は、ある行列の「固有値」を求める方程式であるというものである。高校の計算と、この記事で扱う大学の概念は次のように対応する。

高校の計算	大学の概念	ボックス
2 項ずつ組にして次へ進む	行列 $C$ を掛ける：$v_{n+1}=Cv_n$	def-mfr-companion
特性方程式 $t^2=pt+q$	固有多項式 $\det(tE-C)=0$	thm-mfr-charpoly
等比数列 $\lambda^n$ が解になる	固有ベクトル $(\lambda,1)^{\top}$	thm-mfr-charpoly
一般項 $A\alpha^n+B\beta^n$	対角化 $C^n=PD^nP^{-1}$	thm-mfr-distinct
$a_{n+1}-\beta a_n$ が等比数列	左固有ベクトルによる成分の取り出し	rem-mfr-left-eigen

行列の計算の準備

現在の高校の課程（平成30年告示の学習指導要領）では、行列は数学Cの「数学的な表現の工夫」（数学Cの 3 つの内容から適宜選んで学ぶものの一つ）で、表や離散グラフのような事象の関係を表す方法として扱われる。漸化式を行列で表すことや固有値は、そこでの内容や例には含まれていない（文部科学省『高等学校学習指導要領（平成30年告示）』p. 102、同『高等学校学習指導要領（平成30年告示）解説数学編理数編』pp. 126–127）。そこで、この記事で使う計算を最初にまとめる。以下、数と言えば複素数とする。

2 次正方行列とベクトルの積

数を 2 行 2 列に並べた $A=\begin{pmatrix}a&b\\c&d\end{pmatrix}$ を 2 次正方行列という。縦に 2 つ並べた $v=\begin{pmatrix}x\\y\end{pmatrix}$（ベクトル）との積と、2 つの 2 次正方行列の積を
$$ Av:=\begin{pmatrix}ax+by\\cx+dy\end{pmatrix},\qquad \begin{pmatrix}a&b\\c&d\end{pmatrix}\begin{pmatrix}a'&b'\\c'&d'\end{pmatrix}:=\begin{pmatrix}aa'+bc'&ab'+bd'\\ca'+dc'&cb'+dd'\end{pmatrix} $$
で定める。$E:=\begin{pmatrix}1&0\\0&1\end{pmatrix}$ を単位行列といい、$A^0:=E$、$A^{n+1}:=A^nA$ で冪 $A^n$ を定める。$\det A:=ad-bc$ を $A$ の行列式、$\operatorname{tr}A:=a+d$ を $A$ の跡という。横に並べた $(x\ \ y)$ と $A$ の積 $(x\ \ y)A:=(xa+yc\ \ \ xb+yd)$ も使う。

積の定義の式を列ごとに見ると、$AB$ の第 1 列は $A$ と「$B$ の第 1 列」の積、$AB$ の第 2 列は $A$ と「$B$ の第 2 列」の積になっている。後で行列 $P$ の列を 1 本ずつ扱うときに、この見方を使う。
行列の積は順序を変えると値が変わることがある。一方、$(AB)C=A(BC)$、$(AB)v=A(Bv)$（結合法則）は、両辺の成分を計算すると一致する（本記事では計算を省く）。$AE=EA=A$、$Ev=v$ である。

行列の積を計算する

$A=\begin{pmatrix}1&2\\3&4\end{pmatrix}$、$B=\begin{pmatrix}0&1\\1&1\end{pmatrix}$、$v=\begin{pmatrix}5\\6\end{pmatrix}$ とする。
$$ Av=\begin{pmatrix}1\cdot5+2\cdot6\\3\cdot5+4\cdot6\end{pmatrix}=\begin{pmatrix}17\\39\end{pmatrix},\qquad AB=\begin{pmatrix}1\cdot0+2\cdot1&1\cdot1+2\cdot1\\3\cdot0+4\cdot1&3\cdot1+4\cdot1\end{pmatrix}=\begin{pmatrix}2&3\\4&7\end{pmatrix}. $$
同様に $BA=\begin{pmatrix}3&4\\4&6\end{pmatrix}$ となり、$AB\ne BA$ である。$AB$ の第 1 列 $\begin{pmatrix}2\\4\end{pmatrix}$ は、$A$ と $B$ の第 1 列 $\begin{pmatrix}0\\1\end{pmatrix}$ の積 $\begin{pmatrix}1\cdot0+2\cdot1\\3\cdot0+4\cdot1\end{pmatrix}$ に等しい。

2 次正方行列の逆行列

$A=\begin{pmatrix}a&b\\c&d\end{pmatrix}$ で $\det A=ad-bc\ne0$ ならば、
$$ A^{-1}:=\frac1{ad-bc}\begin{pmatrix}d&-b\\-c&a\end{pmatrix} $$
は $AA^{-1}=A^{-1}A=E$ を満たす。$A^{-1}$ を $A$ の逆行列という。

掛けて確かめる

定義どおりに掛けると
$$ \begin{pmatrix}a&b\\c&d\end{pmatrix}\begin{pmatrix}d&-b\\-c&a\end{pmatrix}=\begin{pmatrix}ad-bc&-ab+ba\\cd-dc&-cb+da\end{pmatrix}=\begin{pmatrix}ad-bc&0\\0&ad-bc\end{pmatrix} $$
であり、両辺を $ad-bc$ で割ると $AA^{-1}=E$ を得る。掛ける順を逆にしても、同じ計算で $\begin{pmatrix}da-bc&db-bd\\-ca+ac&-cb+ad\end{pmatrix}=(ad-bc)E$ となる。$\square$

漸化式を行列で書く

三項間漸化式では、次の項を決めるのに「直前の 2 項」が必要である。そこで、隣り合う 2 項を組にしたベクトル
$$ v_n:=\begin{pmatrix}a_{n+1}\\a_n\end{pmatrix} $$
を考える。$v_n$ から $v_{n+1}$ への移り方は、1 つの行列で書ける。

三項間漸化式のコンパニオン行列

複素数 $p,q$（$q\ne0$）について、漸化式 $a_{n+2}=pa_{n+1}+qa_n$ に対し、2 次正方行列
$$ C:=\begin{pmatrix}p&q\\1&0\end{pmatrix} $$
をこの漸化式のコンパニオン行列（companion matrix、同伴行列）という。

1 行目は漸化式の係数を並べたもの、2 行目は「$a_{n+1}$ を 1 段下へずらす」働きをする。流儀によっては、この行列の転置や行と列の順を逆にしたものをコンパニオン行列と呼ぶ（固有多項式の記事の「多項式の同伴行列」は別の並べ方である）。

漸化式は行列の冪になる

$(a_n)$ が漸化式 $a_{n+2}=pa_{n+1}+qa_n$ の解ならば、すべての $n\ge0$ で $v_{n+1}=Cv_n$ であり、したがって $v_n=C^nv_0$ である。

積の定義と帰納法

積の定義により
$$ Cv_n=\begin{pmatrix}p&q\\1&0\end{pmatrix}\begin{pmatrix}a_{n+1}\\a_n\end{pmatrix}=\begin{pmatrix}pa_{n+1}+qa_n\\a_{n+1}\end{pmatrix}=\begin{pmatrix}a_{n+2}\\a_{n+1}\end{pmatrix}=v_{n+1} $$
である（3 つ目の等号で漸化式を使った）。次に $v_n=C^nv_0$ を数学的帰納法で示す。$n=0$ では $C^0v_0=Ev_0=v_0$ である。$v_n=C^nv_0$ とすると、$v_{n+1}=Cv_n=C(C^nv_0)=(CC^n)v_0$ である。$CC^n=C^{n+1}$ も同じく帰納法で確かめられる（$n=0$ で $CE=C$、$CC^n=C^{n+1}$ ならば $CC^{n+1}=C(C^nC)=(CC^n)C=C^{n+1}C=C^{n+2}$）。$\square$

行列を掛けて項を進める

$a_0=0$、$a_1=4$、$a_{n+2}=2a_{n+1}+3a_n$ のコンパニオン行列は $C=\begin{pmatrix}2&3\\1&0\end{pmatrix}$、$v_0=\begin{pmatrix}4\\0\end{pmatrix}$ である。
$$ v_1=Cv_0=\begin{pmatrix}2\cdot4+3\cdot0\\4\end{pmatrix}=\begin{pmatrix}8\\4\end{pmatrix},\qquad v_2=Cv_1=\begin{pmatrix}2\cdot8+3\cdot4\\8\end{pmatrix}=\begin{pmatrix}28\\8\end{pmatrix},\qquad v_3=Cv_2=\begin{pmatrix}80\\28\end{pmatrix}. $$
下の成分が $a_1,a_2,a_3$、上の成分が $a_2,a_3,a_4$ である。一般項を求めることは、$C^n$ を求めることと同じになった。

確率の漸化式を推移行列の冪で書く同じ見方は確率漸化式と定常分布で扱う。

固有値と固有ベクトル

$C^n$ を求めるには、$C$ を掛けても同じ直線の上にとどまる（定数倍になる）ベクトルを探すのがよい。そういうベクトルなら、何回掛けても定数倍されるだけだからである。倍率は負でもよく（そのときは向きが反対になる）、虚数でもよい。

2 次正方行列の固有値と固有多項式

$A$ を 2 次正方行列とする。数 $\lambda$ と、$\mathbf 0$ でないベクトル $v$ が $Av=\lambda v$ を満たすとき、$\lambda$ を $A$ の固有値、$v$ を固有値 $\lambda$ に属する固有ベクトルという。$t$ の 2 次式
$$ \chi_A(t):=\det(tE-A)=(t-a)(t-d)-bc=t^2-(\operatorname{tr}A)\,t+\det A $$
を $A$ の固有多項式（特性多項式）という。ここで $A=\begin{pmatrix}a&b\\c&d\end{pmatrix}$、$tE-A=\begin{pmatrix}t-a&-b\\-c&t-d\end{pmatrix}$ である。

固有値を求める（1）[ex-mfr-eigen-sym]

$S=\begin{pmatrix}2&1\\1&2\end{pmatrix}$ の固有多項式は $\chi_S(t)=t^2-4t+3=(t-1)(t-3)$ である。実際
$$ S\begin{pmatrix}1\\1\end{pmatrix}=\begin{pmatrix}3\\3\end{pmatrix}=3\begin{pmatrix}1\\1\end{pmatrix},\qquad S\begin{pmatrix}1\\-1\end{pmatrix}=\begin{pmatrix}1\\-1\end{pmatrix}=1\cdot\begin{pmatrix}1\\-1\end{pmatrix} $$
なので、$3$ と $1$ は固有値で、$\begin{pmatrix}1\\1\end{pmatrix}$、$\begin{pmatrix}1\\-1\end{pmatrix}$ はそれぞれに属する固有ベクトルである。

固有値を求める（2）：虚数の固有値

$R=\begin{pmatrix}0&-1\\1&0\end{pmatrix}$ は平面のベクトルを $90^\circ$ 回転させる行列である（$R\begin{pmatrix}x\\y\end{pmatrix}=\begin{pmatrix}-y\\x\end{pmatrix}$）。$\mathbf 0$ でないベクトルを $90^\circ$ 回すと元の直線から必ず外れるので、実数の範囲には固有ベクトルがない。固有多項式は $\chi_R(t)=t^2+1$ で、解は $\pm i$ である。複素数の範囲では
$$ R\begin{pmatrix}1\\-i\end{pmatrix}=\begin{pmatrix}i\\1\end{pmatrix}=i\begin{pmatrix}1\\-i\end{pmatrix} $$
となり、$i$ は固有値である。

2 つの例で、固有値は固有多項式の根になっていた。これは一般に成り立つ。

固有値は固有多項式の根

数 $\lambda$ が 2 次正方行列 $A$ の固有値であることと、$\chi_A(\lambda)=0$ であることは同値である。

行列式が 0 かどうかで分ける

$M:=\lambda E-A=\begin{pmatrix}m_{11}&m_{12}\\m_{21}&m_{22}\end{pmatrix}$ とおくと $\det M=\chi_A(\lambda)$ である。$Av=\lambda v$ は $\lambda v-Av=\mathbf 0$、すなわち $Mv=\mathbf 0$ と同じなので、「$\lambda$ が固有値」は「$Mv=\mathbf 0$ となる $v\ne\mathbf 0$ がある」と同じである。
段 1（$\det M\ne0$ なら固有値でない）：prop-mfr-inverse により $M^{-1}$ がある。$Mv=\mathbf 0$ の両辺に左から $M^{-1}$ を掛けると $v=M^{-1}\mathbf 0=\mathbf 0$ となるので、$v\ne\mathbf 0$ は見つからない。
段 2（$\det M=0$ なら固有値）：2 つのベクトル $u:=\begin{pmatrix}m_{12}\\-m_{11}\end{pmatrix}$、$w:=\begin{pmatrix}m_{22}\\-m_{21}\end{pmatrix}$ を考える。成分を計算すると
$$ Mu=\begin{pmatrix}m_{11}m_{12}-m_{12}m_{11}\\m_{21}m_{12}-m_{22}m_{11}\end{pmatrix}=\begin{pmatrix}0\\-\det M\end{pmatrix}=\mathbf 0,\qquad Mw=\begin{pmatrix}m_{11}m_{22}-m_{12}m_{21}\\m_{21}m_{22}-m_{22}m_{21}\end{pmatrix}=\begin{pmatrix}\det M\\0\end{pmatrix}=\mathbf 0 $$
である。$u,w$ のどちらかが $\mathbf 0$ でなければ、それが求める $v$ である。どちらも $\mathbf 0$ なら $M$ の 4 つの成分がすべて $0$ なので、どんな $v\ne\mathbf 0$ でも $Mv=\mathbf 0$ となる。$\square$

主定理 1：特性方程式は固有多項式である

特性方程式とコンパニオン行列の固有多項式

漸化式 $a_{n+2}=pa_{n+1}+qa_n$ のコンパニオン行列 $C$ について、
$$ \chi_C(t)=t^2-pt-q $$
である。したがって特性方程式 $t^2=pt+q$ の解は $C$ の固有値にほかならない。さらに、$\lambda$ が特性方程式の解ならば、$\begin{pmatrix}\lambda\\1\end{pmatrix}$ は固有値 $\lambda$ に属する固有ベクトルである。

跡と行列式を計算する

段 1：$C=\begin{pmatrix}p&q\\1&0\end{pmatrix}$ なので $\operatorname{tr}C=p+0=p$、$\det C=p\cdot0-q\cdot1=-q$ である。def-mfr-eigen の式に入れて $\chi_C(t)=t^2-pt+(-q)=t^2-pt-q$ を得る。lem-mfr-eigen-root により、固有値は $\chi_C(t)=0$ の解、すなわち特性方程式の解である。
段 2：$\lambda^2=p\lambda+q$ とする。積の定義により
$$ C\begin{pmatrix}\lambda\\1\end{pmatrix}=\begin{pmatrix}p\lambda+q\cdot1\\\lambda\end{pmatrix}=\begin{pmatrix}\lambda^2\\\lambda\end{pmatrix}=\lambda\begin{pmatrix}\lambda\\1\end{pmatrix} $$
である（2 つ目の等号で $p\lambda+q=\lambda^2$ を使った）。$\begin{pmatrix}\lambda\\1\end{pmatrix}$ は下の成分が $1$ なので $\mathbf 0$ でない。$\square$

コンパニオン行列の固有ベクトル

$C=\begin{pmatrix}2&3\\1&0\end{pmatrix}$（漸化式 $a_{n+2}=2a_{n+1}+3a_n$）では $\chi_C(t)=t^2-2t-3=(t-3)(t+1)$ で、固有値は $3,-1$ である。thm-mfr-charpoly の固有ベクトルは $u=\begin{pmatrix}3\\1\end{pmatrix}$、$w=\begin{pmatrix}-1\\1\end{pmatrix}$ で、
$$ Cu=\begin{pmatrix}2\cdot3+3\cdot1\\3\end{pmatrix}=\begin{pmatrix}9\\3\end{pmatrix}=3u,\qquad Cw=\begin{pmatrix}2\cdot(-1)+3\cdot1\\-1\end{pmatrix}=\begin{pmatrix}1\\-1\end{pmatrix}=-w $$
である。一方 $e=\begin{pmatrix}1\\0\end{pmatrix}$ では $Ce=\begin{pmatrix}2\\1\end{pmatrix}$ となり、$e$ の定数倍でないので、元の直線（$x$ 軸）から外れる。

図1：固有ベクトル u, w は C を掛けても同じ直線の上にとどまるが、固有ベクトルでない e は別の直線に移る
図 1 の左では、$u$ は 3 倍に伸び、$w$ は $-1$ 倍で向きが反対になるが、どちらも元の直線の上にある。右の $e$ は $C$ を掛けると別の直線に移る。

特性方程式の由来

固有ベクトル $\begin{pmatrix}\lambda\\1\end{pmatrix}$ は、等比数列 $a_n=\lambda^n$ の $v_0=\begin{pmatrix}a_1\\a_0\end{pmatrix}$ にあたる。$v_0$ が固有ベクトルなら、$v_n=C^nv_0=\lambda^nv_0$ となって各項が毎回 $\lambda$ 倍される。つまり、特性方程式は「$C$ を掛けても同じ直線の上にとどまる（定数倍になる）ベクトル」を探す方程式である。$q\ne0$ なので $\det C=-q\ne0$ であり、固有値はどれも $0$ でない（$\chi_C(0)=-q\ne0$ なので $0$ は固有多項式の根でない）。

コンパニオン行列の固有ベクトル（2）[ex-mfr-eigvec-2]

漸化式 $a_{n+2}=5a_{n+1}-6a_n$ のコンパニオン行列は $C=\begin{pmatrix}5&-6\\1&0\end{pmatrix}$ で、$\chi_C(t)=t^2-5t+6=(t-2)(t-3)$ である。thm-mfr-charpoly の固有ベクトル $\begin{pmatrix}3\\1\end{pmatrix}$、$\begin{pmatrix}2\\1\end{pmatrix}$ に $C$ を掛けると
$$ C\begin{pmatrix}3\\1\end{pmatrix}=\begin{pmatrix}5\cdot3-6\cdot1\\3\end{pmatrix}=\begin{pmatrix}9\\3\end{pmatrix}=3\begin{pmatrix}3\\1\end{pmatrix},\qquad C\begin{pmatrix}2\\1\end{pmatrix}=\begin{pmatrix}5\cdot2-6\cdot1\\2\end{pmatrix}=\begin{pmatrix}4\\2\end{pmatrix}=2\begin{pmatrix}2\\1\end{pmatrix} $$
となる。等比数列の解 $3^n$、$2^n$ の $v_0=\begin{pmatrix}a_1\\a_0\end{pmatrix}$ が、それぞれ $\begin{pmatrix}3\\1\end{pmatrix}$、$\begin{pmatrix}2\\1\end{pmatrix}$ である。

固有値の和と積がトレースと行列式になることはトレースと固有値で扱う。

主定理 2：異なる 2 解なら対角化できる

固有ベクトルが 2 本とれると、$C^n$ が計算できる。そのために、次の言葉を用意する。

対角化可能と対角化

右上と左下の成分がどちらも $0$ の 2 次正方行列 $\begin{pmatrix}\lambda_1&0\\0&\lambda_2\end{pmatrix}$ を対角行列という。2 次正方行列 $A$ について、逆行列をもつ 2 次正方行列 $P$ と数 $\lambda_1,\lambda_2$ があって
$$ P^{-1}AP=\begin{pmatrix}\lambda_1&0\\0&\lambda_2\end{pmatrix} $$
となるとき、$A$ は対角化可能であるという。このような $P$ と対角行列 $P^{-1}AP$ を求めることを、$A$ の対角化という。

対角化の小さな例

ex-mfr-eigen-sym の $S=\begin{pmatrix}2&1\\1&2\end{pmatrix}$ の固有ベクトル $\begin{pmatrix}1\\1\end{pmatrix}$、$\begin{pmatrix}1\\-1\end{pmatrix}$ を並べて $P=\begin{pmatrix}1&1\\1&-1\end{pmatrix}$ とする。$\det P=-1-1=-2$ なので、prop-mfr-inverse により $P^{-1}=\frac12\begin{pmatrix}1&1\\1&-1\end{pmatrix}$ である。
$$ SP=\begin{pmatrix}3&1\\3&-1\end{pmatrix},\qquad P^{-1}SP=\frac12\begin{pmatrix}1&1\\1&-1\end{pmatrix}\begin{pmatrix}3&1\\3&-1\end{pmatrix}=\frac12\begin{pmatrix}6&0\\0&2\end{pmatrix}=\begin{pmatrix}3&0\\0&1\end{pmatrix} $$
なので、$S$ は対角化可能である。対角成分に固有値 $3,1$ が並ぶ。$SP$ の第 1 列 $\begin{pmatrix}3\\3\end{pmatrix}$ は、固有ベクトル $\begin{pmatrix}1\\1\end{pmatrix}$ の $3$ 倍になっている。

異なる 2 解の場合の対角化と一般項

特性方程式 $t^2=pt+q$（$q\ne0$）が異なる 2 解 $\alpha,\beta$ をもつとする。$P:=\begin{pmatrix}\alpha&\beta\\1&1\end{pmatrix}$、$D:=\begin{pmatrix}\alpha&0\\0&\beta\end{pmatrix}$ とおくと、$P$ は逆行列をもち
$$ P^{-1}CP=D,\qquad C^n=PD^nP^{-1} $$
である（特に $C$ は対角化可能である）。漸化式の解 $(a_n)$ は、すべての $n\ge0$ で
$$ a_n=\frac{(a_1-\beta a_0)\,\alpha^n-(a_1-\alpha a_0)\,\beta^n}{\alpha-\beta} $$
を満たす。

固有ベクトルを並べる

方針：固有ベクトルを 2 本並べた行列 $P$ で $C$ を対角行列 $D$ に変え、$D^n$ を計算する。
段 1（$P$ は逆行列をもつ）：$\det P=\alpha\cdot1-\beta\cdot1=\alpha-\beta\ne0$ なので、prop-mfr-inverse により
$$ P^{-1}=\frac1{\alpha-\beta}\begin{pmatrix}1&-\beta\\-1&\alpha\end{pmatrix} $$
である。
段 2（$CP=PD$）：thm-mfr-charpoly により $C\begin{pmatrix}\alpha\\1\end{pmatrix}=\alpha\begin{pmatrix}\alpha\\1\end{pmatrix}$、$C\begin{pmatrix}\beta\\1\end{pmatrix}=\beta\begin{pmatrix}\beta\\1\end{pmatrix}$ である。行列の積 $CP$ の各列は、$C$ と $P$ の各列の積なので
$$ CP=\begin{pmatrix}\alpha\cdot\alpha&\beta\cdot\beta\\\alpha\cdot1&\beta\cdot1\end{pmatrix},\qquad PD=\begin{pmatrix}\alpha&\beta\\1&1\end{pmatrix}\begin{pmatrix}\alpha&0\\0&\beta\end{pmatrix}=\begin{pmatrix}\alpha^2&\beta^2\\\alpha&\beta\end{pmatrix} $$
となり、$CP=PD$ である。左から $P^{-1}$ を掛けて $P^{-1}CP=D$、右から $P^{-1}$ を掛けて $C=PDP^{-1}$ を得る。
段 3（$C^n=PD^nP^{-1}$）：帰納法で示す。$n=0$ では $PEP^{-1}=PP^{-1}=E$ である。$C^n=PD^nP^{-1}$ とすると、
$$ C^{n+1}=C^nC=(PD^nP^{-1})(PDP^{-1})=PD^n(P^{-1}P)DP^{-1}=PD^{n+1}P^{-1} $$
である。また $D^n=\begin{pmatrix}\alpha^n&0\\0&\beta^n\end{pmatrix}$ である（対角行列どうしの積は、対角成分どうしの積になる）。
段 4（一般項）：prop-mfr-power により $v_n=C^nv_0=PD^nP^{-1}v_0$ である。右から順に計算する。
$$ P^{-1}v_0=\frac1{\alpha-\beta}\begin{pmatrix}a_1-\beta a_0\\-a_1+\alpha a_0\end{pmatrix},\qquad D^nP^{-1}v_0=\frac1{\alpha-\beta}\begin{pmatrix}(a_1-\beta a_0)\,\alpha^n\\-(a_1-\alpha a_0)\,\beta^n\end{pmatrix}. $$
$v_n$ の下の成分 $a_n$ は、$P$ の下の行 $(1\ \ 1)$ とこのベクトルの積、つまり 2 つの成分の和であり、主張の式を得る。$\square$

C の n 乗を書き下す

$C=\begin{pmatrix}2&3\\1&0\end{pmatrix}$ では $\alpha=3$、$\beta=-1$ で、$P=\begin{pmatrix}3&-1\\1&1\end{pmatrix}$、$P^{-1}=\frac14\begin{pmatrix}1&1\\-1&3\end{pmatrix}$ である。まず
$$ PD^n=\begin{pmatrix}3&-1\\1&1\end{pmatrix}\begin{pmatrix}3^n&0\\0&(-1)^n\end{pmatrix}=\begin{pmatrix}3^{n+1}&-(-1)^n\\3^n&(-1)^n\end{pmatrix} $$
であり、これに右から $P^{-1}$ を掛けると
$$ C^n=\frac14\begin{pmatrix}3^{n+1}+(-1)^n&3^{n+1}-3(-1)^n\\3^n-(-1)^n&3^n+3(-1)^n\end{pmatrix} $$
となる。$n=4$ では $C^4=\frac14\begin{pmatrix}244&240\\80&84\end{pmatrix}=\begin{pmatrix}61&60\\20&21\end{pmatrix}$ で、$C$ を 4 回掛けた結果と一致する。$v_0=\begin{pmatrix}4\\0\end{pmatrix}$ に掛けると下の成分は $\frac14\cdot4\,(3^n-(-1)^n)=3^n-(-1)^n$ で、ex-mfr-review の答えと同じである。

虚数の固有値でも対角化できる

thm-mfr-distinct の証明は、$\alpha,\beta$ が虚数でもそのまま通る（使ったのは四則演算だけである）。たとえば周期 6 の漸化式 $a_{n+2}=a_{n+1}-a_n$ のコンパニオン行列 $\begin{pmatrix}1&-1\\1&0\end{pmatrix}$ は、固有値が虚数 $\frac{1\pm\sqrt3\,i}2$ だけである（lem-mfr-eigen-root）。成分が実数のベクトル $v\ne\mathbf 0$ に実数の行列を掛けても成分は実数のままなので、$Cv$ が $v$ の虚数倍になることはなく、実数の範囲には固有ベクトルがない。対角化する $P$ の列は固有ベクトルでなければならない（重解とJordan細胞で示す）ので、成分が実数の $P$ では対角化できない。しかし複素数の範囲では $P=\begin{pmatrix}\frac{1+\sqrt3\,i}2&\frac{1-\sqrt3\,i}2\\1&1\end{pmatrix}$ で対角化できる。
同じように、ex-mfr-eigen-rot の回転 $R$ も、固有ベクトル $\begin{pmatrix}1\\-i\end{pmatrix}$（固有値 $i$）と $\begin{pmatrix}1\\i\end{pmatrix}$（固有値 $-i$）を並べた $P=\begin{pmatrix}1&1\\-i&i\end{pmatrix}$ で対角化できる。実際 $R\begin{pmatrix}1\\i\end{pmatrix}=\begin{pmatrix}-i\\1\end{pmatrix}=-i\begin{pmatrix}1\\i\end{pmatrix}$、$\det P=i-(-i)=2i\ne0$ であり、
$$ P^{-1}RP=\frac1{2i}\begin{pmatrix}i&-1\\i&1\end{pmatrix}\begin{pmatrix}0&-1\\1&0\end{pmatrix}\begin{pmatrix}1&1\\-i&i\end{pmatrix}=\begin{pmatrix}i&0\\0&-i\end{pmatrix} $$
となる。

Fibonacci 数と Binet の公式

Fibonacci数 $F_0=0$、$F_1=1$、$F_{n+2}=F_{n+1}+F_n$ のコンパニオン行列は $C=\begin{pmatrix}1&1\\1&0\end{pmatrix}$ で、特性方程式 $t^2=t+1$ の解は $\varphi=\frac{1+\sqrt5}2$、$\psi=\frac{1-\sqrt5}2$、$\varphi-\psi=\sqrt5$ である。thm-mfr-distinct の式に $a_0=0$、$a_1=1$ を入れると
$$ F_n=\frac{\varphi^n-\psi^n}{\sqrt5} $$
（Binet の公式）を得る。$n=5$ で $\varphi^5=\frac{11+5\sqrt5}2$、$\psi^5=\frac{11-5\sqrt5}2$ なので $F_5=\frac{5\sqrt5}{\sqrt5}=5$ である。$|\psi|<1$ なので $\psi^n$ は $0$ に近づき、$v_n=\begin{pmatrix}F_{n+1}\\F_n\end{pmatrix}$ は固有ベクトル $\begin{pmatrix}\varphi\\1\end{pmatrix}$ の方向に近づく。比 $F_{n+1}/F_n$ は $1,2,1.5,1.666\ldots,1.6,1.625,\dots$ と $\varphi=1.6180\ldots$ に近づく。

図2：Fibonacci 数の点は固有ベクトルの方向の直線に近づき、比は黄金比に近づく
図 2 の左は点 $v_n=(F_{n+1},F_n)$、右は比 $F_{n+1}/F_n$ である。$v_n$ を 2 本の固有ベクトルの方向に分けると、$\varphi$ の方向の成分は毎回 $\varphi\approx1.618$ 倍に育ち、$\psi$ の方向の成分は毎回 $\psi\approx-0.618$ 倍に縮む。そのため、育つ成分の方向だけが残って見える。

高校の手順との対応

ex-mfr-review で使った「$a_{n+1}+a_n$ は公比 $3$ の等比数列」は、行列の言葉では何にあたるのだろうか。

左固有ベクトルによる成分の取り出し

thm-mfr-distinct の証明の段 1 により、$P^{-1}$ の上の行は $\frac1{\alpha-\beta}(1\ \ {-\beta})$、つまり $(1\ \ {-\beta})$ の定数倍である。定数倍しても以下の性質は変わらないので、$(1\ \ {-\beta})$ を使う。これを左から $C$ に掛けると、$p=\alpha+\beta$、$q=-\alpha\beta$ により
$$ (1\ \ {-\beta})\begin{pmatrix}p&q\\1&0\end{pmatrix}=(p-\beta\ \ \ q)=(\alpha\ \ {-\alpha\beta})=\alpha\,(1\ \ {-\beta}) $$
となる。このような横ベクトルを左固有ベクトルという。したがって、数 $(1\ \ {-\beta})\,v_n=a_{n+1}-\beta a_n$ は
$$ (1\ \ {-\beta})\,v_{n+1}=(1\ \ {-\beta})\,Cv_n=\alpha\,(1\ \ {-\beta})\,v_n $$
により毎回 $\alpha$ 倍される。高校で使う「$a_{n+1}-\beta a_n$ は公比 $\alpha$ の等比数列」は、$v_n$ を固有ベクトルの方向に分けたときの成分を取り出す操作である。2 つの成分を求めて組み合わせることが、$P^{-1}$ を掛けてから $P$ を掛けることにあたる。

左固有ベクトルを確かめる

$C=\begin{pmatrix}2&3\\1&0\end{pmatrix}$（$\alpha=3$、$\beta=-1$）では
$$ (1\ \ 1)\,C=(2+1\ \ \ 3+0)=(3\ \ 3)=3\,(1\ \ 1),\qquad (1\ \ {-3})\,C=(2-3\ \ \ 3+0)=(-1\ \ 3)=-1\cdot(1\ \ {-3}) $$
である。$(1\ \ 1)v_n=a_{n+1}+a_n$ は公比 $3$、$(1\ \ {-3})v_n=a_{n+1}-3a_n$ は公比 $-1$ の等比数列になる。これが ex-mfr-review の 2 つの等比数列である。

例と反例

外した仮定	崩れる結論	ボックス
特性方程式が異なる 2 解をもつ	固有ベクトルを並べた正則な $P$ がある	ex-mfr-double-counter
係数が定数（毎回同じ行列を掛ける）	$v_n=C^nv_0$	ex-mfr-nonconstant

反例：重解では固有ベクトルが 1 方向しかない

$a_{n+2}=4a_{n+1}-4a_n$ のコンパニオン行列 $C=\begin{pmatrix}4&-4\\1&0\end{pmatrix}$ は、$\chi_C(t)=(t-2)^2$ で固有値は $2$ だけである（重解）。固有ベクトル $\begin{pmatrix}x\\y\end{pmatrix}$ は $(C-2E)\begin{pmatrix}x\\y\end{pmatrix}=\begin{pmatrix}2x-4y\\x-2y\end{pmatrix}=\mathbf 0$、すなわち $x=2y$ を満たすものなので、$\begin{pmatrix}2\\1\end{pmatrix}$ の定数倍しかない。2 本の固有ベクトル $c\begin{pmatrix}2\\1\end{pmatrix}$、$d\begin{pmatrix}2\\1\end{pmatrix}$ を並べた行列の行列式は $2c\cdot d-2d\cdot c=0$ で、逆行列をもたない。thm-mfr-distinct の方法は使えない。この場合は重解とJordan細胞で扱う。

反例：係数が n によると毎回違う行列を掛ける

$a_{n+2}=a_{n+1}+(n+1)a_n$ では、$v_{n+1}=C_nv_n$、$C_n:=\begin{pmatrix}1&n+1\\1&0\end{pmatrix}$ となり、掛ける行列が $n$ ごとに変わる。$v_2=C_1C_0v_0$ であって $C_0^2v_0$ ではない。$C_0=\begin{pmatrix}1&1\\1&0\end{pmatrix}$、$C_1=\begin{pmatrix}1&2\\1&0\end{pmatrix}$ について $C_1C_0=\begin{pmatrix}3&1\\1&1\end{pmatrix}$、$C_0C_1=\begin{pmatrix}2&2\\1&2\end{pmatrix}$ で、掛ける順序によって結果も変わる。1 つの行列の固有値で一般項を表すことはできない。

微分方程式との対応

同じ特性方程式 $t^2=pt+q$ は、微分方程式 $y''=py'+qy$ を解くときにも現れる。$e^{\lambda x}$ は微分すると $\lambda$ 倍になるので、1 つずらすと $\lambda$ 倍になる等比数列 $\lambda^n$ の役をする。この記事の行列の見方も、そのまま微分方程式に移る。

漸化式 $a_{n+2}=pa_{n+1}+qa_n$	微分方程式 $y''=py'+qy$
1 つずらす：$a_n\mapsto a_{n+1}$	微分する：$y\mapsto y'$
等比数列 $\alpha^n$（ずらすと $\alpha$ 倍）	指数関数 $e^{\alpha x}$（微分すると $\alpha$ 倍）
$b_n:=a_{n+1}-\beta a_n$ は $b_{n+1}=\alpha b_n$	$z:=y'-\beta y$ は $z'=\alpha z$
重解：$a_n/\alpha^n$ が等差数列	重解：$y/e^{\alpha x}$ が 1 次関数
一般項 $A\alpha^n+B\beta^n$、重解で $(A+Bn)\alpha^n$	一般解 $Ae^{\alpha x}+Be^{\beta x}$、重解で $(A+Bx)e^{\alpha x}$
$v_n=(a_{n+1},a_n)^{\top}$ は $v_{n+1}=Cv_n$	$Y=(y',y)^{\top}$ は $Y'=CY$（同じ $C$）

右の列は本記事では証明しない。証明は微分方程式としての指数関数・三角関数にある。その記事は方程式を $y''+py'+qy=0$ の形で書くので、ここでの $p,q$ はその記事の $-p,-q$ にあたる。また、その記事では $p,q$ を実数とし、特性方程式の解が虚数のときは一般解を $\cos$ と $\sin$ で書いている。

さらに先へ

重解の場合：コンパニオン行列は対角化できず、$\begin{pmatrix}\alpha&1\\0&\alpha\end{pmatrix}$ の形（Jordan 細胞）に変形される。一般項の $n\alpha^n$ はその $n$ 乗から現れる（重解とJordan細胞）。
余りによる計算：$C^n$ は、$t^n$ を固有多項式 $t^2-pt-q$ で割った余りに $C$ を代入しても求まる（行列のn乗と割り算の余り）。
項が増えても同じ：$a_{n+k}=c_1a_{n+k-1}+\cdots+c_ka_n$ でも、$k$ 項を縦に並べたベクトルに $k$ 次のコンパニオン行列を掛ける形になり、特性方程式はその固有方程式になる（固有多項式）。$k$ 個の異なる固有値があれば対角化できる（本記事では証明しない。Axl24 5.58、p. 166）。
微分方程式を行列で解く：上の対応表で $C^n$ にあたるのは行列の指数関数 $e^{xC}$ で、$Y'=CY$ の解は $Y=e^{xC}Y(0)$ と書ける。$e^{xC}$ も対角化を使って計算できる（本記事では扱わない。行列の指数関数）。