Power of an adjacency matrix For any graph $\mathcal{G}$, what do the powers of its adjacency matrix $A$ represent? As an example, what does element (u, v) of matrix $A^2$ correspond to?
 A: The $uv$-entry of the $k$-th power $A^k$ counts the number of walks of length $k$ from the vertex $u$ to the vertex $v$. (This can be proved by induction on $k$.)
When $k=2$ you get the number of common neighbours of $u$ and $v$.
A: Just to concur with Chris Godsil, I think the following can also help
Let $ X $ be a directed graph with adjacency matrix $ A $. Then the number of walks from $ u $ to $ v $ with length  $ r $ is $ (A^{r})_{uv} $.
To do this proof we also need counting principles which are the 
Product Rule of Counting : If a job of size $ k=t+p $ can be done in $ m $ ways to finish size $ t $,  and then $ n  $ ways to finish size $ p $, then there are $ mn $ ways of doing this job. 
Sum Rule Counting: If a person can do either job $ A $ in $ m $ times or job $B $ in $ n $ times but can not do both at the same time, then there are $ m+n $ ways of doing either of the jobs.
Suppose $ r=1 $, then $(A^{1})_{ij}= e^{T} _{i} A e_{j} =  \left\{ \begin{array}{ll} 
\displaystyle 1 &,  uv \, is \,  an \, edge \\
\displaystyle 0 &, otherwise 
\end{array} \right. $ 
 But the edge $ uv $ is a $ u-v $ walk of length $ 1 $, hence the lemma holds when $ r=1 $
We now assume that $ (A^{r})_{u _{i} v_{j}}=a_{ij} $ is the number $ u _{i} - v_{j} $ walks of length $r$. Let $ A=[b_{ij}] $.
Hence, by this assumption,  for each $ k=1,2,3,..., n $,  $ a_{ik} $ is the number of $ u _{i} - v_{k} $ of length $ r $ and $ b_{kj} $  is the number of $ u _{k} - v_{j} $ of length $ 1 $ by the same assumption.  
Hence, by product rule of counting,  $a_{ik} b_{kj} $, is the number of $ u _{i} - v_{j} $ walks of length $ k+1 $ for each $ k=1,2,3,...n $.
Hence, by sum rule of counting there are $ \displaystyle \sum _{k=1} ^{n}  a_{ik} b_{kj}$  paths ( $ u _{i} - v_{j} $ paths centered at either of the $ k' $s, $ k=1,2,3,...,n $) of length $ r+1 $.
But  $ \displaystyle \sum _{k=1} ^{n}  (A^{r})_{ik} A_{kj} = (A^{r}A)_{ij}=(A^{r+1})_{ij}$
