betaFeedback

WorksMathematics

The real eigenvalues of the non-backtracking Laplacian

Abstract

Let GG be a simple graph on NN nodes and MM edges, with minimum degree at least 22. We prove that the non-backtracking Laplacian of GG has at least 2M−2N+2c+2b2M-2N+2c+2b real eigenvalues, counted with algebraic multiplicity, where cc is the number of connected components of GG and bb is the number of bipartite ones. More precisely, at least M−N+2cM-N+2c of them lie in [0,1)[0,1) and at least M−N+2bM-N+2b lie in (1,2](1,2]. We show that the bound 2M−2N+2c+2b2M-2N+2c+2b is sharp, and that a connected dd-regular graph attains it if and only if it is strictly Ramanujan, i.e., every adjacency eigenvalue μ≠±dμ\ne\pm d satisfies ∣μ∣<2d−1|μ|<2\sqrt{d-1}. For completeness, we also show that the non-backtracking Laplacian has at most 2M−2c−2b2M-2c-2b real eigenvalues.

Introduction

While most of the spectral theory of simple graphs concerns symmetric matrices, such as the adjacency matrix and the graph Laplacians (we refer to [10, 8, 18] for three monographs), a growing body of work is devoted to non-symmetric operators, and in particular to non-backtracking operators. The eigenvalues of these operators are in general complex, and even a basic question such as how many of them are real is often difficult to answer.

Non-backtracking operators first appeared in 1989 in the work of Hashimoto [16], in the context of zeta functions of graphs, and they have since proved useful in many areas, including algebraic graph theory [30, 4, 11], the study of Ramanujan graphings [3], epidemic spreading [29, 9], community detection [20, 7, 6], and centrality measures [22, 31]. We refer to [32, 12, 13, 28, 1, 2, 15, 23, 5] for further results on non-backtracking operators and their applications.

The idea behind these operators is to study walks on a graph that are never allowed to return along the edge they have just traversed. More precisely, let G=(V,E)G=(V,E) be a simple graph on NN nodes and MM edges, with minimum degree at least 22. Each edge of GG admits two orientations, and we write [v,w][v,w] for the oriented edge with input in⁡([v,w]):=v\operatorname{in}([v,w]):=v and output out⁡([v,w]):=w\operatorname{out}([v,w]):=w. Its inverse is [v,w]−1:=[w,v][v,w]^{-1}:=[w,v]. This gives 2M2M oriented edges, which we label as e1,…,e2Me_1,\ldots,e_{2M} in such a way that

eM+i=ei−1,for i=1,…,M.e_{M+i}=e_i^{-1}, \qquad\text{for } i=1,\ldots,M.

A non-backtracking random walk on GG is a discrete-time Markov process on the oriented edges such that the probability of going from eie_i to eje_j is

