Expresan los valores de una matriz en pow N

Question

Tengo una matriz cuadrada (que viene de una Cadena de Markov) que se ve así:

$$Q = \begin{bmatrix} 0 & 1& 0 & 0 & .. & 0 & 0\\ 0 & a & 1-a & 0 & .. & 0 & 0\\ 0 & 0 & b & 1 - b & .. & 0 & 0\\ .. & .. & .. & .. & .. & .. & .. \\ 0 & 0 & 0 & 0 & .. & 0 & 1 \end{bmatrix}$$

con $a, b, c,$ etc. los números reales entre el $0$ $1$ incluido.

Estoy interesado en los valores de la primera línea de la matriz $Q^N$. Actualmente, estoy usando una biblioteca (numpy) que me permite calcular $Q^N$ y luego leí la primera línea de esta matriz. Pero con grandes matrices ($> 500 \times 500$) y los grandes valores de $N$ (~ 10000), es un poco demasiado lento para mi uso.

Por curiosidad, me han conspirado $Q^N_{0,j}$ $N$ entre 1 a 1000 y me encontré con que se siga algo que se parece a una distribución de Poisson o similar (pero no sé si es sólo por mi específicos de la matriz de entrada $Q$ o no).

Mi pregunta es, dada una matriz Q, hay una manera para obtener los valores de $Q^N_{0,j}$ sin tener que calcular $Q^N$?

Edit: los términos de la diagonal son tales como: 0 <= a <= b <= c <= ... < 1

Edit2:

Parece que si puedo diagonalize $Q$, puedo usar $Q^n = P D^n P^{-1}$, lo que es más rápido para grandes valores de $n$ de una exponenciación al cuadrado (como el usado por numpy). El problema es que no estoy seguro de que es posible para cualquier matriz $Q$. Y si no es posible, me gustaría aceptar una ligera modificación de $Q$, $P$ o $D$ si el resultado es lo suficientemente cerca.

Edit3:

Los valores de la primera línea de $Q^N$$N \in [1,100]$:

Edit4:

es $a <= b$ e no $a < b$, lo siento!

Answer 1

Un general bidiagonal matriz no siempre es diagonalizable; por ejemplo, si $a=b=\ldots=\frac{1}{2}$ obtendrá un bloque de Jordan de autovalores $\frac{1}{2}$.

Pero, puesto que todas sus entradas son distintas, estás de suerte. Voy a cambiar de notación un poco:

$$M = \left[\begin{array}{ccccc} a_1 & 1-a_1 & & &\\ & a_2 & 1-a_2 & &\\ & & \ddots & &\\ & & & a_{n-1} & 1-a_{n-1}\\ & & & & 1\end{array}\right].$$ (En su caso, $a_1 = 0$.)

Entonces los autovalores de a $M$ son sencillamente $a_1, \ldots, a_{n-1},1$. El vector propio correspondiente a $1$ es, obviamente, la constante 1 vector. El autovector de a $a_i$ es el vector de la $v^i$, donde $$v^i_j = \begin{cases}0, &j > i\\ \frac{\prod_{k=j}^{i-1} (a_k-1)}{\prod_{k=j}^{i-1} (a_k-a_i)}, & j \leq i\end{cases}$$ y $v^i_i = 1$ por el vacío producto de la convención. Usted puede comprobar esta fórmula por mirar el $j$ésima fila de a $Mv^i$:

$$a_j \frac{\prod_{k=j}^{i-1} (a_k-1)}{\prod_{k=j}^{i-1} (a_k-a_i)} + (1-a_j+1)\frac{\prod_{k=j}^{i-1} (a_k-1)}{\prod_{k=j+1}^{i-1} (a_k-a_i)}=\left(a_j+\frac{(1-a_j)(a_j-a_i)}{a_j-1}\right)v^i_j = a_i v^i_j.$$

Así que ahora que usted tiene los vectores propios y valores propios, se puede descomponer $M = BDB^{-1}$ y calcular el $M^n = BD^nB^{-1}$.

EDIT: Aquí está la fórmula para $B^{-1}$. Escribir $$B = \left[\begin{array}{cccc} v^1 & v^2 & \ldots & v^n\end{array}\right]$$ donde $v^i$ es como el anterior y $v^n$ es el vector. Entonces $$B^{-1} = \left[\begin{array}{cccc} w^1 & w^2 & \ldots & w^n\end{array}\right]$$ con $$w^i_j = \begin{cases}0, &j > i\\ \frac{\prod_{k=j}^{i-1} (a_k-1)}{\prod_{k=j+1}^{i} (a_k-a_j)}, & j \leq i\end{cases}$$ para $i<n$ y $$w^n_j = \begin{cases}1, &j = n\\ -\frac{\prod_{k=j+1}^{n-1} (a_k-1)}{\prod_{k=j}^{n-2} (a_k-a_{n-1})}, & j < n.\end{cases}$$