9
$\begingroup$

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

$\endgroup$
2
  • 1
    $\begingroup$ This idea might go back further than the definition of matrix product in its modern form, which makes it very hard to track down. (This is true, for example, of Kirchhoff's original version of the matrix-tree theorem, which - in 1847 - predates the modern notions of both matrices and trees.) $\endgroup$
    – Misha Lavrov
    Commented Oct 29, 2022 at 20:38
  • 1
    $\begingroup$ That being said, I did not encounter powers of the adjacency matrix in König's Theorie der endlichen und unendlichen Graphen, which in 1936 was the first textbook on graph theory. So it's possible that this fact is more recent. $\endgroup$
    – Misha Lavrov
    Commented Oct 29, 2022 at 20:45

1 Answer 1

Reset to default
3
$\begingroup$

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:

It is apparent that these matrices may also be raised to higher powers to obtain the four-step or five-step or even more indirect connections among the members of a group.

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:

In $X^n$ the entry ${x_{ij}}^{(n)} = c$ if and only if there are $c$ distinct $n$-chains from $i$ to $j$ (for proof see §5.04). Thus, if in the fifth power of a matrix of data $X$ we find that the number of $9$ occurs in the third row of the seventh column, we may conclude that there are $9$ distinct $5$-chains from element $3$ to element $7$.

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:

  • König's 1936 textbook Theorie der endlichen und unendlichen Graphen, which does define adjacency matrix of graphs, and presents several results on the determinants of the adjacency matrix, but does not even consider products or powers of these matrices. I consider the result on counting walks simpler and more likely to appear in a textbook, so this is some evidence that it was not yet known to graph theorists in 1936.
  • Berge's Graphs and Hypergraphs (I read the 1973 translation of the French textbook published in 1970) gives the following in Chapter 4, Section 5 (Counting paths):

Corollary 1. If $G$ is a graph and $A$ is its associated matrix, the general coefficient $p^i_j$ of the matrix $P = A^k$ (the product of $A$ with itself $k$ times) equals the number of distinct paths of length $k$ from $x_i$ to $x_j$ in $G$.

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.

$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .