## 答r2123b──關於矩陣與遞迴關係式的特徵多項式

$\displaystyle y_{n}+a_1y_{n-1}+\cdots+a_{k-1}y_{n-k+1}+a_ky_{n-k}=0,~~~n\ge k$

\displaystyle\begin{aligned} y_{n}+a_1y_{n-1}+\cdots+a_{k-1}y_{n-k+1}+a_ky_{n-k}&=r^n+a_1r^{n-1}+\cdots+a_{k-1}r^{n-k+1}+a_kr^{n-k}\\ &=r^{n-k}(r^k+a_1r^{k-1}+\cdots+a_{k-1}r+a_k)=0.\end{aligned}

$p(r)=r^k+a_1r^{k-1}+\cdots+a_{k-1}r+a_k$

$\lambda_1,\ldots,\lambda_k$$p(r)$$k$ 個根。如果 $\lambda_j$ 相異，可得通解 (見“線性世界的根基──疊加原理”)

$\displaystyle y_n=c_1\lambda_1^n+\cdots+c_k\lambda_k^n$

\displaystyle\begin{aligned} y_n&=-a_1y_{n-1}-\cdots-a_{k-1}y_{n-k+1}-a_ky_{n-k}\\ y_{n-1}&=y_{n-1}\\ &\vdots\\ y_{n-k+1}&=y_{n-k+1},\end{aligned}

$\displaystyle \begin{bmatrix} y_{n-k+1}\\ y_{n-k+2}\\ \vdots\\ y_{n-1}\\ y_n \end{bmatrix}=\begin{bmatrix} 0&1&0&\cdots&0\\ 0&0&1&\cdots&0\\ \vdots&\vdots&\vdots&\ddots&\vdots\\ 0&0&0&\cdots&1\\ -a_k&-a_{k-1}&-a_{k-2}&\cdots&-a_1 \end{bmatrix}\begin{bmatrix} y_{n-k}\\ y_{n-k+1}\\ \vdots\\ y_{n-2}\\ y_{n-1} \end{bmatrix}$

$\displaystyle A=\begin{bmatrix} 0&1&0&\cdots&0\\ 0&0&1&\cdots&0\\ \vdots&\vdots&\vdots&\ddots&\vdots\\ 0&0&0&\cdots&1\\ -a_k&-a_{k-1}&-a_{k-2}&\cdots&-a_1 \end{bmatrix}$

$\displaystyle p_A(t)=\det(tI-A)=t^k+a_1t^{k-1}+\cdots+a_{k-1}t+a_k$

[1] 維基百科：向左走‧向右走