¿Existe alguna forma de saber cuándo dos matrices de transferencia producen las mismas relaciones de recurrencia?

Question

En Combinatoria, matriz de transferencia es una matriz que define las relaciones de recurrencia lineal. Pregunto específicamente por la matriz

$\left(\begin{array}{cccc} 2 & 1 & 0 & 0\\ 1 & 1 & 0 & 0\\ 0 & 0 & 2 & 0\\ 1 & 0 & 0 & 2 \end{array}\right)$

Que define el siguiente conjunto de relaciones de recurrencia:

$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}$

Con las condiciones iniciales $a_0 = b_0 = c_0 = d_0 = 1$

Obtenemos la misma solución con otra matriz, difiriendo en la primera línea:

$\left(\begin{array}{cccc} 1 & 0 & 1 & 1\\ 1 & 1 & 0 & 0\\ 0 & 0 & 2 & 0\\ 1 & 0 & 0 & 2 \end{array}\right)$

Mi pregunta es: ¿hay una forma fácil e intuitiva de ver que esas dos matrices darían la misma solución? Y si la hay, ¿existe algún criterio general de la teoría matricial que generalice mi pregunta concreta?

Puede encontrar más información sobre la matriz de transferencia en El libro de Stanely o Flajolet & Sedgewick . Otra forma útil de pensar en esto es contar el número de caminos en el grafo cuya matriz de adyacencia (incluyendo multiplicidades de aristas) está representada por la matriz de transferencia

Answer 1

Básicamente, se pregunta si para dos matrices, $A$ y $B$ y para un vector inicial dado $v_0$ para cualquier $n \in \mathbb{N}$ $A^nv_0=B^nv_0$ . Si $v_0$ es un vector propio de $A$ y $B$ La comprobación de esto es fácil: equivale a $(A-B)v_0=0$ o $v_0 \in \ker{(A-B)}$ (la primera forma es conveniente para comprobar diferentes $B$ segundo - para comprobar diferentes $v_0$ ).

Ahora dejemos que $v_0=c_1e_1+...+c_ke_k=c_1'e_1'+...+c_k'e_k'$ donde $(e_1,...,e_k)$ es parte de la base de Jordan para $A$ para que $c_i \neq 0$ y $(e_1',...,e_k')$ es la base de Jordania para $B$ para que $c_i' \neq 0$ . Los valores propios más altos correspondientes deben ser iguales y las proyecciones de $v_0$ a los correspondientes eigenspaces $v_\lambda, v_\lambda'$ deben ser iguales; luego los valores propios correspondientes al segundo deben ser iguales y así sucesivamente.

Si Jordan bloquea para ambos $A$ y $B$ son triviales ( $A$ y $B$ no tienen vectores propios generalizados), esta es una condición suficiente: $v_0=v_{\lambda_1}+...+v_{\lambda_m}, A^nv_0=B^nv_0=\lambda_1^nv_{\lambda_1}+...+\lambda_m^nv_{\lambda_m}$ . En este caso, basta con comprobar $(A^n-B^n)v_0=0$ para $n \le \dim(A)$ o comprobar directamente la descomposición de $v_0$ en Jordania a base de $A$ y $B$ .

Entonces, para su pregunta: podemos ver que los valores propios de $A$ son ( $2,2,{3-\sqrt{5} \over 2},{3+\sqrt{5} \over 2}$ ), el bloque de Jordan para el valor 2 es trivial, $v_0=(-1)e_1+1e_2+(1-{2 \sqrt{5} \over 5})e_3+(1+{2 \sqrt{5} \over 5})e_4$ . Los valores propios de $B$ son ( $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'$ . Finalmente, $e_2-e_1=-e_2', e_3=e_3', e_4=e_4'$ .

No puedo decir que esta forma sea especialmente fácil (gracias a WolframAlpha por los cálculos); probablemente haya alguna forma inteligente de calcular todo eso sólo a partir de la forma de $(A-B)$ No pude averiguarlo.