Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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 1

up vote 2 down vote accepted

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.