Discrete trace formulas and holomorphic functional calculus for the adjacency matrix of regular graphs

This paper introduces a unified framework utilizing holomorphic functional calculus on a specific ellipse to expand the adjacency matrix of regular graphs in terms of non-backtracking matrices, thereby deriving discrete trace formulas that connect spectral theory with graph combinatorics and offering new proofs for problems such as walk counting, the Ihara-Bass formula, and graph-based heat and Schrödinger equations.

The Gist

Imagine a city made entirely of intersections (vertices) connected by one-way streets (edges). In mathematics, this is called a graph. Now, imagine that every intersection in this city has exactly the same number of roads leading out of it. This is a regular graph.

The authors of this paper, Gong, Li, and Liu, have built a new "universal translator" to understand these cities. Their goal is to connect two very different ways of looking at the city:

1. The Spectral View: Looking at the city through the lens of its "vibrations" or frequencies (mathematically, the eigenvalues of the adjacency matrix).
2. The Walking View: Counting the actual paths people can take through the streets.

Here is a simple breakdown of their discovery using everyday analogies.

1. The Problem: The "Backtracking" Mess

If you ask, "How many ways can I walk from Intersection A to Intersection B in 10 steps?" the answer is usually a huge, complicated number. Why? Because most of those walks involve backtracking.

• Backtracking: You walk down a street, realize you made a mistake, and immediately turn around to go back the way you came.
• The Mess: In a large city, the number of these "go-forward-then-go-back" paths is overwhelming and messy. It's like trying to count every single step a person takes while wandering aimlessly in a fog.

The authors focus on Non-Backtracking Walks. These are paths where you never immediately turn around. You walk forward, turn left, turn right, but you never do a U-turn on the very next step.

• The Analogy: Think of a tourist who is determined to see new sights and refuses to retrace their immediate steps. Their path is much "cleaner" and easier to track.

2. The Solution: A Special "Translator" (Holomorphic Functional Calculus)

The authors use a sophisticated mathematical tool called holomorphic functional calculus.

• The Metaphor: Imagine you have a complex machine (the graph's adjacency matrix) that processes data. Usually, to understand what the machine does with a specific input (like a heat equation or a wave), you have to solve a difficult puzzle.
• The Innovation: The authors found a way to "plug in" any smooth, well-behaved function (like a wave or a heat pattern) directly into the machine using a special ellipse in the mathematical landscape.
• The Result: Instead of getting a messy, unsolvable equation, their method expands the answer into a neat, infinite series of Non-Backtracking Matrices.

Think of it like this: Instead of trying to describe a chaotic crowd by tracking every single person's erratic movements, they realized that if you only track the people walking in a straight line without doubling back, you can perfectly reconstruct the behavior of the whole crowd.

3. The Core Discovery: The Trace Formulas

The paper derives what they call Discrete Trace Formulas.

• The Concept: A "trace" in math is like taking a snapshot of the whole system.
• The Formula: They proved that the total "vibration" or "energy" of the graph (the sum of its eigenvalues) is directly equal to the number of closed non-backtracking loops (paths that start and end at the same place without U-turning).
• The Analogy: Imagine a drum. The sound it makes (its spectrum) is determined by the shape of the drum skin. The authors found a way to calculate the sound of the drum simply by counting how many distinct, non-repeating loops a drummer could trace on the skin without lifting their stick.

4. What They Proved (The Applications)

Using this new "translator," the authors re-proved several famous results in a unified, simpler way. They didn't invent new physics, but they showed that these different problems are actually the same puzzle seen from different angles.

• Counting Walks: They gave a new, clean formula to count how many ways you can walk from point A to point B, by converting the messy "general walks" into "non-backtracking walks."
• The Heat Equation: This models how heat (or a rumor) spreads through the graph. They showed that the spread of heat can be calculated by summing up the contributions of these clean, non-backtracking paths.
• The Schrödinger Equation: This models quantum particles moving on the graph. Again, the complex quantum behavior is revealed to be a sum of these simple, non-backtracking paths.
• The Ihara-Bass Theorem: This is a famous relationship between the graph's structure and its "zeta function" (a number that encodes the graph's loops). The authors showed this famous theorem is just a natural consequence of their new formula when applied to logarithms.

5. The "Infinite" City

A unique feature of their work is that it works not just for small, finite cities, but for infinite ones (like an endless grid or an infinite tree).

• The Metaphor: Usually, math breaks down when things get infinite. But because they used this specific "ellipse" and "non-backtracking" approach, their formulas hold true even if the city stretches on forever.

Summary

The paper is essentially a unified theory of graph movement.

• Old Way: Try to count every possible path, get bogged down in backtracking, and struggle to connect it to the graph's vibrations.
• New Way (This Paper): Ignore the backtracking. Focus only on the "forward-moving" paths. Use a special mathematical lens (holomorphic calculus) to show that these clean paths perfectly explain the graph's vibrations, heat flow, and quantum behavior.

