Formula for the entry of a matrix power [closed]

Question

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. \tag{1} \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.)

EDIT:

\begin{rant}

In the original post, I simply asked for a reference for formula \ref{ijentryofmatrixpower} above, but many have opined below that neither a proof or reference is necessary. I disagree, and I would like to give an argument as to why.

As with every mathematical statement, there are two possibilities:

1. Formula \ref{ijentryofmatrixpower} is taken as axiomatic, in which case, there is obviously nothing to prove because it is accepted as true.
2. Matrix multiplication and exponentiation is defined, per the norm. In this case, it is inescapable that \ref{ijentryofmatrixpower} requires a proof.

Several commenters in this thread mention a textbook by the "eminent" Richard Stanley, who offers the following proof:
If we appeal to authority, as others in this post have, then, since Stanley offers a proof, it is clear then that he takes the position that the statement requires a proof!

Here's another consideration that supports a proof: everyone on this post is a professional, seasoned mathematician, but not everyone reading a paper or textbook is. I agree that a proof isn't necessary if this is the only constituency in my audience; however, this is obviously never the case and, in the interest of inclusion, it is a terrible practice to simply state that the result is "obvious" or follows "immediately" from the definition.

Here's another viewpoint: suppose, as an educator, that you include this problem in an examination or assignment. Would you be comfortable giving full-credit to a student stating that the result "is immediate from the definition of matrix multiplication" or "this doesn't need a proof"? The answer is obviously "no" and it is hypocritical not to hold ourselves to the same standards that we expect of our students.

\end{rant}

Answer 1

I agree with LSpice that I don't think this really needs a proof or a citation, but in combinatorics this sort of thing is often called "the transfer matrix method" and accordingly it is stated in combinatorics texts, e.g. it is Theorem 4.7.1 in Stanley's Enumerative Combinatorics, Vol. I (the proof begins "The proof is immediate from the definition of matrix multiplication").

Note that "arbitrary field" can be replaced with "arbitrary semiring"; Stanley states the result for a commutative ring.

Answer 2

Here is the screenshot from Stanley's book.

Ironically, providing a proof would have been just as long (or short) as what he wrote:

Proceed by induction on $n$. The base-case corresponds with the definition of matrix-multiplication.

If the result holds when $m \ge 2$, then \begin{align} a_{ij}^{m+1} &= \sum_{k=1}^n a_{ik}^{(m)} a_{kj} \tag{matrix mult.} \\ &= \sum_{k=1}^n \left( \sum_{k_1,\dots,k_{m-1} = 1}^n \left[ \prod_{\ell = 1}^m a_{k_{\ell-1},k_\ell} \right] \right) a_{kj} \tag{IH} \\ &= \sum_{k_1,\dots,k_{m} = 1}^n \left[ \prod_{\ell = 1}^{m+1} a_{k_{\ell-1},k_\ell} \right], \end{align} after relabeling $k$ as $k_m$.