Is there a nice way to tell when two transfer-matrices produce the same recurrence relations? In Combinatorics, transfer matrix is a matrix defining linear recurrence relations. I am asking specifically about the matrix
$\left(\begin{array}{cccc}
2 & 1 & 0 & 0\\
1 & 1 & 0 & 0\\
0 & 0 & 2 & 0\\
1 & 0 & 0 & 2
\end{array}\right)$
Which defines the following set of recurrence relations:
$a_{n}=2a_{n-1}+b_{n-1}$
$b_{n}=a_{n-1}+b_{n-1}$
$c_{n}=2c_{n-1}$
$d_{n}=a_{n-1}+2d_{n-1}$
With the initial conditions $a_0 = b_0 = c_0 = d_0 = 1$
We get the same solution with another matrix, differing in the first line:
$\left(\begin{array}{cccc}
1 & 0 & 1 & 1\\
1 & 1 & 0 & 0\\
0 & 0 & 2 & 0\\
1 & 0 & 0 & 2
\end{array}\right)$
My question is: is there an easy, intuitive way to see that those two matrices would yield the same solution? And if there is, is there some matrix-theory general criterion that generalizes my specific question?
More background on transfer-matrix can be found in Stanely's book or Flajolet & Sedgewick. Another helpful way of thinking on this is counting the number of paths in the graph whose adjacency matrix (including multiplicities of edges) is represented by the transfer-matrix 

Basically, you ask whether for two matrices, $A$ and $B$ and for given initial vector $v_0$, for any $n \in \mathbb{N}$ $A^nv_0=B^nv_0$. If $v_0$ is an eigenvector for $A$ and $B$, checking this is easy: it's equivalent to $(A-B)v_0=0$ or $v_0 \in \ker{(A-B)}$ (first form is convenient for checking different $B$, second - for checking different $v_0$).
Now let $v_0=c_1e_1+...+c_ke_k=c_1'e_1'+...+c_k'e_k'$ where $(e_1,...,e_k)$ is part of Jordan basis for $A$ so that $c_i \neq 0$ and $(e_1',...,e_k')$ is Jordan basis for $B$ so that $c_i' \neq 0$. Highest corresponding eigenvalues must be the same and projections of $v_0$ to corresponding eigenspaces $v_\lambda, v_\lambda'$ must be equal; then second-highest corresponding eigenvalues must be equal and so forth.
If Jordan blocks for both $A$ and $B$ are trivial ($A$ and $B$ don't have generalized eigenvectors), this is sufficient condition: $v_0=v_{\lambda_1}+...+v_{\lambda_m}, A^nv_0=B^nv_0=\lambda_1^nv_{\lambda_1}+...+\lambda_m^nv_{\lambda_m}$. In this case, it's enough to either check $(A^n-B^n)v_0=0$ for $n \le \dim(A)$, or directly check decomposition of $v_0$ in Jordan basis of $A$ and $B$.
So, for your question: we can see that eigenvalues of $A$ are ($2,2,{3-\sqrt{5} \over 2},{3+\sqrt{5} \over 2}$), Jordan block for value 2 is trivial, $v_0=(-1)e_1+1e_2+(1-{2 \sqrt{5} \over 5})e_3+(1+{2 \sqrt{5} \over 5})e_4$. Eigenvalues of $B$ are ($1,2,{3-\sqrt{5} \over 2},{3+\sqrt{5} \over 2}$), $v_0=0e_1'+(-1)e_2'+(1-{2 \sqrt{5} \over 5})e_3'+(1+{2 \sqrt{5} \over 5})e_4'$. Finally, $e_2-e_1=-e_2', e_3=e_3', e_4=e_4'$.
Can't say this way is especially easy (thanks to WolframAlpha for computations); probably there is some intelligent way to figure all that just from the form of $(A-B)$ I couldn't find out.
