Solving recursive relations using matrix method.

Question

I am looking to solve the recursive relation $P_n=2P_{(n-2)}+3P_{(n-3)}+7P_{(n-7)}$ using the matrix method. The matrix method solves the recursive relation in O(log n) time. How do we construct the matrix relation for such a recursive relation?

Answer 1

The basic idea of "the matrix method" is to rewrite the given recursion as $X_{n+1} = AX_n$, where $X_i \in \mathbb R^d$ and $A \in \def\Mat{\mathop{\mathrm{Mat}}\nolimits}\Mat_d(\mathbb R)$. To achieve this, we let $$ X_i := \begin{pmatrix} P_i \\ P_{i+1} \\ \vdots \\ P_{i+6} \end{pmatrix}\in \mathbb R^7 $$ We have \begin{align*} X_{i+1} &=\begin{pmatrix} P_{i+1} \\ P_{i+2} \\ \vdots \\ P_{i+7} \end{pmatrix}\\ &= \begin{pmatrix} P_{i+1} \\ P_{i+2} \\ \vdots \\ P_{i+6}\\ 2P_{i+5} + 3P_{i+4} + 7P_i \end{pmatrix}\\ &= \begin{pmatrix} 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 7 & 0 & 0 & 0 & 3 & 2 & 0\end{pmatrix} \cdot X_i \end{align*} So we have $$ A = \begin{pmatrix} 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 7 & 0 & 0 & 0 & 3 & 2 & 0\end{pmatrix} \in \Mat_7(\mathbb R). $$