graph theorymatricesproof-writing
Let A be an adjacency matrix of a graph $G$. Prove that the $(i, j)^{th}$ entry of $A^2$ is the number of paths of length $2$ between vertex $i$ and vertex $j$.
*I know the adjacency matrix will be a square matrix.
I would appreciate any help explaining this problem and advice of where to begin this proof.
The adjacency matrix does not calculate the number of $k$-length paths in a graph. It calculates the number of $k$-length walks from one vertex to another. (More specifically, the entries of the $n$th power of the adjacency matrix encodes the number of walks). To see the difference between paths and walks, consider any two adjacent vertices not part of a cycle. Then there is exact one path between the two vertices i.e. the edge between them, but there exists an infinite number of walks between them. For example $v_1 \rightarrow v_2 \rightarrow v_1 \rightarrow v_2$ is a walk from $v_1$ to $v_2$ of length $3$. Specifically, paths do not allow repetition of vertices while walks do, therefore this does not in general aid in the computation of Hamiltonian paths or indeed, paths of arbitrary lengths.
There doesn't seem to be a simple expression involving the adjacency matrix for the number of simple (i.e. self-avoiding) paths in an arbitrary graph, but there is an algorithm.
Googling "adjacency matrix number of paths" turned up this SE question which points out (with a nice example) that powers of the adjacency matrix count the number of walks of length $n$, not paths. That fact also turned up in this wikipedia entry. These walks allow a vertex to be visited more than once, so it's unlikely they can help you to count simple paths.
The paper Self-Avoiding Paths and the Adjacency Matrix of a Graph - J. Ponstein contains an algorithm on pages 9-10 which counts all simple paths in an arbitrary graph.
Edit: The good news is explicit formulae for the paths of length $n$ exist, the bad news is the number of terms in the formulae grow exponentially with $n$!
The paper On the determination of redundancies in sociometric chains - Ross, Ian C.; Harary, Frank counts the number of 'redundant paths' (i.e. non-simple paths, walks of length $n$ where a vertex is visited more than once).
The English language powerpoint slideshow of the Russian language paper "The number of fixed length cycles in an undirected graph. Explicit formulae in case of small lengths" by S. N. Perepechko & A. N. Voropaev contains formula for path lengths 2-5 using the Ross & Harary method. I reproduce, for your delectation or horror, 2 of the 17476 terms from the path length 10 formula ($\times$ is element-wise matrix multiplication, $\cdot$ is ordinary matrix multiplication):
Best Answer
The number of paths of length $2$ from $u$ to $v$ is equal to the sum over $w\in V$ of all the ways to get from $u$ to $w$ multiplied by all the ways to get from $w$ to $v$, in one step. So it is the sum over $w\in G$ of $A_{u,w}A_{w,v}$. This is exactly $A^2_{uv}$.