-2
$\begingroup$

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

$\endgroup$
  • 6
    $\begingroup$ This is just the definition of matrix multiplication; I wouldn't expect a reference if I read it in a paper. If you really look for a reference, perhaps a textbook where there's a discussion of adjacency matrices, since this formula can be used to count paths of a certain length in a graph? (In fact, I'd argue that this is the 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:39
  • 1
    $\begingroup$ The case when $n=2$ (obviously) corresponds to the definition, but the formula for $n>2$ requires a proof by induction. $\endgroup$ – Pietro Paparella Oct 7 at 19:23
  • 1
    $\begingroup$ Since you have stated that you wish to have a fully explicit proof, not just a reference to the fact, and since the opinion of such an eminence as @RichardStanley that this need not be written out in more detail than he does suggests that it might be hard to find it written out in as detailed a form as you want in a reputable reference, it sure seems that the easiest thing to do would be just to write the (easy, short) proof. $\endgroup$ – LSpice Oct 7 at 20:47
  • 2
    $\begingroup$ To be clear, I think you shouldn't write the proof. I only think that, if you 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
  • 3
    $\begingroup$ It is a partial case of the formula for the entries of the product of several matrices like $[A_1A_2\ldots A_m]_{i,j}=\sum_{k_1,\ldots,k_{m-1}} [A_1]_{i,k_1}[A_2]_{k_1,k_2}\ldots [A_m]_{k_{m-1},j}$ which is even a more straightforward corollary of the matrix multiplication definition. I support other comments here that such things should not be proved: everybody who is able to understand the proof does not need it. $\endgroup$ – Fedor Petrov Oct 7 at 22:32
5
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I disagree; the formula merits a proof. $\endgroup$ – Pietro Paparella Oct 7 at 19:46
  • 1
    $\begingroup$ Well, in any case Stanley gives one. $\endgroup$ – Qiaochu Yuan Oct 7 at 19:50
  • $\begingroup$ "The proof is immediate from the definition of matrix multiplication" is not a proof. $\endgroup$ – Pietro Paparella Oct 7 at 19:59
  • 3
    $\begingroup$ To be clear, I said this how the proof begins. Stanley then gives a proof after that sentence, although admittedly it is very short and maybe less detailed than you would like. $\endgroup$ – Qiaochu Yuan Oct 7 at 20:06
  • $\begingroup$ I looked it up; he does not. He simply states the formula after that sentence that you quoted. I understand that it is simple. I understand that it follows from matrix multiplication. But it still requires proof. $\endgroup$ – Pietro Paparella Oct 7 at 20:08
0
$\begingroup$

Here is the screenshot from Stanley's book. enter image description here

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

| cite | improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ I would argue that the base case should be $n = 0$ (or $n = 1$ if you don't like to discuss paths of length $1$, but I'd argue that stating the result in such a way that it applies to $n = 0$—as I guess that Stanley does, although I don't see the definition of $A_{i j}(n)$—is part of properly formulating it). One advantage would be that you don't need to use the definition of matrix multiplication twice (once for the base case, and once for the inductive step). $\endgroup$ – LSpice Oct 8 at 3:21
  • $\begingroup$ Indeed; but with the way I wrote the formula, the indices in the summation run from 1 to $m-1$. $\endgroup$ – Pietro Paparella Oct 8 at 14:13
  • 1
    $\begingroup$ (I got $m$ and $n$ mixed up, sorry.) This point is why I mentioned that stating the result in such a way that it clearly works for $m = 0$ and $m = 1$ is probably good practice; but notice that it does work exactly as written, as long as one is careful about interpretation. For $m = 0$ or $m = 1$ you are summing over empty tuples, of which there is a unique one; for $m = 0$ the summand is the empty product, which is $1$; and for $m = 1$ the summand is the product of the single term $a_{ij}$. $\endgroup$ – LSpice Oct 8 at 14:20
  • $\begingroup$ Gosh, it almost seems like, from our discussion, that a proof is warranted after all. ¯_(ツ)_/¯ $\endgroup$ – Pietro Paparella Oct 8 at 15:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.