こんにちは！@tsum_tsumです！

今回は機械学習から離れて、完全に個人の趣味で記事を書こうと思います。

なぜこんな記事を書こうと思ったかというと、@tsum_tsumはエンジニアをする前、とある学校で（数学の）教師をしておりました。教材研究をするのですが、その過程で浮かんだ疑問は記事のネタになるんじゃないか？ と思って書いてみたくなりました。

では今回のテーマですが、「特性方程式」です。他の分野でも同じ名称が出てくるかと思いますが、今回は高校数学の数列（漸化式） に絞ってお話していければと思います。

もし、ご興味があればご一読していただければ、今後の励みになりますのでよろしくお願いします！

はじめに

皆さんが高校生の時に習うであろう「漸化式」を振り返ってみましょう。教科書に出てくる漸化式は下記のようだったかと思います。

a_{n+1} = pa_n + q,

a_{n+2} = pa_{n+1} + qa_n.

特に、上の式を二項間漸化式、下の式を三項間漸化式といったりしますね。一般に

a_{n+k-1} = p_{k-1}a_{n+k-2} + \cdots + p_2a_{n+1} + p_1 a_n

を $k$ 項間漸化式といいます。

高校生のとき、学校や塾、予備校の先生からこの特性方程式を教えられ、何となく解いていた方も多いのではないでしょうか。しかし、冷静になって考えると、「この特性方程式ってどこから来たの？」となるんですよね（かく言う私も当時はなっていなかったですが…）。そこで、今回は特性方程式がどうやって導出されるのか解説したいと思います。

特性方程式とは？

ここでは簡単のため、三項間漸化式 $a_{n+2} = pa_{n+1} + qa_n$ を考えましょう。この数列の特性方程式は

\begin{eqnarray}
a_{n+2} & \rightarrow & t^2 \\
a_{n+1} & \rightarrow & t \\
a_n     & \rightarrow & 1
\end{eqnarray}

と置き換えた方程式

t^2 = pt + q

のことです。そして、この特性方程式の解を $t = \alpha_1, \alpha_2$ としたとき、

a_n = c_1 \alpha_1^n + c_2 \alpha_2^n

と表されます。（ここでは、簡単のため $\alpha_1, \alpha_2 \in {\mathbb R}, \alpha_1 \ne \alpha_2$ を仮定しています。）

漸化式を行列を使って解く

漸化式に話を戻しましょう。いきなりですが、漸化式を行列を使って表してみます。すると下記のようになります。

\begin{pmatrix}
    a_{n+2} \\
    a_{n+1}
\end{pmatrix}
= 
\begin{pmatrix}
    p & q \\
    1 & 0
\end{pmatrix}
\begin{pmatrix}
a_{n+1} \\
a_n
\end{pmatrix}.

さらに式変形してみます。すると、下記のようになります。

\begin{eqnarray}
    \begin{pmatrix}
        a_{n+2} \\
        a_{n+1}
    \end{pmatrix}
    &=& 
    \begin{pmatrix}
        p & q \\
        1 & 0
    \end{pmatrix}
    \begin{pmatrix}
    a_{n+1} \\
    a_n
    \end{pmatrix}  \\
    &=&
    \begin{pmatrix}
        p & q \\
        1 & 0
    \end{pmatrix}^2
    \begin{pmatrix}
    a_n \\
    a_{n-1}
    \end{pmatrix}  \\
    &=& \cdots  \\
    &=&
    \begin{pmatrix}
        p & q \\
        1 & 0
    \end{pmatrix}^{n-1}
    \begin{pmatrix}
    a_2 \\
    a_1
    \end{pmatrix}.  \\
\end{eqnarray}

$a_1, a_2$ は初期条件なので、これで、$a_n$ を求められそうです。しかし、これを求めるには

\begin{pmatrix}
    p & q \\
    1 & 0
\end{pmatrix}^{n-1}

を計算する必要がありますね。そして、これを計算するには対角化が必要になります。

行列の対角化

