Given $A$, is there a quick way to compute the $(i,j)$th entry of $A^n$ I am studying elementary graph theory and there is a theorem which states that if you take the nth power of the adjacency matrix, the $(i,j)$ entry corresponds to the number of walks from $v_i$ to $v_j$ with length $n$.
Is there a quick way to compute that one entry without having to compute the whole matrix?
For example:
$$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}$$
This means that there are 5 walks of length 2 from v2 to v2 in the graph represented by A.
Is there a method to directly compute the $(2,2)$ entry of $A^2$ without computing the whole matrix? What about other powers like $n = 3$ or $n = 4$?
 A: Probably want to diagonalize this matrix.
Then 
$$
 \mathbf{A} = \mathbf{P\ D\ P}^{-1}
$$
and 
$$
 \mathbf{A}^{k} = \mathbf{P}\ \mathbf{D}^{k}\ \mathbf{P}^{-1}
$$

For this problem, the diagonal matrix of eigenvalues is
$$
\mathbf{D} = 
\left(
\begin{array}{ccc}
 2.39138 & 0 & 0 \\
 0 & -2.16425 & 0 \\
 0 & 0 & 0.772866 \\
\end{array}
\right)
$$

The matrix of eigenvectors, and its inverse are,
$$
\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)
$$

You can check that
$$
 \mathbf{D}^{10} = 
\left(
\begin{array}{ccc}
 6116.32 & 0 & 0 \\
 0 & 2254.6 & 0 \\
 0 & 0 & 0.0760395 \\
\end{array}
\right)
$$
and therefore
$$
 \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)
$$