P(ei→ej)={1deg⁡(out⁡(ei))−1if out⁡(ei)=in⁡(ej) and ej≠ei−1,0otherwise.\mathbb{P}(e_i\to e_j)= \begin{cases} \frac{1}{\deg(\operatorname{out}(e_i))-1} & \text{if }\operatorname{out}(e_i)=\operatorname{in}(e_j)\text{ and }e_j\ne e_i^{-1},\\ 0 & \text{otherwise.} \end{cases}

In particular, the assumption that GG has minimum degree at least 22 guarantees that the denominator is always positive. Moreover, one can also see a non-backtracking random walk as a process on VV, but in this case the probability that the walker moves from a vertex vv to one of its neighbors depends on the vertex she came from. Hence, this process is not Markovian on VV.

Non-backtracking random walks are encoded by the non-backtracking graph or Hashimoto graph of GG, denoted G\mathcal{G}, which is the directed graph whose vertices are the 2M2M oriented edges of GG, and which has a directed edge from eie_i to eje_j if and only if

out⁡(ei)=in⁡(ej) and ej≠ei−1,\operatorname{out}(e_i)=\operatorname{in}(e_j)\text{ and }e_j\ne e_i^{-1},

i.e., if and only if a non-backtracking random walk can go from eie_i to eje_j in one step. The adjacency matrix of G\mathcal{G} is the 2M×2M2M\times2M matrix AA with (0,1)(0,1)-entries such that

Aij=1⟺out⁡(ei)=in⁡(ej) and ej≠ei−1,A_{ij}=1\Longleftrightarrow\operatorname{out}(e_i)=\operatorname{in}(e_j)\text{ and }e_j\ne e_i^{-1},

and its transpose A⊤A^\top is the non-backtracking matrix of GG introduced by Hashimoto [16]. Moreover, a random walk on G\mathcal{G} is precisely a non-backtracking random walk on GG. Since each vertex eie_i of G\mathcal{G} has (out-)degree

deg⁡G(ei)=deg⁡(out⁡(ei))−1≥1,\deg_{\mathcal{G}}(e_i)=\deg(\operatorname{out}(e_i))-1\ge1,

the random walk Laplacian of G\mathcal{G} is well-defined, and it is called the non-backtracking Laplacian of GG. It can be written as

L:=Id−D−1A=Id−T,\mathcal{L}:=\mathrm{Id}-\mathcal{D}^{-1}A=\mathrm{Id}-\mathcal{T},

where Id\mathrm{Id} denotes the identity matrix, D\mathcal{D} is the degree matrix of G\mathcal{G} and has diagonal entries

Dii:=deg⁡G(ei),D_{ii}:=\deg_{\mathcal{G}}(e_i),

and T:=D−1A\mathcal{T}:=\mathcal{D}^{-1}A is the transition probability matrix of the non-backtracking random walk on G\mathcal{G}.

We introduced the non-backtracking Laplacian in [17], together with J. Jost. Its spectral properties were further investigated in [26], its connection to graph colorings was studied in [24], and it has been applied to vertex clustering in [6]. The computations in [17 Table 2] showed that, among graphs with at most ten nodes and minimum degree at least 2, substantially fewer graphs admit a cospectral mate for the non-backtracking Laplacian than for the other operators considered; that is, there are fewer pairs of non-isomorphic graphs with the same L\mathcal{L} spectrum. Moreover, in the same paper we showed that the presence of certain cycle configurations produces real eigenvalues of L\mathcal{L}.

For the non-backtracking matrix, the Ihara–Bass formula [4, 30, 19],

det⁡(Id⁡−uA)=(1−u2)M−Ndet⁡(Id⁡−uA+u2(D−Id⁡)),(1)\det(\operatorname{Id}-uA)=(1-u^2)^{M-N}\det(\operatorname{Id}-uA+u^2(D-\operatorname{Id})), \tag*{(1)}

where AA and DD are the adjacency and degree matrices of GG, gives at least 2M−2N2M-2N real eigenvalues for each of A\mathcal{A} and AT\mathcal{A}^{\mathsf{T}}, counted with algebraic multiplicity. If GG is dd–regular, then

L=Id⁡−1d−1A.\mathcal{L}=\operatorname{Id}-\frac{1}{d-1}\mathcal{A}.

Therefore, in this case, L\mathcal{L} also has at least 2M−2N2M-2N real eigenvalues, counted with algebraic multiplicity. For irregular graphs, however, degree normalization does not act by a scalar rescaling, and the Ihara–Bass formula does not directly give a corresponding lower bound for L\mathcal{L}. It is therefore natural to ask whether the lower bound 2M−2N2M-2N nevertheless holds for the non-backtracking Laplacian. Motivated by numerical experiments, we conjectured in 2022 that L\mathcal{L} always has at least 2M−2N2M-2N real eigenvalues, counted with algebraic multiplicity. We formulated this conjecture during our course on non-backtracking operators of graphs at the Max Planck Institute for Mathematics in the Sciences, and it was later stated as an open problem in [25 Exercise 13].

Here we prove this conjecture, and we refine it as follows.

Theorem (Theorem 4.1 and Corollary 5.2). Let GG be a simple graph on NN nodes and MM edges, with minimum degree at least 2. Let cc be the number of connected components of GG, and let bb be the number of bipartite ones. Then, the number of real eigenvalues of the non-backtracking Laplacian of GG, counted with algebraic multiplicity, is at least

2M−2N+2c+2b.2M-2N+2c+2b.

Moreover, this bound is sharp.

For connected regular graphs, we also determine exactly when the above bound is attained. Recall that a connected dd–regular graph is Ramanujan [21, 27] if every adjacency eigenvalue μ≠±d\mu\ne\pm d satisfies

∣μ∣≤2d−1.|\mu|\le2\sqrt{d-1}.

We call it strictly Ramanujan if every adjacency eigenvalue μ≠±d\mu\ne\pm d satisfies

∣μ∣<2d−1.|\mu|<2\sqrt{d-1}.

We show that, for a connected regular graph GG, the non-backtracking Laplacian has exactly 2M−2N+2+2b2M - 2N + 2 + 2b real eigenvalues if and only if GG is strictly Ramanujan. In particular, cycles, complete graphs and balanced complete bipartite graphs, which are strictly Ramanujan, attain the bound.

We also determine how these real eigenvalues are distributed around 1. In Theorem 6.2, we show that at least M−N+2cM - N + 2c of them lie in [0,1)[0,1) and at least M−N+2bM - N + 2b lie in (1,2](1,2].

For completeness, we also prove in Theorem 7.1 that L\mathcal{L} has at most 2M−2c−2b2M - 2c - 2b real eigenvalues, counted with algebraic multiplicity, and that this bound is attained by the cycle C4C_4.

Structure of the paper

In Section 2, we fix the notation and establish some preliminary results, including Lemma 2.2 from indefinite linear algebra. In Section 3, we prove Theorem 3.1, which settles our 2022 conjecture. In Section 4, we refine this bound by taking into account the connected and bipartite components of the graph, thus proving Theorem 4.1. In Section 5, we show that the refined bound is sharp, and we prove that a connected regular graph attains it if and only if it is strictly Ramanujan. In Section 6, we show how the real eigenvalues split around 1. Finally, in Section 7, we prove an upper bound on the number of real eigenvalues of the non-backtracking Laplacian.

Notation and preliminaries

Throughout the paper, we fix a simple graph G=(V,E)G=(V,E) on NN nodes and MM edges, with minimum degree at least 2, and we use the same notation as in the introduction. In particular, G=(V,E)\mathcal{G}=(\mathcal{V},\mathcal{E}) denotes the non-backtracking graph of GG, whose vertices are the 2M2M oriented edges e1,…,e2Me_1,\ldots,e_{2M} of GG, labeled so that

eM+i=ei−1,for i=1,…,M.e_{M+i}=e_i^{-1}, \qquad\text{for } i=1,\ldots,M.

Moreover, AA and D\mathcal{D} denote the adjacency and degree matrices of GG, while L=Id−D−1A\mathcal{L}=\mathrm{Id}-\mathcal{D}^{-1}A and T=D−1A\mathcal{T}=\mathcal{D}^{-1}A denote the non-backtracking Laplacian and the transition matrix of the non-backtracking random walk on GG.

We identify each vector f∈C2Mf\in\mathbb{C}^{2M} with the function

f:V→Cei↦fi.\begin{aligned} f:\mathcal{V}&\to\mathbb{C}\\ e_i&\mapsto f_i. \end{aligned}

In these terms, the transition matrix acts as

(Tf)([v,w])=1deg⁡w−1∑z∼w,z≠vf([w,z]),(2)(\mathcal{T}f)([v,w])=\frac{1}{\deg w-1}\sum_{\substack{z\sim w,\,z\ne v}}f([w,z]), \tag*{(2)}

for every [v,w]∈V[v,w]\in\mathcal{V}, where z∼wz\sim w means that zz and ww are adjacent in GG.

Given a real symmetric matrix K∈Rr×rK \in\mathbb{R}^{r \times r}, the KK-product on Cr\mathbb{C}^{r} is defined as

(x,y)K:=⟨x,Ky⟩=xTKy,(\mathbf{x},\mathbf{y})_{K} := \langle\mathbf{x},K\mathbf{y}\rangle= \mathbf{x}^{\mathsf{T}}K\mathbf{y},

where ⟨⋅,⋅⟩\langle\cdot,\cdot\rangle is the standard inner product on Cr\mathbb{C}^{r}. A matrix R∈Rr×rR \in\mathbb{R}^{r \times r} is said to be self-adjoint with respect to the KK-product, or KK-self-adjoint, if

(Rx,y)K=(x,Ry)K for all x,y∈Cr,(R\mathbf{x},\mathbf{y})_{K} = (\mathbf{x},R\mathbf{y})_{K} \text{ for all } \mathbf{x},\mathbf{y} \in\mathbb{C}^{r},

or equivalently, if

RTK=KR.R^{\mathsf{T}}K = KR.

As in [17], we let PP be the 2M×2M2M \times2M matrix

P:=(0Id⁡Id⁡0),P := \begin{pmatrix} 0 & \operatorname{Id} \\ \operatorname{Id} & 0 \end{pmatrix},

where each block has size M×MM \times M. Since eM+i=ei−1e_{M+i}=e_{i}^{-1}, we have that

(Pf)(e)=f(e−1)(Pf)(e)=f(e^{-1})

for each e∈Ve \in\mathcal{V}. Moreover, by [17 Theorem 3.8], L\mathcal{L} is PP-self-adjoint, that is,

LTP=PL.(3)\mathcal{L}^{\mathsf{T}}P=P\mathcal{L}. \tag*{(3)}

We now introduce the matrix

H:=P(Id⁡−L)=PT.H := P(\operatorname{Id}-\mathcal{L})=P\mathcal{T}.

Its entries are

Hij={1deg⁡(in⁡(ei))−1if in⁡(ei)=in⁡(ej) and ei≠ej,0otherwise.H_{ij} = \begin{cases} \frac{1}{\deg(\operatorname{in}(e_i))-1} & \text{if } \operatorname{in}(e_i)=\operatorname{in}(e_j) \text{ and } e_i\ne e_j,\\ 0 & \text{otherwise.} \end{cases}

In particular, HH is real and symmetric. Moreover, L\mathcal{L} is HH-self-adjoint. In fact, by (3) and since L\mathcal{L} commutes with Id⁡−L\operatorname{Id}-\mathcal{L},

LTH=LTP(Id⁡−L)=PL(Id⁡−L)=P(Id⁡−L)L=HL.(4)\mathcal{L}^{\mathsf{T}}H=\mathcal{L}^{\mathsf{T}}P(\operatorname{Id}-\mathcal{L})=P\mathcal{L}(\operatorname{Id}-\mathcal{L})=P(\operatorname{Id}-\mathcal{L})\mathcal{L}=H\mathcal{L}. \tag*{(4)}

The matrix HH plays a central role in the proofs of our main results, for the following reason. By Lemma 2.2 below, if a real matrix RR is self-adjoint with respect to the KK-product of a real symmetric invertible matrix KK, then RR has at most 2min⁡(n+(K),n−(K))2\min(n_{+}(K),n_{-}(K)) non-real eigenvalues, where n+(K)n_{+}(K) and n−(K)n_{-}(K) denote the numbers of positive and negative eigenvalues of KK, counted with multiplicity. By (3), L\mathcal{L} is PP-self-adjoint. However, PP has eigenvalues 11 and −1-1, each with multiplicity MM, so in this case the lemma only says that L\mathcal{L} has at most 2M2M non-real eigenvalues, which is trivial since L\mathcal{L} is a 2M×2M2M \times2M matrix. The advantage of considering HH is that L\mathcal{L} is also HH-self-adjoint, by (4), and HH has only NN positive eigenvalues and 2M−N2M-N negative ones, by Lemma 2.1 below. Since every vertex of GG has degree at least 2, we have that

2M=∑v∈Vdeg⁡v≥2N,2M=\sum_{v\in V}\deg v\ge2N,

and therefore

min⁡(n+(H),n−(H))=min⁡(N,2M−N)=N.(5)\min(n_+(H),n_-(H))=\min(N,2M-N)=N. \tag*{(5)}

Hence, by Lemma 2.2, L\mathcal{L} has at most 2N2N non-real eigenvalues, that is, at least 2M−2N2M-2N real ones. This is the content of Theorem 3.1. For the refinement in Theorem 4.1, we then use the connected and bipartite components of GG to reduce the number of positive eigenvalues of HH that need to be taken into account.

We first prove the claim on the eigenvalues of HH.

Lemma 2.1. The matrix HH is invertible. Moreover,

n+(H)=Nandn−(H)=2M−N.n_+(H)=N \qquad\text{and}\qquad n_-(H)=2M-N.

Proof. By definition of HH, we have that Hij=0H_{ij}=0 whenever in⁡(ei)≠in⁡(ej)\operatorname{in}(e_i)\ne\operatorname{in}(e_j). Hence, if we order the oriented edges according to their input, HH is block diagonal, with one block HvH_v of size deg⁡v×deg⁡v\deg v\times\deg v for each v∈Vv\in V. Moreover,

Hv=1deg⁡v−1(Jdeg⁡v−Id),H_v=\frac{1}{\deg v-1}(J_{\deg v}-I_d),

where Jdeg⁡vJ_{\deg v} denotes the deg⁡v×deg⁡v\deg v\times\deg v matrix whose entries are all equal to 1. Since Jdeg⁡vJ_{\deg v} has eigenvalue deg⁡v\deg v with multiplicity 1, and eigenvalue 0 with multiplicity deg⁡v−1\deg v-1, the block HvH_v has eigenvalue 1 with multiplicity 1, and eigenvalue −1/(deg⁡v−1)-1/(\deg v-1) with multiplicity deg⁡v−1\deg v-1. The eigenvalues of HH, with multiplicity, are those of the blocks HvH_v. Since none of them is zero, HH is invertible, and

n+(H)=∑v∈V1=N,whilen−(H)=∑v∈V(deg⁡v−1)=2M−N.n_+(H)=\sum_{v\in V}1=N,\qquad\text{while}\qquad n_-(H)=\sum_{v\in V}(\deg v-1)=2M-N.

We now state the linear algebra fact used in the proofs of our main results. Given a real square matrix RR, we let nR(R)n_{\mathbb{R}}(R) denote the number of real eigenvalues of RR, counted with algebraic multiplicity.

Lemma 2.2. Let K∈Rr×rK\in\mathbb{R}^{r\times r} be symmetric and invertible, and let R∈Rr×rR\in\mathbb{R}^{r\times r} be KK-self-adjoint. Then, RR has at most 2min⁡(n+(K),n−(K))2\min(n_+(K),n_-(K)) non-real eigenvalues, counted with algebraic multiplicity. Equivalently,

nR(R)≥r−2min⁡(n+(K),n−(K)).n_{\mathbb{R}}(R)\ge r-2\min(n_+(K),n_-(K)).

Proof. Since RR is KK-self-adjoint, it follows from [14 page 77] (see the inequality following equation (5.2.4) and the comment after it, where A=RA=R, H=KH=K and i−(H)=n−(K)i_-(H)=n_-(K) in our notation) that n−(K)n_-(K) is at least half the number of non-real eigenvalues of RR, counted with algebraic multiplicity. Since RR is also (−K)(-K)-self-adjoint, and since n−(−K)=n+(K)n_-(-K)=n_+(K), the same holds for n+(K)n_+(K). Therefore, the number of non-real eigenvalues of RR is at most 2min⁡(n+(K),n−(K))2\min(n_+(K),n_-(K)).

The bound 2M−2N2M - 2N

In this section, we prove our 2022 conjecture, which states that the non-backtracking Laplacian of a graph with minimum degree at least 2 has at least 2M−2N2M - 2N real eigenvalues. As anticipated in § 2, this follows by combining the HH-self-adjointness of L\mathcal{L} with Lemma 2.1 and Lemma 2.2.

Theorem 3.1. Let GG be a simple graph on NN nodes and MM edges, with minimum degree at least 2. Then, the number of real eigenvalues of the non-backtracking Laplacian of GG, counted with algebraic multiplicity, is at least

2M−2N.2M - 2N.

Proof. By (4), L\mathcal{L} is HH-self-adjoint, and by Lemma 2.1, HH is a real symmetric invertible matrix with n+(H)=Nn_{+}(H) = N and n−(H)=2M−Nn_{-}(H) = 2M - N. As observed in (5), the minimum degree assumption implies that

min⁡(n+(H),n−(H))=N.\min\left(n_{+}(H), n_{-}(H)\right) = N.

Applying Lemma 2.2 with R=LR = \mathcal{L} and K=HK = H yields

nR(L)≥2M−2N.n_{\mathbb{R}}(\mathcal{L}) \ge2M - 2N.

The refined bound

In this section, we refine Theorem 3.1 by taking into account the connected and bipartite components of GG. These give explicit eigenvectors of L\mathcal{L} with real eigenvalues, which allow us to reduce the number of positive eigenvalues of HH that need to be taken into account in Lemma 2.2.

Theorem 4.1. Let GG be a simple graph on NN nodes and MM edges, with minimum degree at least 2. Let cc be the number of connected components of GG, and let bb be the number of bipartite ones. Then, the number of real eigenvalues of the non-backtracking Laplacian of GG, counted with algebraic multiplicity, is at least

2M−2N+2c+2b.2M - 2N + 2c + 2b.

Proof. For each connected component CC of GG, let V(C)V(C) be the vertex set of CC, let E(C)E(C) be its edge set, and let 1C:V→{0,1}\mathbf{1}_{C}: V \to\{0,1\} be the indicator function of the oriented edges of $C. If CC is bipartite, fix a function sC:V(C)→{1,−1}s_{C}: V(C) \to\{1,-1\} that takes opposite values on adjacent vertices, and let

σC:V→{0,1,−1}\sigma_{C}: V \to\{0,1,-1\}
[v,w]↦{sC(v),if [v,w] is an oriented edge of C,0,otherwise.[v,w] \mapsto \begin{cases} s_{C}(v), & \text{if } [v,w] \text{ is an oriented edge of } C,\\ 0, & \text{otherwise.} \end{cases}

By (2) we have that, for every [v,w]∈V[v,w]\in\mathcal{V},

(T1C)([v,w])=1deg⁡w−1∑z∼w,z≠v1C([w,z])={1if [v,w] is an oriented edge of C,0otherwise.(T\mathbb{1}_C)([v,w])=\frac{1}{\deg w-1}\sum_{\substack{z\sim w,\,z\ne v}}\mathbb{1}_C([w,z]) =\begin{cases} 1 & \text{if }[v,w]\text{ is an oriented edge of }C,\\ 0 & \text{otherwise.} \end{cases}

Hence, T1C=1CT\mathbb{1}_C=\mathbb{1}_C. Similarly, for every [v,w]∈V[v,w]\in\mathcal{V}, by definition of PP, and since [v,w][v,w] and [w,v][w,v] belong to the same connected component,

(P1C)([v,w])=1C([w,v])=1C([v,w]).(P\mathbb{1}_C)([v,w])=\mathbb{1}_C([w,v])=\mathbb{1}_C([v,w]).

Hence, P1C=1CP\mathbb{1}_C=\mathbb{1}_C. Moreover, if CC is bipartite and [v,w][v,w] is in CC, then sC(w)=−sC(v)s_C(w)=-s_C(v). Since each oriented edge [w,z][w,z] with z∼wz\sim w also belongs to CC, this implies that, by (2),

(TσC)([v,w])=1deg⁡w−1∑z∼w,z≠vσC([w,z])=1deg⁡w−1∑z∼w,z≠vsC(w)=−sC(v),(T\sigma_C)([v,w])=\frac{1}{\deg w-1}\sum_{\substack{z\sim w,\,z\ne v}}\sigma_C([w,z]) =\frac{1}{\deg w-1}\sum_{\substack{z\sim w,\,z\ne v}}s_C(w) =-s_C(v),

and by definition of PP,

(PσC)([v,w])=σC([w,v])=sC(w)=−sC(v).(P\sigma_C)([v,w])=\sigma_C([w,v])=s_C(w)=-s_C(v).

Together with the fact that both TσCT\sigma_C and PσCP\sigma_C vanish outside CC, this implies that

TσC=−σCandPσC=−σC.T\sigma_C=-\sigma_C\qquad\text{and}\qquad P\sigma_C=-\sigma_C.

Since H=PTH=PT and L=Id⁡−TL=\operatorname{Id}-T, from the above equalities it follows that

H1C=1C,L1C=0,HσC=σC,LσC=2σC.H\mathbb{1}_C=\mathbb{1}_C,\qquad L\mathbb{1}_C=0,\qquad H\sigma_C=\sigma_C,\qquad L\sigma_C=2\sigma_C.

Now, let W⊆C2MW\subseteq\mathbb{C}^{2M} be the span of the functions 1C\mathbb{1}_C, for all connected components CC, and σC\sigma_C, for all bipartite components CC. These c+bc+b functions are non-zero and mutually orthogonal with respect to the standard inner product. In fact, functions associated with different components have disjoint supports, and for a bipartite component CC,

⟨1C,σC⟩=∑e∈V1C(e)σC(e)=∑{v,w}∈E(C)(σC([v,w])+σC([w,v]))=∑{v,w}∈E(C)(sC(v)+sC(w))=0.\begin{aligned} \langle\mathbb{1}_C,\sigma_C\rangle=\sum_{e\in\mathcal{V}}\mathbb{1}_C(e)\sigma_C(e) \\ &=\sum_{\{v,w\}\in E(C)}\bigl(\sigma_C([v,w])+\sigma_C([w,v])\bigr) \\ &=\sum_{\{v,w\}\in E(C)}\bigl(s_C(v)+s_C(w)\bigr) =0. \end{aligned}

Therefore, dim⁡W=c+b\dim W=c+b. Moreover, Hw=wH\mathbf{w}=\mathbf{w} for every w∈W\mathbf{w}\in W, and since WW is spanned by eigenvectors of L\mathcal{L}, it is L\mathcal{L}-invariant, that is, Lw∈W\mathcal{L}\mathbf{w}\in W for every w∈W\mathbf{w}\in W.

Now, for all w∈W\mathbf{w}\in W and x∈C2M\mathbf{x}\in\mathbb{C}^{2M}, we have that

(w,x)H=w‾THx=(Hw‾)Tx=Hw‾Tx=w‾Tx=⟨w,x⟩,(\mathbf{w},\mathbf{x})_H=\overline{\mathbf{w}}^{\mathsf{T}}H\mathbf{x}=(H\overline{\mathbf{w}})^{\mathsf{T}}\mathbf{x}=\overline{H\mathbf{w}}^{\mathsf{T}}\mathbf{x}=\overline{\mathbf{w}}^{\mathsf{T}}\mathbf{x}=\langle\mathbf{w},\mathbf{x}\rangle,

where the second equality holds because HH is symmetric, the third because HH is real, and the fourth because Hw=wH\mathbf{w}=\mathbf{w}.

Therefore, if we let W⊥W^\perp be the orthogonal complement of WW with respect to the standard inner product, then W⊥W^\perp is also L\mathcal{L}-invariant. In fact, let x∈W⊥\mathbf{x}\in W^\perp and w∈W\mathbf{w}\in W. Then, since Lw∈W\mathcal{L}\mathbf{w}\in W, we have that

⟨w,Lx⟩=(w,Lx)H=(Lw,x)H=⟨Lw,x⟩=0,\langle\mathbf{w},\mathcal{L}\mathbf{x}\rangle=(\mathbf{w},\mathcal{L}\mathbf{x})_H=(\mathcal{L}\mathbf{w},\mathbf{x})_H=\langle\mathcal{L}\mathbf{w},\mathbf{x}\rangle=0,

where the first and third equalities follow from the above identity, the second one holds because L\mathcal{L} is HH-self-adjoint, and the last one because x∈W⊥\mathbf{x}\in W^\perp. Hence, Lx∈W⊥\mathcal{L}\mathbf{x}\in W^\perp.

Now, let QQ be a real orthogonal matrix whose first cc columns are the vectors 1C/∥1C∥\mathbf{1}_{\mathcal{C}}/\|\mathbf{1}_{\mathcal{C}}\|, whose next bb columns are the vectors σC/∥σC∥\boldsymbol{\sigma}_{\mathcal{C}}/\|\boldsymbol{\sigma}_{\mathcal{C}}\|, and whose remaining 2M−c−b2M-c-b columns form an orthonormal basis of W⊥W^\perp, which can be chosen real since WW is spanned by real vectors. In other words, QQ is the change of basis to an orthonormal basis adapted to the decomposition C2M=W⊕W⊥\mathbb{C}^{2M}=W\oplus W^\perp. Since both summands are L\mathcal{L}-invariant, QTLQQ^{\mathsf{T}}\mathcal{L}Q is block diagonal, and since the first c+bc+b columns of QQ are eigenvectors of L\mathcal{L}, with eigenvalue 00 for the first cc ones and 22 for the next bb ones,

QTLQ=(LW00L0),Q^{\mathsf{T}}\mathcal{L}Q= \begin{pmatrix} \mathcal{L}_W & 0\\ 0 & \mathcal{L}_0 \end{pmatrix},

where LW\mathcal{L}_W is the diagonal matrix with cc diagonal entries equal to 00 and bb diagonal entries equal to 22, and L0\mathcal{L}_0 is a real matrix of size (2M−c−b)×(2M−c−b)(2M-c-b)\times(2M-c-b).

Similarly, let qj\mathbf{q}_j denote the jj-th column of QQ. Then (QTHQ)ij=(qi,qj)H(Q^{\mathsf{T}}HQ)_{ij}=(\mathbf{q}_i,\mathbf{q}_j)_H, and by the identity above, (qi,qj)H=⟨qi,qj⟩(\mathbf{q}_i,\mathbf{q}_j)_H=\langle\mathbf{q}_i,\mathbf{q}_j\rangle, which is 11 if i=ji=j and 00 otherwise, whenever qi∈W\mathbf{q}_i\in W or qj∈W\mathbf{q}_j\in W. Hence

QTHQ=(Id00H0),Q^{\mathsf{T}}HQ= \begin{pmatrix} I_d & 0\\ 0 & H_0 \end{pmatrix},

where H0H_0 is a real symmetric matrix of size (2M−c−b)×(2M−c−b)(2M-c-b)\times(2M-c-b).

Since HH is invertible, so is H0H_0. Moreover, by Sylvester’s law of inertia and Lemma 2.1,

n+(H0)=n+(H)−(c+b)=N−c−bn_+(H_0)=n_+(H)-(c+b)=N-c-b

and

n−(H0)=n−(H)=2M−N.n_-(H_0)=n_-(H)=2M-N.

Since QT=Q−1Q^{\mathsf{T}}=Q^{-1}, the identity LTH=HL\mathcal{L}^{\mathsf{T}}H=H\mathcal{L} implies that

(QT ⁣LQ)T(QTHQ)=QTLTHQ=QTHLQ=(QTHQ)(QTLQ),(Q^{\mathsf{T}\!}\mathcal{L}Q)^{\mathsf{T}}(Q^{\mathsf{T}}HQ)=Q^{\mathsf{T}}\mathcal{L}^{\mathsf{T}}HQ=Q^{\mathsf{T}}H\mathcal{L}Q=(Q^{\mathsf{T}}HQ)(Q^{\mathsf{T}}\mathcal{L}Q),

and comparing the lower right blocks gives L0⊤H0=H0L0\mathcal{L}_0^{\top}H_0 = H_0\mathcal{L}_0. That is, L0\mathcal{L}_0 is H0H_0-self-adjoint. By (5), we have that

N−c−b≤N≤2M−N.N-c-b \le N \le2M-N.

and therefore Lemma 2.2 implies that L0\mathcal{L}_0 has at most 2(N−c−b)2(N-c-b) non-real eigenvalues, counted with algebraic multiplicity.

Finally, since Q⊤LQQ^{\top}\mathcal{L}Q is block diagonal,

det⁡(t Id⁡−L)=det⁡(t Id⁡−LW)⋅det⁡(t Id⁡−L0)=tc(t−2)bdet⁡(t Id⁡−L0).\det(t\,\operatorname{Id}-\mathcal{L})=\det(t\,\operatorname{Id}-\mathcal{L}_W)\cdot\det(t\,\operatorname{Id}-\mathcal{L}_0)=t^c(t-2)^b\det(t\,\operatorname{Id}-\mathcal{L}_0).

Hence, every non-real eigenvalue of L\mathcal{L} is an eigenvalue of L0\mathcal{L}_0, with the same algebraic multiplicity, and therefore

nR(L)≥2M−2(N−c−b)=2M−2N+2c+2b.n_{\mathbb{R}}(\mathcal{L})\ge2M-2(N-c-b)=2M-2N+2c+2b.

Sharpness

In this section, we show that the bound in Theorem 4.1 is sharp. For connected regular graphs, we first determine exactly when it is attained: by Theorem 5.1, this happens if and only if the graph is strictly Ramanujan. As a consequence, in Corollary 5.2 we obtain several explicit families of graphs attaining the bound.

Theorem 5.1. Let GG be a connected dd-regular graph with d≥2d \ge2, and let κ\kappa be the number of adjacency eigenvalues μ≠±d\mu\ne\pm d of GG with ∣μ∣≥2d−1|\mu| \ge2\sqrt{d-1}, counted with multiplicity. Then,

nR(L)=2M−2N+2+2b+2κ.n_{\mathbb{R}}(\mathcal{L})=2M-2N+2+2b+2\kappa.

In particular, equality in Theorem 4.1 holds if and only if GG is strictly Ramanujan, that is, every adjacency eigenvalue μ≠±d\mu\ne\pm d satisfies ∣μ∣<2d−1|\mu| < 2\sqrt{d-1}.

Proof. Let GG be a connected dd-regular graph on NN nodes and MM edges, with d≥2d \ge2. Since GG is connected, we have that c=1c=1, and therefore the quantity in Theorem 4.1 is

2M−2N+2+2b,2M-2N+2+2b,

where b=1b=1 if GG is bipartite, and b=0b=0 otherwise.

Now, let μ1,…,μN\mu_1,\ldots,\mu_N be the eigenvalues of the adjacency matrix AA of GG, listed with multiplicity, and given μ∈R\mu\in\mathbb{R}, let

qμ(t):=t2−μd−1t+1d−1.q_\mu(t):=t^2-\frac{\mu}{d-1}t+\frac{1}{d-1}.

Since GG is dd-regular, we have that D=d Id⁡D=d\,\operatorname{Id} and

T=1d−1A.\mathcal{T}=\frac{1}{d-1}A.

Hence, the Ihara–Bass formula (1) becomes

det⁡(Id−uA)=(1−u2)M−N∏j=1N(1−μju+(d−1)u2).\det(\mathrm{Id}-uA) = (1-u^2)^{M-N}\prod_{j=1}^{N}(1-\mu_j u+(d-1)u^2).

For t≠0t \ne0, substituting u=1/((d−1)t)u=1/((d-1)t) and multiplying both sides by t2Mt^{2M}, we obtain

det⁡(t Id−T)=(t2−1(d−1)2)M−N∏j=1Nqμj(t).\det(t\,\mathrm{Id}-\mathcal{T}) = \left(t^2-\frac{1}{(d-1)^2}\right)^{M-N}\prod_{j=1}^{N}q_{\mu_j}(t).

Note that the exponent M−N=N(d−2)/2M-N=N(d-2)/2 is non-negative. We now count the real roots of each factor, with multiplicity.

The first factor has 2(M−N)2(M-N) real roots, namely 1/(d−1)1/(d-1) and −1/(d−1)-1/(d-1), each with multiplicity M−NM-N.

Since GG is connected and dd-regular, dd is a simple eigenvalue of AA. Moreover, −d-d is an eigenvalue of AA if and only if GG is bipartite, in which case it is also simple. The corresponding quadratic factors are

qd(t)=(t−1)(t−1d−1)andq−d(t)=(t+1)(t+1d−1),q_d(t)=(t-1)\left(t-\frac{1}{d-1}\right) \qquad\text{and}\qquad q_{-d}(t)=(t+1)\left(t+\frac{1}{d-1}\right),

which have two real roots each. Hence, the eigenvalues ±d\pm d contribute 2+2b2+2b real roots.

For every other eigenvalue μ≠±d\mu\ne\pm d of AA, the discriminant of qμq_\mu is

(μd−1)2−4d−1=μ2−4(d−1)(d−1)2.\left(\frac{\mu}{d-1}\right)^2-\frac{4}{d-1} =\frac{\mu^2-4(d-1)}{(d-1)^2}.

Therefore, qμq_\mu has two real roots, counted with multiplicity, if ∣μ∣≥2d−1|\mu|\ge2\sqrt{d-1}, and two non-real roots if ∣μ∣<2d−1|\mu|<2\sqrt{d-1}.

Since the multiplicities of the roots add up when polynomials are multiplied, we obtain, with κ\kappa as in the statement,

nR(T)=2(M−N)+2+2b+2κ.n_{\mathbb{R}}(\mathcal{T})=2(M-N)+2+2b+2\kappa.

Since L=Id−T\mathcal{L}=\mathrm{Id}-\mathcal{T}, this implies that

nR(L)=2M−2N+2+2b+2κ.n_{\mathbb{R}}(\mathcal{L})=2M-2N+2+2b+2\kappa.

In particular, L\mathcal{L} has exactly 2M−2N+2+2b2M-2N+2+2b real eigenvalues if and only if κ=0\kappa=0, that is, if and only if GG is strictly Ramanujan.

Corollary 5.2. The bound in Theorem 4.1 is attained by the following graphs:

  • the cycle graph CNC_N, for every N≥3N\ge3;

  • the complete graph KNK_N, for every N≥3N\ge3;

  • the complete bipartite graph Kr,rK_{r,r}, for every r≥2r\ge2.

In particular, the bound in Theorem 4.1 is sharp.

Proof. Since all these graphs are connected and regular, by Theorem 5.1 it suffices to show that they are strictly Ramanujan.

  • The cycle CNC_N is 22-regular, and its adjacency eigenvalues are 2cos⁡(2πj/N)2\cos(2\pi j/N), for j=0,…,N−1j=0,\ldots,N-1. All of them except ±2\pm2 satisfy ∣μ∣<2=22−1|\mu|<2=2\sqrt{2}-1.

  • The complete graph KNK_N is (N−1)(N-1)-regular, and its only adjacency eigenvalue other than N−1N-1 is −1-1, which satisfies 1<2N−21<2\sqrt{N-2} for N≥3N\ge3.

  • The complete bipartite graph Kr,rK_{r,r} is rr-regular, and its only adjacency eigenvalue other than ±r\pm r is 00, which satisfies 0<2r−10<2\sqrt{r-1} for r≥2r\ge2.

This proves the claim.

Splitting the real eigenvalues around 1

Theorem 4.1 counts the real eigenvalues of L\mathcal{L}. In this section, we show how many of them must lie on each side of 11. Equivalently, we count the positive and the negative real eigenvalues of T=Id⁡−L\mathcal{T}=\operatorname{Id}-\mathcal{L}.

Recall from [17 Theorem 4.1] that every eigenvalue λ\lambda of L\mathcal{L} satisfies

∣1−λ∣≥1Δ−1,|1-\lambda|\ge\frac{1}{\Delta-1},

where Δ\Delta is the largest degree of GG. Hence, the real eigenvalues of L\mathcal{L} in [0,1)[0,1) actually lie in [0,1−1/(Δ−1)][0,1-1/(\Delta-1)], and those in (1,2](1,2] lie in [1+1/(Δ−1),2][1+1/(\Delta-1),2].

For a real symmetric matrix KK, we define its signature as

sig⁡(K):=n+(K)−n−(K).\operatorname{sig}(K):=n_{+}(K)-n_{-}(K).

For a real square matrix RR, we let n>(R)n_{>}(R) and n<(R)n_{<}(R) denote the numbers of positive and negative real eigenvalues of RR, counted with algebraic multiplicity.

The following lemma, which refines Lemma 2.2, is needed for the proof of Theorem 6.2 below.

Lemma 6.1. Let K∈Rr×rK\in\mathbb{R}^{r\times r} be symmetric and invertible, and let R∈Rr×rR\in\mathbb{R}^{r\times r} be invertible and KK-self-adjoint. Then,

n>(R)≥∣sig⁡(K)+sig⁡(KR)∣2andn<(R)≥∣sig⁡(K)−sig⁡(KR)∣2.n_{>}(R)\ge\frac{|\operatorname{sig}(K)+\operatorname{sig}(KR)|}{2} \qquad\text{and}\qquad n_{<}(R)\ge\frac{|\operatorname{sig}(K)-\operatorname{sig}(KR)|}{2}.

Proof. The matrix KRKR is real, symmetric and invertible, since

(KR)T=RTK=KR.(KR)^{\mathsf{T}}=R^{\mathsf{T}}K=KR.

By the canonical form for KK-self-adjoint matrices [14 Theorem 5.1.1], there is an invertible matrix SS such that S−1RSS^{-1}RS and S∗KSS^{*}KS are block diagonal with matching blocks, as follows. Each Jordan block Jm(λ)J_m(\lambda) of a real eigenvalue λ\lambda is paired with εPm\varepsilon P_m, where PmP_m is the m×mm \times m matrix with ones on the anti-diagonal and zeros elsewhere, and ε∈{1,−1}\varepsilon\in\{1,-1\}. Each pair of Jordan blocks Jm(λ)⊕Jm(λ‾)J_m(\lambda) \oplus J_m(\overline{\lambda}) of a non-real eigenvalue λ\lambda is paired with P2mP_{2m}. Since

S∗KRS=(S∗KS)(S−1RS),S^*KRS=(S^*KS)(S^{-1}RS),

the matrices S∗KSS^*KS and S∗KRSS^*KRS are block diagonal, and by Sylvester’s law of inertia their signatures are the sums of the signatures of the blocks. The symmetric matrix PmP_m has signature 11 if mm is odd and 00 if mm is even, and so does PmJm(λ)P_mJ_m(\lambda) multiplied by sgn⁡(λ)\operatorname{sgn}(\lambda), for real λ≠0\lambda\ne0. For a pair of non-real eigenvalues, both blocks have signature 00, since the span of the first mm basis vectors of the block is isotropic for both forms and has half the dimension. Therefore

sig⁡(K)=∑ε,sig⁡(KR)=∑sgn⁡(λ)ε,\operatorname{sig}(K)=\sum\varepsilon,\qquad\operatorname{sig}(KR)=\sum\operatorname{sgn}(\lambda)\varepsilon,

where both sums run over the Jordan blocks of odd size belonging to real eigenvalues λ\lambda. Let pp and qq be the sums of ε\varepsilon over such blocks with λ>0\lambda> 0 and with λ<0\lambda< 0, respectively. Then, sig⁡(K)=p+q\operatorname{sig}(K)=p+q and sig⁡(KR)=p−q\operatorname{sig}(KR)=p-q. Finally, ∣p∣|p| is at most the number of blocks with λ>0\lambda> 0, which is at most n>(R)n_{>}(R), and similarly ∣q∣≤n<(R)|q| \le n_{<}(R).

Using Lemma 6.1, we can now refine Theorem 4.1 as follows.

Theorem 6.2. Let GG be a simple graph on NN nodes and MM edges, with minimum degree at least 22. Let cc be the number of connected components of GG, and let bb be the number of bipartite ones. Then, TT has at least M−N+2cM-N+2c positive and at least M−N+2bM-N+2b negative real eigenvalues, counted with algebraic multiplicity. Equivalently, LL has at least M−N+2cM-N+2c real eigenvalues in [0,1)[0,1) and at least M−N+2bM-N+2b real eigenvalues in (1,2](1,2].

Proof. We use the notation of the proof of Theorem 4.1. Let T0:=Id⁡−L0\mathcal{T}_0:=\operatorname{Id}-L_0, so that QTTQQ^{\mathsf{T}}TQ is block diagonal with blocks Id⁡−LW\operatorname{Id}-L_W and T0\mathcal{T}_0, and QTHQ=QTPTQQ^{\mathsf{T}}HQ=Q^{\mathsf{T}}PTQ has blocks Id⁡\operatorname{Id} and H0H_0.

Since P1C=1CP\mathbf{1}_C=\mathbf{1}_C and PσC=−σCP\sigma_C=-\sigma_C, the matrix PP maps WW to itself, and since PP is symmetric, it also maps W⊥W^\perp to itself. Hence QTPQQ^{\mathsf{T}}PQ is block diagonal, with a diagonal first block PWP_W having cc entries equal to 11 and bb entries equal to −1-1, and a second block P0P_0. Comparing the second blocks in

QTHQ=(QTPQ)(QTTQ)Q^{\mathsf{T}}HQ=(Q^{\mathsf{T}}PQ)(Q^{\mathsf{T}}TQ)

and in (3) gives

H0=P0T0H_0=P_0\mathcal{T}_0

and

T0TP0=P0T0.\mathcal{T}_0^{\mathsf{T}}P_0=P_0\mathcal{T}_0.

The matrix PP has eigenvalues 11 and −1-1, each with multiplicity MM. By Sylvester’s law of inertia, n+(P0)=M−cn_+(P_0)=M-c and n−(P0)=M−bn_-(P_0)=M-b, and from the proof of Theorem 4.1, n+(H0)=N−c−bn_+(H_0)=N-c-b and n−(H0)=2M−Nn_-(H_0)=2M-N. Hence,

sig⁡(P0)=b−candsig⁡(H0)=2N−2M−c−b.\operatorname{sig}(P_0)=b-c\qquad\text{and}\qquad\operatorname{sig}(H_0)=2N-2M-c-b.

Since H0H_0 is invertible, so is T0\mathcal{T}_0. Lemma 6.1 with K=P0K=P_0 and R=T0R=\mathcal{T}_0 gives

n>(T0)≥∣(b−c)+(2N−2M−c−b)∣2=M−N+cn_{>}(\mathcal{T}_0) \ge\frac{\lvert(b-c)+(2N-2M-c-b)\rvert}{2}=M-N+c

and

n<(T0)≥∣(b−c)−(2N−2M−c−b)∣2=M−N+b,n_{<}(\mathcal{T}_0) \ge\frac{\lvert(b-c)-(2N-2M-c-b)\rvert}{2}=M-N+b,

where we used M≥NM \ge N. Finally, the first block Id⁡−LW\operatorname{Id}-\mathcal{L}_W contributes the eigenvalue 11 with multiplicity cc and the eigenvalue −1-1 with multiplicity bb. The statement for L\mathcal{L} follows from L=Id⁡−T\mathcal{L}=\operatorname{Id}-\mathcal{T} and the fact that all eigenvalues of T\mathcal{T} have modulus at most 11, since T\mathcal{T} is row-stochastic.

Adding the two bounds of Theorem 6.2 gives Theorem 4.1. Both bounds are attained by the strictly Ramanujan graphs of Theorem 5.1: in the proof of that theorem, the factor

(t2−1(d−1)2)M−N\left(t^2-\frac{1}{(d-1)^2}\right)^{M-N}

contributes M−NM-N positive and M−NM-N negative roots, the eigenvalue dd of AA contributes the positive roots 11 and 1/(d−1)1/(d-1), and the eigenvalue −d-d, present exactly when GG is bipartite, contributes the negative roots −1-1 and −1/(d−1)-1/(d-1).

Remark 6.3. The results of this section do not depend on the particular weights 1/(deg⁡v−1)1/(\deg v-1), and they hold for any weighted matrix Tf=CfA\mathcal{T}_f=C_fA, where ff is a positive function on the vertices and CfC_f is the diagonal matrix with diagonal entries (Cf)ee:=f(out⁡(e))(C_f)_{ee}:=f(\operatorname{out}(e)). In fact, as in Lemma 2.1, PTfP\mathcal{T}_f is symmetric with NN positive and 2M−N2M-N negative eigenvalues, therefore Lemma 6.1 shows that Tf\mathcal{T}_f has at least M−NM-N positive and at least M−NM-N negative real eigenvalues. The refinement by 2c2c and 2b2b can also be obtained, using the Perron–Frobenius Theorem in place of the explicit eigenvectors 1C\mathbf{1}_C and σC\sigma_C. In particular, T\mathcal{T} corresponds to f(v)=1/(deg⁡v−1)f(v)=1/(\deg v-1), while f≡1f\equiv1 gives the transpose of the non-backtracking matrix. Note, however, that the location of the real eigenvalues of Id⁡−T\operatorname{Id}-\mathcal{T} in [0,1)[0,1) and (1,2](1,2] uses the fact that T\mathcal{T} is row-stochastic, and it does not extend to arbitrary weights.

An upper bound

We now complement Theorem 4.1 with an upper bound on the number of real eigenvalues of L\mathcal{L}.

Theorem 7.1. Let GG be a simple graph on NN nodes and MM edges, with minimum degree at least 22. Let cc be the number of connected components of GG, and let bb be the number of bipartite ones. Then, the number of real eigenvalues of the non-backtracking Laplacian of GG, counted with algebraic multiplicity, is at most

2M−2c−2b.2M-2c-2b.

Moreover, this bound is attained by the cycle C4C_4.

Proof. Since L=Id⁡−T\mathcal{L}=\operatorname{Id}-\mathcal{T}, it suffices to show that T\mathcal{T} has at least 2c+2b2c+2b non-real eigenvalues, counted with algebraic multiplicity.

If we order the oriented edges of GG according to the connected components of GG, then T\mathcal{T} is block diagonal, with one block TC\mathcal{T}_C for each connected component CC, and TC\mathcal{T}_C is the transition matrix of the non-backtracking random walk on CC. Hence, it suffices to show that each TC\mathcal{T}_C has at least two non-real eigenvalues, and at least four if CC is bipartite. To this end, we use the following three facts.

(i) All eigenvalues of TC\mathcal{T}_C are non-zero. In fact, T=PH\mathcal{T}=PH is invertible, since P2=Id⁡P^2=\operatorname{Id} and HH is invertible by Lemma 2.1, and the eigenvalues of TC\mathcal{T}_C are eigenvalues of T\mathcal{T}.

(ii) Since TC\mathcal{T}_C is row-stochastic, all eigenvalues tt of TC\mathcal{T}_C satisfy ∣t∣≤1|t|\le1. Moreover, for the same reason, 11 is an eigenvalue of TC\mathcal{T}_C, with the constant functions as eigenfunctions.

(iii) We have that tr⁡(TC2)=0\operatorname{tr}(\mathcal{T}_C^2)=0. In fact,

tr⁡(TC2)=∑e(TC2)ee=∑e∑e′(TC)ee′(TC)e′e.\operatorname{tr}(\mathcal{T}_C^2)=\sum_e(\mathcal{T}_C^2)_{ee}=\sum_e\sum_{e'}(\mathcal{T}_C)_{ee'}(\mathcal{T}_C)_{e'e}.

where ee and e′e' range over the oriented edges of CC. If (TC)ee′(TC)e′e≠0(\mathcal{T}_C)_{ee'}(\mathcal{T}_C)_{e'e}\ne0, then both factors are non-zero, that is, a non-backtracking random walk can go from ee to e′e' and from e′e' to ee. The first step requires e′e' to start at the output of ee, and the second one requires e′e' to end at the input of ee, therefore e′=e−1e'=e^{-1}. But the step from ee to e−1e^{-1} is excluded by the definition of a non-backtracking random walk. Hence, all terms in the above sum vanish.

Now, let t1,…,tmt_1,\ldots,t_m be the eigenvalues of TC\mathcal{T}_C, listed with algebraic multiplicity. Then, by (iii),

∑k=1mtk2=tr⁡(TC2)=0.(6)\sum_{k=1}^{m}t_k^2=\operatorname{tr}(\mathcal{T}_C^2)=0. \tag*{(6)}

By (i), every real eigenvalue tkt_k of TC\mathcal{T}_C satisfies tk2>0t_k^2>0. Hence, by (6), TC\mathcal{T}_C has at least one non-real eigenvalue. Since TC\mathcal{T}_C is real, its non-real eigenvalues appear in complex conjugate pairs, and therefore TC\mathcal{T}_C has at least two non-real eigenvalues.

Now, assume that CC is bipartite. Let V(C)V(C) denote the vertex set of CC, and let MCM_C denote the number of edges of CC. We want to show that, in this case, TC\mathcal{T}_C cannot have exactly one pair of complex conjugate non-real eigenvalues. Since CC is bipartite, there exists a function s:V(C)→{1,−1}s:V(C)\to\{1,-1\} that takes opposite values on adjacent vertices. Hence, we can define the 2MC×2MC2M_C\times2M_C diagonal matrix ZCZ_C with diagonal entries

(ZC)ee:=s(in⁡(e)),(Z_C)_{ee}:=s(\operatorname{in}(e)),

for each oriented edge ee of $C. If (TC)ee′≠0(\mathcal{T}_C)_{ee'} \ne0, then a non-backtracking random walk can go from ee to e′e', implying that in⁡(e′)=out⁡(e)\operatorname{in}(e')=\operatorname{out}(e), and therefore s(in⁡(e′))=−s(in⁡(e))s(\operatorname{in}(e'))=-s(\operatorname{in}(e)). Therefore, since ZCZ_C is diagonal, for all oriented edges e,e′e,e' of CC we have that

(ZCTCZC)ee′=∑f,g(ZC)ef(TC)fg(ZC)ge′=(ZC)ee(TC)ee′(ZC)e′e′=s(in⁡(e))(TC)ee′s(in⁡(e′))=−(TC)ee′.(Z_C\mathcal{T}_C Z_C)_{ee'}=\sum_{f,g}(Z_C)_{ef}(\mathcal{T}_C)_{fg}(Z_C)_{ge'} =(Z_C)_{ee}(\mathcal{T}_C)_{ee'}(Z_C)_{e'e'} =s(\operatorname{in}(e))(\mathcal{T}_C)_{ee'}s(\operatorname{in}(e')) =-(\mathcal{T}_C)_{ee'}.

where the last equality follows from the previous observation if (TC)ee′≠0(\mathcal{T}_C)_{ee'}\ne0, and is trivial if (TC)ee′=0(\mathcal{T}_C)_{ee'}=0. Hence,

ZCTCZC=−TC.Z_C\mathcal{T}_C Z_C=-\mathcal{T}_C.

Since ZC2=Id⁡Z_C^2=\operatorname{Id}, it follows that TC\mathcal{T}_C and −TC-\mathcal{T}_C are similar, and therefore the eigenvalues of TC\mathcal{T}_C, with multiplicity, are invariant under t↦−tt\mapsto-t. In particular, since 11 is an eigenvalue of TC\mathcal{T}_C by (ii), so is −1-1.

Now assume, by contradiction, that TC\mathcal{T}_C has exactly two non-real eigenvalues, tt and tˉ\bar{t}. By the above invariance, −t-t is also a non-real eigenvalue of TC\mathcal{T}_C, therefore −t∈{t,tˉ}-t\in\{t,\bar{t}\}. Since t≠0t\ne0 by (i), we have that −t≠t-t\ne t, and therefore −t=tˉ-t=\bar{t}. This means that tt is purely imaginary, that is, t=iγt=i\gamma for some γ∈R\gamma\in\mathbb{R} with γ≠0\gamma\ne0. Moreover, ∣γ∣=∣t∣≤1|\gamma|=|t|\le1 by (ii).

We now separate, in (6), one copy of the eigenvalue 11, one copy of the eigenvalue −1-1, and the two eigenvalues iγi\gamma and −iγ-i\gamma. Denoting by II the set of indices of the remaining eigenvalues, which are all real, we obtain

0=∑k=1mtk2=12+(−1)2+(iγ)2+(−iγ)2+∑k∈Itk2=2−2γ2+∑k∈Itk2.0=\sum_{k=1}^{m}t_k^2=1^2+(-1)^2+(i\gamma)^2+(-i\gamma)^2+\sum_{k\in I}t_k^2=2-2\gamma^2+\sum_{k\in I}t_k^2.

Since ∣γ∣≤1|\gamma|\le1, we have that 2−2γ2≥02-2\gamma^2\ge0, and by (i), tk2>0t_k^2>0 for every k∈Ik\in I. Hence, both 2−2γ22-2\gamma^2 and the sum over II must vanish, that is, γ2=1\gamma^2=1 and I=∅I=\varnothing. Therefore, the only eigenvalues of TC\mathcal{T}_C are 11, −1-1, ii, and −i-i, each with multiplicity one. Since TC\mathcal{T}_C is a 2MC×2MC2M_C\times2M_C matrix, this implies that MC=2M_C=2. However, since every vertex of CC has degree at least 22, we have

2MC=∑v∈V(C)deg⁡v≥2∣V(C)∣.2M_C=\sum_{v\in V(C)}\deg v\ge2|V(C)|.

implying that MC≥∣V(C)∣≥3M_C\ge|V(C)|\ge3. This is a contradiction, and therefore TC\mathcal{T}_C has at least four non-real eigenvalues.

Finally, for the cycle C4C_4, we have that M=N=4M=N=4 and c=b=1c=b=1, therefore

2M−2N+2c+2b=4=2M−2c−2b.2M-2N+2c+2b=4=2M-2c-2b.

Together with Theorem 4.1, this shows that L\mathcal{L} has exactly 44 real eigenvalues, and that the bound is attained.

Declaration of AI assistance

The proofs presented in this paper were developed with the assistance of ChatGPT-6.1 Sol (OpenAI) and Claude Opus 5.5 (Anthropic). All proofs were checked in detail by the authors, who take full responsibility for the content.

Funding

Raffaella Mulas is supported by the Dutch Research Council (NWO) through the grant VI.Veni.232.002 (Grant ID: https://doi.org/10.61686/NLUFV33835).

References

  1. [1]F. Arrigo, D.J. Higham, and V. Nof erini. Beyond non-backtracking: non-cycling network centrality measures. Proceedings. Mathematical, Physical, and Engineering Sciences, 476, 2020.DOI
  2. [2]F. Arrigo, D.J. Higham, V. Noferini, and R. Wood. Weighted enumeration of nonbacktracking walks on weighted graphs. SIAM Journal on Matrix Analysis and Applications, 45(1):397–418, 2024.arxiv.org/abs/2202.02888
  3. [3]Á. Backhausz, B. Szegedy, and B. Virág. Ramanujan graphings and correlation decay in local algorithms. Random Structures & Algorithms, 47(3):424–435, 2015.DOI
  4. [4]H. Bass. The Ihara-Selberg zeta function of a tree lattice. International Journal of Mathematics, 3(06):717–797, 1992.DOI
  5. [5]M. Bolla. The non-backtracking random walk and its usage for vertex clustering. arXiv preprint arXiv:2512.24434, 2025.arxiv.org/abs/2512.24434
  6. [6]M. Bolla, H. Reittu, and F. Abdelkhalek. Clustering the nodes of sparse edge-weighted graphs via non-backtracking spectra. In Future of Information and Communication Conference, pages 81–99. Springer, 2025.DOI
  7. [7]C. Bordenave, M. Lelarge, and L. Massoulié. Nonbacktracking spectrum of random graphs: Community detection and nonregular Ramanujan graphs. Annals of probability: An official journal of the Institute of Mathematical Statistics, 46(1):1–71, 2018.
  8. [8]A.E. Brouwer and W.H. Haemers. Spectra of graphs. Springer Science & Business Media, 2011.
  9. [9]C. Castellano and R. Pastor-Satorras. Relevance of backtracking paths in recurrent-state epidemic spreading on networks. Physical Review E, 98(5):052313, 2018.DOI
  10. [10]F. Chung. Spectral graph theory. American Mathematical Soc., 1997.
  11. [11]Y. Cooper. Properties determined by the Ihara zeta function of a graph. The Electronic Journal of Combinatorics, 16(1):R84, 2009.DOI
  12. [12]S. Coste and Y. Zhu. Eigenvalues of the non-backtracking operator detached from the bulk. Random Matrices: Theory and Applications, 10(03):2150028, 2021.DOI
  13. [13]C. Glover and M. Kempton. Some spectral properties of the non-backtracking matrix of a graph. Linear Algebra and its Applications, 618:37–57, 2021.DOI
  14. [14]I. Gohberg, P. Lancaster, and L. Rodman. Indefinite linear algebra and applications. Springer Science & Business Media, 2006.DOI
  15. [15]P. Grindrod, D.J. Higham, and V. Noforini. The Deformed Graph Laplacian and Its Applications to Network Centrality Analysis. SIAM Journal on Matrix Analysis and Applications, 39(1):310–341, 2018.DOI
  16. [16]K. Hashimoto. Zeta functions of finite graphs and representations of p-adic groups. In Automorphic Forms and Geometry of Arithmetic Varieties, volume 15 of Advanced Studies in Pure Mathematics, pages 211–280. Elsevier, 1989.
  17. [17]J. Jost, R. Mulas, and L. Torres. Spectral theory of the non-backtracking Laplacian for graphs. Discrete Mathematics, 346(10):113536, 2023.DOI
  18. [18]J. Jost, R. Mulas, and D. Zhang. Spectra of Discrete Structures. Number 221 in Cambridge Studies in Advanced Mathematics. Cambridge University Press, 2026.DOI
  19. [19]M. Kempton. Non-backtracking random walks and a weighted Ihara’s theorem. Open Journal of Discrete Mathematics, 6(4):207–226, 2016.arxiv.org/abs/1603.05553
  20. [20]F. Krzakala, C. Moore, E. Mossel, J. Neeman, A. Sly, L. Zdeborová, and P. Zhang. Spectral redemption in clustering sparse networks. Proceedings of the National Academy of Sciences, 110(52):20935–20940, 2013.DOI
  21. [21]A. Lubotzky, R. Phillips, and P. Sarnak. Ramanujan graphs. Combinatorica, 8(3):261–277, 1988.
  22. [22]T. Martin, X. Zhang, and M.E.J. Newman. Localization and centrality in networks. Physical Review E, 90(5):052808, 2014.DOI
  23. [23]A. Mellor and A. Grusovin. Graph comparison via the nonbacktracking spectrum. Phys. Rev. E, 99:052309, May 2019.DOI
  24. [24]R. Mulas. Maximal colourings for graphs. Graphs and Combinatorics, 40(93), 2024.arxiv.org/abs/2307.10910
  25. [25]R. Mulas. Spectral theory of graphs and hypergraphs. Lecture notes for the BeyondTheEdge MSCA Doctoral Network, Marseille, France, 2025. Available at https://cdn.prod.website-files.com/673b1c6a31679f06b3ecf571/68d3daeb1b89a52be5dee00e_Marseille-LectureNotes-RM.pdf (Accessed October 2026).
  26. [26]R. Mulas, D. Zhang, and G. Zucal. There is no going back: Properties of the non-backtracking Laplacian. Linear Algebra Appl., 680:341–370, 2024.arxiv.org/abs/2303.00373
  27. [27]M.R. Murty. Ramanujan graphs. Journal of the Ramanujan Mathematical Society, 18(1):33–52, 2003.
  28. [28]R. Pastor-Satorras and C. Castellano. The localization of non-backtracking centrality in networks and its physical consequences. Scientific reports, 10(1):1–12, 2020.
  29. [29]M. Shrestha, S.V. Scarpino, and C. Moore. Message-passing approach for recurrent-state epidemic models on networks. Physical Review E, 92(2):022821, 2015.pubmed.ncbi.nlm.nih.gov/26382468
  30. [30]A. Terras. Zeta functions of graphs: A stroll through the garden, volume 128 of Cambridge studies in advanced mathematics. Cambridge University Press, 2010.DOI
  31. [31]L. Torres, K.S. Chan, H. Tong, and T. Eliassi-Rad. Nonbacktracking eigenvalues under node removal: X-centrality and targeted immunization. SIAM Journal on Mathematics of Data Science, 3(2):656–675, 2021.DOI
  32. [32]L. Torres, P. Suárez-Serrato, and T. Eliassi-Rad. Non-backtracking cycles: length spectrum theory and graph mining applications. Applied Network Science, 4(1):1–35, 2019.DOI

Paper details

vlnc:W_6ns2xrph
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

GPT-6.1 Sol (bare), Claude Opus 5.5 (bare)

View statement
Looking for related papers…
Contents