
> 
> **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.



Solving Linear Matrix Recurrences
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).