They didn't just solve one problem; they built a single framework that solves counting, heat flow, and quantum mechanics on graphs all at once, proving that the "soul" of a graph is hidden in its non-backtracking loops.

Technical Summary

Technical Summary: Discrete Trace Formulas and Holomorphic Functional Calculus for Regular Graphs

Problem Statement
The spectral theory of regular graphs is fundamentally linked to the combinatorics of walks on the graph. While the trace method relates the spectrum of the adjacency matrix $A$ to the total number of closed walks, general walks are often too complex to analyze directly due to the presence of backtracking. Non-backtracking walks offer a "simpler" combinatorial structure, playing a crucial role in the study of Ramanujan graphs and the second eigenvalue conjecture. However, existing discrete trace formulas on regular graphs (analogous to Selberg's trace formula on hyperbolic surfaces) have historically been restricted to functions constructed from rotation-invariant functions on regular trees. This limitation hinders the application of trace formulas to arbitrary analytic functions of the adjacency matrix.

Methodology
The authors propose a unified framework based on holomorphic functional calculus applied to the adjacency matrix $A$ of a $(q+1)$-regular graph (including infinite graphs). The core methodology involves:

1. Chebyshev-type Polynomials: The authors utilize a specific family of polynomials, $X_{r,q}(x)$, which are intrinsically related to non-backtracking matrices $A_r$. A key combinatorial identity established by Friedman is utilized: $A_r = q^{r/2} X_{r,q}(q^{-1/2}A)$.
2. Joukowsky Transform and Domain $\Omega(\rho)$: The analysis is conducted within a specific domain $\Omega(\rho)$ in the complex plane, defined as an ellipse containing the spectrum of the normalized adjacency matrix $q^{-1/2}A$. This domain is the image of an annulus under the Joukowsky transform $J(z) = z + z^{-1}$.
3. Holomorphic Expansion: By applying Cauchy's integral formula, any function $h$ holomorphic on $\Omega(\rho)$ is expanded into a series of Chebyshev-type polynomials $X_{r,q}$. The coefficients of this expansion are derived using the orthogonality of these polynomials with respect to the Kesten-McKay distribution $\mu_q$ (the spectral measure of the infinite $(q+1)$-regular tree).
4. Functional Calculus: This expansion is applied directly to the operator $q^{-1/2}A$, yielding an expansion of $h(q^{-1/2}A)$ in terms of the non-backtracking matrices $A_r$.

Key Contributions and Results

• Functional Calculus Formula (Theorem A): The paper establishes a general formula for $h(q^{-1/2}A)$ for any function $h$ holomorphic on $\Omega(\rho)$. The formula expresses the operator as a constant term (involving the Kesten-McKay distribution) plus an infinite series of non-backtracking matrices weighted by coefficients determined by the integral of $h$ against the polynomials $X_{r,q}$.
• Discrete Pre-Trace Formula (Theorem B): By evaluating the functional calculus formula at a specific vertex $v$, the authors derive a pre-trace formula. This links the integral of $h$ against the normalized spectral measure at a vertex, $\mu_v^G$, to the number of closed non-backtracking walks starting and ending at $v$.
• Discrete Trace Formula (Theorem C): For finite graphs, summing the pre-trace formula over all vertices yields a trace formula. This relates the sum of $h$ evaluated at the eigenvalues of the graph to the number of circuits (closed non-backtracking walks where the last edge is not the inverse of the first).
  • The authors reformulate this using equivalence classes of prime circuits, creating a formula that structurally resembles Selberg's trace formula on hyperbolic surfaces.
• Unification of Classical Results: The framework provides new, elementary proofs and derivations for several known results:
  • Walk Counting: A formula expressing the total number of walks in terms of non-backtracking walks.
  • Ihara-Bass Theorem: A derivation of the relationship between the Ihara zeta function and the determinant of the adjacency matrix by applying the trace formula to the logarithm function.
  • Heat and Schrödinger Equations: Explicit fundamental solutions for the heat and Schrödinger equations on regular graphs and lattices are derived in terms of non-backtracking matrices and Bessel functions.
  • Fourier-Laplace Transform: A formula for the Fourier-Laplace transform of the spectral measure is obtained, linking it to the number of circuits.

Significance
The paper claims that its primary significance lies in providing a unified method to study the adjacency matrices of regular graphs. By generalizing previous trace formulas (which were limited to specific classes of functions derived from tree geometry) to any function holomorphic on a specific ellipse, the authors enable the systematic application of spectral theory to a broader class of combinatorial problems.

The framework bridges the gap between spectral theory and graph combinatorics by systematically linking the spectrum to non-backtracking walks and circuits. It demonstrates that seemingly disparate results—ranging from the counting of walks on lattices to the Ihara-Bass theorem and solutions to differential equations on graphs—can be derived from a single functional calculus principle. The authors emphasize that this approach avoids the need to explicitly construct functions from rotation-invariant functions on trees, thereby broadening the practical utility of discrete trace formulas.