Linear recurrence with matrix/vectors It's well-known how to find the general solution to a linear recurrence
$$
a(t) = c_1a(t-1) + \cdots + c_ka(t-k)
$$
by looking at the characteristic polynomial, etc.
What is the general method to solve a linear recurrence relation involving vectors and matrices as coefficients? Here $v(t) \in \mathbb C^{n}$ and $A_i\in \text{Mat}^{n\times n}(\mathbb C)$.
$$v(t) = A_1v(t-1) + \cdots + A_{t-k}v(t-k).$$
 A: It's essentially the same as in the scalar case.  Suppose the recurrence is: $$v(t)=A_1\,v(t-1)+\cdots+A_k\,v(t-k),$$
where $v(t)$ is a column vector $(v_1(t),\ldots,v_n(t))^\mathrm{T}$ and $A_i$ is an $n\times n$ matrix of constants. Of course we need to specify initial vectors $v(0), \ldots, v(k-1)$ to get started. 
For $i=1, \ldots, n$, let $B_i = b_{i,0} + b_{i,1}\,x+ b_{i,2}\,x^2+\cdots$ be the formal power series in $x$, with $b_{i,j} := v_i(j)$, and let $B$ be the column vector $(B_1,\ldots, B_n)^\mathrm{T}$.  The recurrence relation tells us that
$$C:=B-(A_1\,B\,x+\cdots+A_k\,B\,x^k)= (I-A_1\,x-A_2x^2-\cdots-A_k\,x^k)\,B.$$
is a column of polynomials in $x$.
  Here, $(I-A_1\,x-A_2x^2-\cdots-A_k\,x^k)$ is an $n\times n$ matrix whose entries are polynomials in $x$.  Each  off-diagonal entry is either $0$ or of degree $>0$, while the diagonal entries have non-zero constant term.  Therefore, the determinant of this matrix is non-zero and hence it has an inverse with entries in the field of rational functions.  Thus:
$$B= (I-A_1\,x-A_2x^2-\cdots-A_k\,x^k)^{-1}\,C.$$
I needed to use this method for a problem in combinatorial probability that I was working on. I have been searching for a reference in a textbook, but have not yet found it described anywhere. 
