I recently posted this question at math.stackexchange to no avail, so I am posing it here as it pertains to (my) mathematical research.

If $A$ is an $n$-by-$n$ matrix with entries over an arbitrary field and $a_{ij}^{(m)}$ denotes the $(i,j)$-entry of $A^m$, where $m \ge 2$, then a straightforward proof by induction reveals that \begin{equation} \label{ijentryofmatrixpower} a_{ij}^{(m)} = \sum_{k_1,\dots,k_{m-1} = 1}^n \left[ \prod_{\ell = 1}^m a_{k_{\ell-1},k_\ell} \right],~k_0 := i,~k_m :=j. \end{equation}

I have seen this result cited in papers and alluded to in textbooks, but have never seen a proof for it. Is anybody aware of a reference for the result? (To reiterate, I realize the result is not difficult to establish, but it would be nice to be able to point to a reference.)

isthe statement that the entries of the matrix power count the costs of length-$r$ paths in a weighted graph (or maybe exponentials of cost, since we're multiplying weights rather than adding).) $\endgroup$ – LSpice Oct 7 at 18:39shouldn'twrite the proof. I only think that,ifyou want a proof explicitly written out, then you are unlikely to find it (I originally said "unlikely to find it except in a textbook", but, if @RichardStanley's proof is not detailed enough, then I begin to doubt that you will find it in a textbook worth citing), and so are left with only the option of writing it yourself. $\endgroup$ – LSpice Oct 7 at 21:02