<s>[INST] Why do diagonal entries of odd potencies of adjacency matrices of forests sum up to zero? I came across the statement that the trace (sum of diagonal entries) of an odd potency of an adjacency matrix of a forest is always zero. I have tried out a few options and it seems to be correct for forests or trees but not for other graphs, e.g.:
$A = \begin{bmatrix} 0 & 1 & 0 & 1 & 1 \\ 1 & 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 \\1 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 \end{bmatrix}$ and $A^3 = \begin{bmatrix} 0 & 4 & 0 & 3 & 3 \\ 4 & 0 & 2 & 0 & 0 \\ 0 & 2 & 0 & 1 & 1 \\ 3 & 0 & 1 & 0 & 0 \\ 3 & 0 & 1 & 0 & 0 \end{bmatrix}$
While if I add one edge to create a circle:
$B = \begin{bmatrix} 0 & 1 & 1 & 1 & 0 \\ 1 & 0 & 1 & 0 & 0 \\ 1 & 1 & 0 & 0 & 0 \\1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \end{bmatrix}$ and $B^3 = \begin{bmatrix} 2 & 4 & 4 & 3 & 0 \\ 4 & 2 & 3 & 1 & 0 \\ 4 & 3 & 2 & 1 & 0 \\ 3 & 1 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \end{bmatrix}$
Can someone explain to me why this is the case?
 [/INST] If $A$ is the adjacency matrix of a graph, then $A^n_{ij}$ counts the number of paths of length $n$ from vertex $i$ to vertex $j$.  If you are in a forest, because there are no cycles, every step along a path is either one step closer or one step father away from any particular vertex.  Because of this, if we start at vertex $i$, we will alternate between an even distance away and an odd distance away.  In particular, at odd times, we are an odd distance away, and therefore NOT back at our starting point.  So all the diagonal entries of $A^n$ are $0$ when $n$ is odd.
</s>