# Solving recursive relations using matrix method.

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?

-
If I understood you correctly, use the $3\times 3$ matrix with $a_{11}=2, a_{22}=3 , a_{33}=7$ and all other entries are 0, and operate on a vector of terms $P_n$ –  DBFdalwayse Aug 24 '13 at 9:42
@DBF no. I don't think that forms the correct relation. –  sudeepdino008 Aug 24 '13 at 9:46

## 1 Answer

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).$$

-