Skip to main content
1 of 2
Sam Hopkins
  • 24.2k
  • 5
  • 97
  • 171

Computing adjacency matrix eigenvalues by counting closed walks

Let $G$ be a finite undirected graph. A closed walk in $G$ is a walk from any vertex of $G$ to itself. It is relatively straightforward to show that the total number of closed walks of length $k$ in $G$ is: $$ \lambda_1^k + \lambda_2^k + \cdots + \lambda_n^k,$$ where $\lambda_1,\ldots,\lambda_n$ are the eigenvalues of the adjaceny matrix of $G$, with mutliplicity.

Often this is thought of as a way to count walks using linear algebra, but in principle it is possible to apply this result "in the other direction" and compute the eigenvalues of the adjacency matrix of $G$ by counting closed walks via some other (e.g., direct combinatorial) argument.

For example, it is possible to find the eigenvalues of the adjacency matrix of the hypercube graph this way (see Stanley, "Enumerative Combinatorics," Vol. 1, 2nd Edition, Chapter 4 Exercise 68; see also Number of closed walks on an $n$-cube and https://math.stackexchange.com/a/3328904/79593). Even simpler would be the case of the complete bipartite graph (ibid. Exercise 69). And for the complete graph this is almost trivial.

Question: Are there some other nice examples of (families of) graphs whose adjacency matrix eigenvalues can be computed via combinatorial walk counting? Especially, are there any graphs where this is the only known way to find a formula for the adjacency matrix eigenvalues?

Sam Hopkins
  • 24.2k
  • 5
  • 97
  • 171