行列の $n$ 乗を求めるために、対角化を振り返っていきましょう。行列 $A$ を対角化をするには、$A$ の固有方程式

\Phi_A(t) = {\rm det}(A - tE) = 0

を解く必要がありますね。ただし、${\rm det}$ は行列式のことです。$\Phi_A(t) = 0$ の2解を $\alpha_1, \alpha_2$ とすると、

P^{-1}AP = \begin{pmatrix}
    \alpha_1 & 0 \\
    0 & \alpha_2
\end{pmatrix}

と表せます。両辺を $n$ 乗することで、

\begin{eqnarray}
(P^{-1}AP)^n &=& \begin{pmatrix}
    \alpha_1 & 0 \\
    0 & \alpha_2
\end{pmatrix}^n \\
P^{-1}A^nP &=& \begin{pmatrix}
    \alpha_1^n & 0 \\
    0 & \alpha_2^n
\end{pmatrix} \\
A^n &=& P\begin{pmatrix}
    \alpha_1^n & 0 \\
    0 & \alpha_2^n
\end{pmatrix}P^{-1} \\
\end{eqnarray}

となり、$A^n$ が求められますね。

特性方程式の正体

では漸化式に戻りましょう。求めたい漸化式は $a_{n+2} = pa_{n+1} + qa_n$ で、それを行列の形に変換しましたね。

\begin{eqnarray}
    \begin{pmatrix}
        a_{n+2} \\
        a_{n+1}
    \end{pmatrix}
    &=&
    \begin{pmatrix}
        p & q \\
        1 & 0
    \end{pmatrix}^{n-1}
    \begin{pmatrix}
    a_2 \\
    a_1
    \end{pmatrix}.  \\
\end{eqnarray}

この漸化式を求めるには、固有方程式を解く必要があります。実際に表すと

\begin{eqnarray}
{\rm det}\left(
\begin{pmatrix} p & q \\ 1 & 0 \end{pmatrix}
-t\begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix}
\right) &=& 0  \\
{\rm det}\left(
\begin{pmatrix} p-t & q \\ 1 & -t \end{pmatrix}
\right) &=& 0  \\
-t(p-t)-q &=& 0  \\
t^2 -pt -q &=& 0
\end{eqnarray}

となります。そして、この固有方程式をよく見ると、$t^2 -pt -q = 0$ が求めたかった特性方程式になっていますね。実は、特性方程式の正体は対角化を計算する過程で現れる固有方程式のことだったんですね！

あとは同じように考えるだけです。$t^2 -pt -q = 0$ の2解を $\alpha_1, \alpha_2$ とすると、

\begin{eqnarray}
\begin{pmatrix} p & q \\ 1 & 0 \end{pmatrix}^n
&=& P\begin{pmatrix}
    \alpha_1^n & 0 \\
    0 & \alpha_2^n
\end{pmatrix}P^{-1} \\
\end{eqnarray}

と表せます。そして、

\begin{eqnarray}
    \begin{pmatrix}
        a_{n+2} \\
        a_{n+1}
    \end{pmatrix}
    &=&
    \begin{pmatrix}
        p & q \\
        1 & 0
    \end{pmatrix}^{n-1}
    \begin{pmatrix}
    a_2 \\
    a_1
    \end{pmatrix}  \\
\end{eqnarray}

に代入することで、$a_n = c_0 \alpha_1^n + c_1 \alpha_2^n$ が得られる、という仕組みなんですね！もちろん、$k$ 項間の漸化式にしても同様の議論で

a_n = c_0 \alpha_1^n + c_1 \alpha_2^n + \cdots + c_{k-1} \alpha_{k}^{n}

が得られます。これで、めでたしめでたし…。

さらにその先へ

※ここからは本題とは少し違う話題になっております。まとめに進みたい方はこちら。

ここまでで「なぜ特性方程式を考えるのか？」という問いには概ね答えられたかと思います。しかし、

