I'm looking for books/texts which develop some theory for systems of linear recurrence equations, if possible with focus on solvability and uniqueness (and whether or not the methods will always work).
So far I had no luck finding such references. I found a few examples in a few books, e.g. in "Foundations of Combinatorics with Applications" by Bender, which has a chapter on them, but without developing any theory regarding them.
You can reduce solving such things to taking powers of matrices, as follows (this is true even if there's only one recurrence, which is a useful thing to know about linear recurrences). It's a little tedious to write down the most general possible thing so let me just indicate the idea with an example. Suppose your system looks like
$$a_n = b_{n-1} + c_{n-2}$$ $$b_n = 2 a_{n-1} + a_{n-2} + c_{n-1}$$ $$c_n = a_{n-2} + 2 c_{n-1}.$$
Your goal is to rewrite the system so that it's a system of first-order recurrences - that is, so that only the index $n-1$ appears on the RHS. You do this by introducing new recurrences given by shifted versions of the old recurrences. In this case, we need to introduce new recurrences $d_n = a_{n-1}$ and $e_n = c_{n-1}$, which produces a new system
$$a_n = b_{n-1} + e_{n-1}$$ $$b_n = 2 a_{n-1} + d_{n-1} + c_{n-1}$$ $$c_n = d_{n-1} + 2 c_{n-1}$$ $$d_n = a_{n-1}$$ $$e_n = c_{n-1}$$
which can be written in matrix form as follows. Write $v_n = \left[ \begin{array}{c} a_n \\ b_n \\ c_n \\ d_n \\ e_n \end{array} \right]$; then the above system can be written
$$v_n = \left[ \begin{array}{ccccc} 0 & 1 & 0 & 0 & 1 \\ 2 & 0 & 1 & 1 & 0 \\ 0 & 0 & 2 & 1 & 0 \\ 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \end{array} \right] v_{n-1}.$$
Write $M$ for the matrix in the above equation. Then we have
$$\boxed{ v_n = M^n v_0. }$$