Dado$A$, ¿hay una manera rápida de calcular la entrada$(i,j)$ th de$A^n$

Question

Estoy estudiando primaria de la teoría de grafos y hay un teorema que dice que si usted toma la n-ésima potencia de la matriz de adyacencia, el $(i,j)$ entrada se corresponde con el número de paseos de $v_i$ $v_j$con una longitud de $n$.

Hay una forma rápida de calcular que una entrada sin tener que calcular la matriz completa?

Por ejemplo:

$$A = \begin{bmatrix} 0 & 2 & 0\\ 2 & 0 & 1\\ 0 & 1 & 1 \end{bmatrix}$$ and $$A^2 = \begin{bmatrix} 4 & 0 & 2\\ 0 & 5 & 1\\ 2 & 1 & 2 \end{bmatrix}$$

Esto significa que hay 5 caminos de longitud 2 de v2 v2 en el gráfico representado por A.

Hay un método para calcular directamente el $(2,2)$ entrada de $A^2$ sin computar la totalidad de la matriz? ¿Qué otros poderes como $n = 3$ o $n = 4$?

Answer 1

Probablemente desee diagonalize esta matriz.

Entonces $$ \mathbf{A} = \mathbf{P\ D\ P}^{-1} $$ y $$ \mathbf{A}^{k} = \mathbf{P}\ \mathbf{D}^{k}\ \mathbf{P}^{-1} $$

---

Para este problema, la matriz diagonal de los valores propios es $$ \mathbf{D} = \left( \begin{array}{ccc} 2.39138 & 0 & 0 \\ 0 & -2.16425 & 0 \\ 0 & 0 & 0.772866 \\ \end{array} \right) $$

La matriz de vectores propios, y su inversa son, $$ \mathbf{P} = \left( \begin{array}{ccc} 1.16366 & 2.92411 & -0.587772 \\ 1.39138 & -3.16425 & -0.227134 \\ 1 & 1 & 1 \\ \end{array} \right), \qquad \mathbf{P}^{-1} = \left( \begin{array}{rrr} 0.271247 & 0.324327 & 0.233097 \\ 0.149472 & -0.161748 & 0.0511172 \\ -0.420719 & -0.16258 & 0.715786 \\ \end{array} \right) $$

---

Se puede comprobar que $$ \mathbf{D}^{10} = \left( \begin{array}{ccc} 6116.32 & 0 & 0 \\ 0 & 2254.6 & 0 \\ 0 & 0 & 0.0760395 \\ \end{array} \right) $$ y por lo tanto $$ \mathbf{A}^{10} = \mathbf{P}\ \mathbf{D}^{10}\ \mathbf{P}^{-1} = \left( \begin{array}{ccc} 2916 & 1242 & 1996 \\ 1242 & 3914 & 1619 \\ 1996 & 1619 & 1541 \\ \end{array} \right) $$