（ここでは、簡単のため $\alpha_1, \alpha_2 \in {\mathbb R}, \alpha_1 \ne \alpha_2$ を仮定しています。）

と述べていたことを思い出してください。

もし上記のような仮定をしていれば、漸化式の一般項は $a_n = c_0 \alpha_1^n + c_1 \alpha_2^n$ のように表せます。しかし、なぜこのような仮定をする必要があるのでしょうか？それは、もしこの仮定を除いてしまうと $a_n = c_0 \alpha_1^n + c_1 \alpha_2^n$ のような一般項ではなくなってしまうからなんですね。

では、なぜそんなことが起こるのでしょうか？また、どのような一般項になるのでしょうか？それを解明するには、「対角化」というものが大きくかかわっています。

実は、行列の対角化はいつでもできるわけではないんですよね。

あらためて行列の対角化

これらの疑問を解消するために、あらためて行列の $n$ 乗の計算式を見てみましょう。固有方程式 $\Phi_A(t) = {\rm det}(A - tE) = 0$ の2解を $\alpha_1, \alpha_2 \ (\alpha_1 \ne \alpha_2)$ とすると

A^n = P\begin{pmatrix}
    \alpha_1^n & 0 \\
    0 & \alpha_2^n
\end{pmatrix}P^{-1} \\

と表せるのでした。さて、実はこの $P$ は $\alpha_1, \alpha_2$ に対応する固有ベクトルをそれぞれ

\begin{eqnarray}
{\rm v}_1 &=& (v_{11}, v_{12})^T \\
{\rm v}_2 &=& (v_{21}, v_{22})^T
\end{eqnarray}

としたときの、

P = \begin{pmatrix}
{\rm v}_1 & {\rm v}_2
\end{pmatrix}
= \begin{pmatrix}
v_{11} & v_{21}  \\
v_{12} & v_{22}
\end{pmatrix}

であることが簡単な計算により分かります。しかし、この $P$ をよく見ると、列ベクトルを 2つ横に並べた行列です。つまり、固有ベクトルが2つあるから表せるんですね（正確には固有空間の次元を考える必要があります）。もし、固有方程式の解が1つ（つまり重解を持つ）しかなく、対応する固有ベクトルが1つしかなければ、$P$ を求めることができませんね（2つの固有ベクトルを並べるには数が足りないですね）。

これが $a_n = c_0 \alpha_1^n + c_1 \alpha_2^n$ のような一般項ではなくなってしまう ことの原因です。つまり、固有ベクトルが1つしかないからなんですね。では、特性方程式の解が1つしかない場合はどのように一般項を表すことができるのでしょうか？次にそれを見ていきましょう。

一旦状況の整理

ここまでの議論は少しややこしいかと思いますので、少し整理します。

ここまで、$a_{n+2} = pa_{n+1} + qa_n$ という漸化式の一般項 $a_n$ を考えていましたね。漸化式の特性方程式は、

漸化式を行列で表現した時の固有方程式

であるということが先ほどまでの議論で分かったかと思います。次に「なぜ固有方程式を考える必要があるか」というと、

対角化をして、行列の $n$ 乗を求めたい

からでしたね。もし対角化ができるのであれば、$a_n = c_0 \alpha_1^n + c_1 \alpha_2^n$ のような一般項が得られて解決です。しかし、対角化はいつでもできるわけではありません。その原因は

固有ベクトルが1つしかない（固有方程式の解が1つしかない）

でしたね。では、いよいよ対角化ができない場合を見ていきましょう。

具体例から考える

先の問いに答えるため、まずは具体例から考えてみます。例えば、漸化式

a_{n+2} = 4a_{n+1} - 4a_n

を考えてみましょう。まず、特性方程式は $t^2 = 4t -4$ なので、解は $t=2$ になります。そうすると先ほどの議論から $a_n = c_0 \alpha_1^n + c_1 \alpha_2^n$ のような表現は得られません。

