The Wikipedia article on powers of an adjacency matrix presently (as of 2022) notes the neat combinatorial fact that, given an adjacency matrix $A$ of some graph, entries of the $n$th power of the adjacency matrix, $A^n_{ij}$, count the number of $n$-length walks from $i$ to $j$. The Wikipedia article further relates this to the problem of counting the number of triangles in said graph by dividing the trace of $A^3$ by $6$, and determining the distance between two nodes in an undirected, unweighted graph.
The Wikipedia article does not name these as lemmas or theorems or corollaries, and states them with only the briefest outline of the proof.
Are these folk results, or is there any other interesting history behind who first formulated and proved them?
These are very nice and fun statements to prove, but I'm curious to know if there's anything else to say about their history.
(I am especially interested in how quantum computers could efficiently explore spectral properties of certain large adjacency matrices of certain large graphs, as, by linearity, exponentiation of the spectrum corresponds to exponentiation of the given adjacency matrix – which then corresponds to counting various walks on the graph.)
Best Answer
In 1949, social psychologist Leon Festinger and mathematicians R. Duncan Luce and Albert Perry (all working together) published papers introducing the idea in application to social psychology.
They divide this into two papers. One, more sociological, is The analysis of sociograms using matrix algebra by Festinger. This one carefully explains how matrix multiplication works for $A^2$, then does the whole thing again for $A^3$, then finally remarks:
The second paper is A method of matrix analysis of group structure by Luce and Perry. This one presents the result more abstractly and gives a proof. Paragraph 3.01 states:
Some results later on in the paper also mention something about the diagonal entries of the cube of the matrix, which ought to count triangles, but the results are confusingly phrased.
It is, of course, possible that matrix powers of graphs were known to graph theorists before they were known to sociologists, but I don't have any evidence of this. Bracketing the time window above from both sides, we have:
It would be interesting to see if Berge's 1958 book Théorie des graphes et ses applications contains this result, but I've been unable to check.