この記事は、昔 Hatena Blog に書いたもののリライトになります。Hatena Blog の数式レイアウトが崩れて、修復に時間を要すると判断したため、Qiita でリライトすることにしました。
受験数学において三項間漸化式は頻出します。以下のようなやつ。
$$
a_{n+2}=3a_{n+1}-2a_nの一般解を求めよ
$$
これを解くには、特性方程式を解いて式を比較して……というめんどくさい手続きをふまなければならないのですが、行列の対角化を使うことにより（計算量はともかく）手続き上はスムーズに解くことができます。
$$
\begin{pmatrix}
a_{n+2} \\
a_{n+1}\
\end{pmatrix}=
\begin{pmatrix}
3 & -2 \\
1 & 0 \
\end{pmatrix}
\begin{pmatrix}
a_{n+1} \\
a_n\
\end{pmatrix}
$$
$$
\Longleftrightarrow
$$
$$
\begin{pmatrix}
a_{n+1} \\
a_n\
\end{pmatrix}=
\begin{pmatrix}
3 & -2 \\
1 & 0 \
\end{pmatrix}^{n-1}
\begin{pmatrix}
a_2 \\
a_1\
\end{pmatrix}
$$
$$
\begin{pmatrix}
a_{n+1} \\
a_n\
\end{pmatrix}=
\begin{pmatrix}
1 & 2 \\
1 & 1 \
\end{pmatrix}
\begin{pmatrix}
1 & 0 \\
0 & 2 \
\end{pmatrix}^{n-1}
\begin{pmatrix}
-1 & 2 \\
1 & -1 \
\end{pmatrix}
\begin{pmatrix}
a_2 \\
a_1\
\end{pmatrix}
$$
$$
\Longleftrightarrow
$$
$$
a_n=
\begin{pmatrix}
1 & 1 \
\end{pmatrix}
\begin{pmatrix}
1 & 0 \\
0 & 2 \
\end{pmatrix}^{n-1}
\begin{pmatrix}
-1 & 2 \\
1 & -1 \
\end{pmatrix}
\begin{pmatrix}
a_2 \\
a_1\
\end{pmatrix}
$$
$$
a_n=
\begin{pmatrix}
1 & 2^{n-1} \
\end{pmatrix}
\begin{pmatrix}
-a_1+2a_2 \\
a_1-a_2 \
\end{pmatrix}
$$
$$
a_n=-a_1+2a_2+2^{n-1}(a_1-a_2)
$$
めでたしめでたし。テクニックだけを知りたいのならば、ここから先は読む必要はありません。
行列の意味するところ
$$
A=\begin{pmatrix}
3 & -2 \\
1 & 0 \
\end{pmatrix}
$$
この行列が意味するところを考えていきます。$2 \times 2$ の行列は平面上における座標変換、それも線形変換を示しています。
つまり、上の行列は $xy$ 平面において $(x,y)=(a_{n+1},a_n)$ という点がどこからどこへ移動するかを示しているということになります。変換の様子を図示したものが下の図になります。
この図示は、私が自作したシェーダ「EigenShader」によるものです。GitHubリポジトリはここ。
Aを作用させ続けると、$(1,0)$ がどのような動きをするかを図示したものが下になります。
また、固有値を持つ線形変換は対角化によって直交基底の成分を抽出することができます。直交基底というとものものしいですが、要は「横方向に $n$ 倍、縦方向に $m$ 倍しているだけ」という状態です。見方を変えると、真の姿はそのようなシンプルな変換であるにも関わらず、何かの事情で、歪んだレンズを介してしか格子座標の世界に姿を現せないかわいそうな行列が $A$ であるともいえます（向こうからしたら我々の世界こそ $A^{-1}$ に歪んだ世界でしょうが）。
その証拠に、歪んだ座標に合わせた初期値を与えてやると以下の通り、
$$
\begin{pmatrix}
3 & -2 \\
1 & 0
\end{pmatrix}
\begin{pmatrix}
1 \\
1
\end{pmatrix}=
\begin{pmatrix}
1 \\
1
\end{pmatrix}=1 \cdot
\begin{pmatrix}
1 \\
1
\end{pmatrix}
$$
$$
a_1=1,a_2=1の時、a_n=1,1,1,1,…
$$
$$
\begin{pmatrix}
3 & -2 \\
1 & 0
\end{pmatrix}
\begin{pmatrix}
2 \\
1
\end{pmatrix}=
\begin{pmatrix}
4 \\
2
\end{pmatrix}=2 \cdot
\begin{pmatrix}
2 \\
1
\end{pmatrix}
$$
$$
a_1=1,a_2=2の時、a_n=1,2,4,8,…
$$
ベクトルがそのまま $1$ 倍、$2$ 倍されています。なんという素直な変換！ お気づきの方も多いと思いますが、「$n$ 倍、$m$ 倍」は行列の固有値、「歪んだ座標に合わせた初期値」は行列の固有ベクトルに相当します。
固有値が重複する場合
漸化式の話に戻ると、特性方程式が重解を持つ場合があります。以下のようなやつ。
$$
a_{n+2}=4a_{n+1}-4a_nの一般解を求めよ
$$
オーソドックスな手法だと、変数の数に対して方程式が足りなくなるため、$2^{n}$ で割るなどの小細工が必要になりますが、行列を用いた手法ならばそのようなものは必要ありません。
$$
\begin{pmatrix}
a_{n+2} \\
a_{n+1}\
\end{pmatrix}=
\begin{pmatrix}
4 & -4 \\
1 & 0 \
\end{pmatrix}
\begin{pmatrix}
a_{n+1} \\
a_n\
\end{pmatrix}
$$
$$
\Longleftrightarrow
$$
$$
\begin{pmatrix}
a_{n+1} \\
a_n\
\end{pmatrix}=
\begin{pmatrix}
4 & -4 \\
1 & 0 \
\end{pmatrix}^{n-1}
\begin{pmatrix}
a_2 \\
a_1\
\end{pmatrix}
$$
$$
\begin{pmatrix}
a_{n+1} \\
a_n\
\end{pmatrix}=
\begin{pmatrix}
2 & 1 \\
1 & 0 \
\end{pmatrix}
\begin{pmatrix}
2 & 1 \\
0 & 2 \
\end{pmatrix}^{n-1}
\begin{pmatrix}
0 & 1 \\
1 & -2 \
\end{pmatrix}
\begin{pmatrix}
a_2 \\
a_1\
\end{pmatrix}
$$
$$
\Longleftrightarrow
$$
$$
a_n=
\begin{pmatrix}
1 & 0 \
\end{pmatrix}
\begin{pmatrix}
2 & 1 \\
0 & 2 \
\end{pmatrix}^{n-1}
\begin{pmatrix}
0 & 1 \\
1 & -2 \
\end{pmatrix}
\begin{pmatrix}
a_2 \\
a_1\
\end{pmatrix}
$$
$$
a_n=
\begin{pmatrix}
1 & 0 \
\end{pmatrix}
\begin{pmatrix}
2^{n-1} & (n-1)2^{n-2} \\
0 & 2^{n-1} \
\end{pmatrix}
\begin{pmatrix}
0 & 1 \\
1 & -2 \
\end{pmatrix}
\begin{pmatrix}
a_2 \\
a_1\
\end{pmatrix}
$$
$$
a_n=
\begin{pmatrix}
2^{n-1} & (n-1)2^{n-2} \
\end{pmatrix}
\begin{pmatrix}
a_1 \\
a_2-2a_1 \
\end{pmatrix}
$$
$$
a_n=2^{n-1}a_1+(n-1)2^{n-2}(a_2-2a_1)
$$
次元を上げて行列で殴る…定数項編
でもこの手法で扱えるのって線形変換だけじゃないの？ と思った方へ。ご安心ください、以下のような非線形な式も次元を増やすことによって線形行列で殴ることができます。
$$
a_{n+1}=2a_n+1の一般解を求めよ
$$
行列形及び回答は以下の通り。
\begin{pmatrix}
a_{n+1} \\\
1
\end{pmatrix}=
\begin{pmatrix}
2 & 1 \\\
0 & 1
\end{pmatrix}
\begin{pmatrix}
a_n \\\
1
\end{pmatrix}
$$
\begin{pmatrix}
a_n \\
1\
\end{pmatrix}=
\begin{pmatrix}
2 & 1 \\
0 & 1 \
\end{pmatrix}^{n-1}
\begin{pmatrix}
a_1 \\
1\
\end{pmatrix}
$$
$$
\begin{pmatrix}
a_n \\
1\
\end{pmatrix}=
\begin{pmatrix}
-1 & 1 \\
1 & 0 \
\end{pmatrix}
\begin{pmatrix}
1 & 0 \\
0 & 2 \
\end{pmatrix}^{n-1}
\begin{pmatrix}
0 & 1 \\
1 & 1 \
\end{pmatrix}
\begin{pmatrix}
a_1 \\
1\
\end{pmatrix}
$$
$$
a_n=
\begin{pmatrix}
-1 & 1 \
\end{pmatrix}
\begin{pmatrix}
1 & 0 \\
0 & 2 \
\end{pmatrix}^{n-1}
\begin{pmatrix}
0 & 1 \\
1 & 1 \
\end{pmatrix}
\begin{pmatrix}
a_1 \\
1\
\end{pmatrix}
$$
$$
a_n=
\begin{pmatrix}
-1 & 2^{n-1} \
\end{pmatrix}
\begin{pmatrix}
1 \\
a_1+1 \
\end{pmatrix}
$$
$$
a_n=-1+2^{n-1}(a_1+1)
$$
この変形は、幾何学的に見ればアフィン変換です。
次元を上げて行列で殴る…階差数列編
次元を上げれば非線形な漸化式も行列計算で解決できる！
今度はさらに発展させてみましょう。
$$
a_{n+1}=a_n+nの一般解を求めよ
$$
いわゆる階差数列というやつ。
これも漸化式を分解することによって以下のように整理できます。
$$
a_{n+1}=a_n+b_n
$$
$$
b_{n+1}=b_n+1
$$
\begin{pmatrix}
a_{n+1} \\\
b_{n+1} \\\
1
\end{pmatrix}=
\begin{pmatrix}
1 & 1 & 0\\\
0 & 1 & 1\\\
0 & 0 & 1
\end{pmatrix}
\begin{pmatrix}
a_n \\\
b_n \\\
1
\end{pmatrix}
\begin{pmatrix}
a_n \\\
b_n \\\
1
\end{pmatrix}=
\begin{pmatrix}
1 & 1 & 0\\\
0 & 1 & 1\\\
0 & 0 & 1
\end{pmatrix}^{n-1}
\begin{pmatrix}
a_1 \\\
1 \\\
1
\end{pmatrix}
$$
※a_2=a_1+1よりb_1=1
$$
\begin{pmatrix}
a_n \\\
b_n \\\
1
\end{pmatrix}=
\begin{pmatrix}
1 & n-1 & \frac{(n-1)(n-2)}{2}\\\
0 & 1 & n-1\\\
0 & 0 & 1
\end{pmatrix}
\begin{pmatrix}
a_1 \\\
1 \\\
1
\end{pmatrix}
a_n=
\begin{pmatrix}
1 & n-1 & \frac{(n-1)(n-2)}{2}
\end{pmatrix}
\begin{pmatrix}
a_1 \\\
1 \\\
1
\end{pmatrix}
$$
a_n=a_1+(n-1)+\frac{(n-1)(n-2)}{2}
$$
$$
a_n=a_1+\frac{n(n-1)}{2}
$$
補足
補足1
タイトルに「平面上」とありますが、正確には「$\mathbb{R}^n$ のユークリッド空間上」です。タイトルのわかりやすさを優先しました。
補足2
$$
a_{n+1}=a_n+b_n
$$
$$
b_{n+1}=b_n+1
$$
を変形すると以下のような三項間漸化式（＋定数項）になります。
$$
a_{n+2} = a_{n+1}+b_{n+1}
$$
$$
a_{n+2} = a_{n+1}+b_n+1
$$
$$
a_{n+2} = a_{n+1}+(a_{n+1}-a_n)+1
$$
$$
a_{n+2} = 2a_{n+1}-a_n+1
$$
つまりこの2つの漸化式は、初期値の反映のされ方（つまり「歪み」）による見え方が違うだけで、本質的には同一のものであるといえます。実際に、得られるジョルダン標準形も同じです。
\begin{pmatrix}
2 & -1 & 1\\\
1 & 0 & 0\\\
0 & 0 & 1
\end{pmatrix}=
\begin{pmatrix}
1 & 1 & 0\\\
1 & 0 & 0\\\
0 & 0 & 1
\end{pmatrix}
\begin{pmatrix}
1 & 1 & 0\\\
0 & 1 & 1\\\
0 & 0 & 1
\end{pmatrix}
\begin{pmatrix}
0 & 1 & 0\\\
1 & -1 & 0\\\
0 & 0 & 1
\end{pmatrix}