まぁこの漸化式の場合、$a_{n+2} - 2a_{n+1} = 2(a_{n+1} - 2a_n)$ なので、解けるっちゃ解けるんですけどね…。実際 $a_{n+1} - 2a_n= b_n$ とおいて、解いてみると、

a_n = (c_0n+c_1)2^{n-1}

という形になります。ただし、$c_0, c_1$ は初期値から決まる定数です。さて、先ほどの表現 $a_n = c_0 \alpha_1^n + c_1 \alpha_2^n$ と見比べてみると、$n$ が含まれているのが気になります。一体どこから $n$ が現れたんですかね？実はその正体は、ジョルダン標準形に隠されています。

ジョルダン標準形へ

先ほど、行列の対角化ができない例を見ていきました。行列 $A$ の対角化とは

P^{-1}AP = \begin{pmatrix}
    \alpha_1 & 0 \\
    0 & \alpha_2
\end{pmatrix}

の形で表現することでしたね。一方で対角化はいつでもできるわけではないということも見ていきました。では、いつでもできるような表現は存在するのでしょうか？実は、

P^{-1}AP = \begin{pmatrix}
    \alpha_1 & 1 \\
    0 & \alpha_2
\end{pmatrix}

のようにすると、この表現はどんな行列でも存在します！ 右上の $0$ が $1$ に変わっただけの行列ですね。そして、この右辺の形のことをジョルダン標準形といいます。そして同じように両辺を $n$ 乗すると、

A^n = P\begin{pmatrix}
    \alpha_1^n & n\alpha_1\alpha_2 \\
    0 & \alpha_2^n
\end{pmatrix}
P^{-1}

が得られます。そして、先ほどの式 $a_n = (c_0n+c_1)2^{n-1}$ に現れた $n$ の正体は、この行列の右上の成分にある $n$ のことだったんですね。

そして一般化へ

最後に $k$ 項間漸化式を見てみましょう。$k$ 項間漸化式は下記のように表される漸化式のことでした。

a_{n+k-1} = p_{k-1}a_{n+k-2} + \cdots + p_2a_{n+1} + p_1 a_n.

この漸化式の特性方程式は $t^k = p_{k-1}t^{k-1} + \cdots + p_2t + p_1$ となります。この方程式が

(t-\alpha_1)^{m_1}(t-\alpha_2)^{m_2}\cdots(t-\alpha_l)^{m_l}=0

のように変形されるとします。ただし、$l \le k, \ m_1 + \cdots + m_l = k$ です。すると、先の議論より、

a_n = (c_{11}+\cdots+c_{1m_1}n^{m_1-1})\alpha_1^{n-1}
+ (c_{21}+\cdots+c_{2m_2}n^{m_2-1})\alpha_2^{n-1}
+ \cdots
+ (c_{l1}+\cdots+c_{lm_l}n^{m_l-1})\alpha_l^{n-1}

になります。この表現はジョルダン標準形から帰着される形なのですが、先ほども述べた通りジョルダン標準形はいつでも存在するので、この式が定数係数の $k$ 項間漸化式の一般形になっています。

ということで、これで本当にめでたしめでたしです…！

まとめ

今回は高校数学の中で現れる疑問について説明してまいりました。特性方程式の正体は、漸化式を行列で表現したときに現れる係数行列の固有方程式だったんですね。

そして、漸化式に関連して行列の対角化について説明していきました。対角化をすることで行列の一般項を得られることを見ていきました。

最後にジョルダン標準形も見ていきました。全ての行列が対角化できるとは限らないので、対角化だけでは全ての漸化式の解法は網羅できません。そこで、ジョルダン標準形という形を考えることで、一般的な漸化式が全て網羅できる（定数係数の漸化式を対象にしています） ということも見ていきました。

個人的には書きたいことを書けて楽しかったのですが、機械学習やエンジニアとの関連性が薄いので、あまり役に立たないかもしれません。しかし、ここまで見てくださったということは最後まで読んでくださっているのだろうと思います。駄文ではございましたが、ここまでお付き合いいただき、ありがとうございます！

では次回お会いしましょう！