# Non-backtracking operator and spectra

Let $$A$$ be the adjacency operator of a symmetric graph $$\Gamma$$. (It may be weighted and/or non-regular, but, to keep it simple, let us say it is unweighted and regular of degree $$d$$.) We want to bound the (non-trivial) eigenvalues of $$A$$. It is then natural to try to bound $$\textrm{Tr} A^{2 k}$$ -- which equals the number of closed paths of length $$2 k$$.

Counting that can be a pain because of backtracking. There is also the option of considering the non-backtracking operator $$H$$ (Hashimoto matrix); the trace of $$H^\ell$$ is precisely the number of non-backtracking closed paths of length $$\ell$$. Counting them is not generally much easier than counting closed paths in general, but it can be cleaner -- and sometimes their number seems to be quite small (whereas the number of closed paths cannot be that small - all walks of length $$2 k$$ induced by trivial words on $$d$$ letters of length $$2 k$$ are closed).

What one can then do is the following. The number of closed paths of length $$2 k$$ -- which equals $$\textrm{Tr} A^{2 k}$$ -- can also be expressed as $$\textrm{Tr} (H+R)^{2 k}$$, where $$R$$ is the edge-reversal operator, i.e., the operator sending an edge $$(v_1,v_2)$$ to $$(v_2,v_1)$$. We can now expand the binomial $$(H+R)^{2 k}$$, and use rules such as $$R H R = H^*$$ (where $$H^*$$ is the adjoint of $$H$$) and $$H^* H = R H (d-2)+ I$$ to simplify. We end up having a linear combination of terms of the form $$\textrm{Tr} H^{\ell}$$, $$\textrm{Tr} R H^{\ell}$$, essentially. Thus we have reduced the problem of bounding $$\textrm{Tr} A^{2 k}$$ to that of bounding $$\textrm{Tr} H^{\ell}$$.

(I suppose this strategy must be extremely well-known. It's more of a mess when the graph is not regular.)

Now, here is the question. What happens if you have a very good bound on $$\textrm{Tr} H^\ell$$ -- say, a bound so small that it is overwhelmed by the contribution of walks coming from trivial words? What sort of extra mileage (on the spectrum of $$A$$?) can one hope to get from such a bound?

• I'm not exactly sure the question, but one can often get a lot of mileage out of the Ihara--Bass formula, which gives a way to map back and forth between the eigenvalues of $A$ and the eigenvalues of $H$. (Several proofs are here -- conservancy.umn.edu/bitstream/handle/11299/3043/1/1459.pdf -- though there are even shorter ones. It is also generalized to graphs with edge weights, even matrix-value edge weights.) This paper gives a good example usage -- arxiv.org/abs/1502.04482. But it's kind of like what you've written in your question. Were you looking for more than this? Aug 31, 2022 at 19:36
• Right - I've glanced at Bordenave's paper, but I guess I am not familiar with how to use the Ihara-Bass formula. In particular, can you use it to bound the eigenvalues of A, either as above or in some other way? My understanding is that Ihara-Bass doesn't really give a direct relation between the spectrum of A and the spectrum of H (see mathoverflow.net/questions/219752/…) - and at any rate the spectrum of H may be the wrong thing to reduce to, as it can be hard to find (H is not normal). Bounding Tr H^{2 k} is easier. Aug 31, 2022 at 22:12
• I think that this article may be useful arxiv.org/abs/2006.13605. Notice that the technique only applies to regular graphs, although one can generalize without much problems to biregular graphs. For general graphs see arxiv.org/abs/1801.00876, but this is more complicated. Sep 1, 2022 at 6:52
• In this one arxiv.org/abs/1801.00876 Bordenave and Collins are interested in the spectra of adjacency matrices of various random models, and they access the whole spectrum through use of Ihara-Bass (ie they prove convergence of spectrum in Hausdorff distance). They comment that using nonbacktracking walk operators is indispensable. Sep 4, 2022 at 13:25