5
$\begingroup$

Question:

Are there standard techniques available for solving the following kind of linear matrix recurrence relations:

$$M_1,\cdots,M_k\ \in\ \mathbb{R}^{m\times n}$$ $$ A_1,\cdots,A_k\ \in\ \mathbb{R}^{n\times n}$$ $$M_{i+k+1}\ =\ \sum_{j=1}^{k}{M_{i+j}A_j} $$

I need to solve the special case of $k=2$ that appears in the iterative modification of edge weights of complete symmetric graphs.

$\endgroup$
2
  • $\begingroup$ Did you mean $n=m=2$? $\endgroup$
    – FusRoDah
    Mar 10, 2019 at 10:52
  • $\begingroup$ @FusRoDah in the case of symmetric graphs I have $k=2, n=m\gt 2$ as the number of vertices can be an arbitrary fixed number with at least 3 edges to rule out the trivial cases. $\endgroup$ Mar 10, 2019 at 10:57

1 Answer 1

7
$\begingroup$

Same method as for scalar equations works. Put matrices $M_{n+k-1},M_{n+k-2},...,M_{n}$ vertically into a big matrix $X_n$ of size $mk\times n$. Then your recurrence becomes a one-step recurrence $X_{n+1}=AX_{n}$, with some $A$, whose solution is $M^n=A^nX_0$, and this is solved by diagonalizing $A$ (or using its Jordan form).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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