Power of an adjacency matrix

Question

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?

Answer 1

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

Answer 2

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