# The real eigenvalues of the non-backtracking Laplacian
:config: {
:numbering: section
}
::
% A preamble written as :mathblock: does not reach inline math (bead rsm-keu
% in the RSM repo), so the macros are defined in an inline preamble.
:math: {:preamble:} \newcommand{\inp}{\operatorname{in}} \newcommand{\out}{\operatorname{out}} \newcommand{\id}{\operatorname{Id}} \newcommand{\mathbbm}[1]{\unicode{x1D7D9}} ::
:author: {
:name: Raffaella Mulas
:email: r.mulas@vu.nl
:affiliation: Vrije Universiteit Amsterdam, Amsterdam, The Netherlands
} ::
:author: {
:name: Leo Torres
:email: leo@leotrs.com
:affiliation: Independent researcher, Leipzig, Germany
} ::
:abstract: {
:keywords: {non-backtracking random walks, spectral graph theory, non-backtracking matrix, non-backtracking Laplacian, Ramanujan graphs}
}
Let $G$ be a simple graph on $N$ nodes and $M$ edges, with minimum degree at least $2$. We prove that the non-backtracking Laplacian of $G$ has at least $2M-2N+2c+2b$ real eigenvalues, counted with algebraic multiplicity, where $c$ is the number of connected components of $G$ and $b$ is the number of bipartite ones. More precisely, at least $M-N+2c$ of them lie in $[0,1)$ and at least $M-N+2b$ lie in $(1,2]$. We show that the bound $2M-2N+2c+2b$ is sharp, and that a connected $d$-regular graph attains it if and only if it is strictly Ramanujan, i.e., every adjacency eigenvalue $\mu\ne\pm d$ satisfies $|\mu|<2\sqrt{d-1}$. For completeness, we also show that the non-backtracking Laplacian has at most $2M-2c-2b$ real eigenvalues.
::
:toc:
::
## 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 :cite:chung,brouwer,BookJMZ:: 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 :cite:hashimoto1989zeta::, in the context of zeta functions of graphs, and they have since proved useful in many areas, including algebraic graph theory :cite:terras2010zeta,bass1992ihara,cooper2009::, the study of Ramanujan graphings :cite:backhausz2015ramanujan::, epidemic spreading :cite:shrestha2015message,castellano2018relevance::, community detection :cite:krzakala2013spectral,bordenave2018nonbacktracking,bolla2025clustering::, and centrality measures :cite:martin2014localization,torres2021nonbacktracking::. We refer to :cite:torres2019non,coste2021eigenvalues,glover2021some,pastor2020localization,Arrigo1,Arrigo2,Gronford1,Mellor1,bolla2025non:: 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)$ be a simple graph on $N$ nodes and $M$ edges, with minimum degree at least $2$. Each edge of $G$ admits two *orientations*, and we write $[v,w]$ for the *oriented edge* with *input* $\inp([v,w])\coloneqq v$ and *output* $\out([v,w])\coloneqq w$. Its inverse is $[v,w]^{-1}\coloneqq[w,v]$. This gives $2M$ oriented edges, which we label as $e_1,\ldots,e_{2M}$ in such a way that
$$ {:nonum:}
e_{M+i}=e_i^{-1},\quad \text{for } i=1,\ldots,M.
$$
A *non-backtracking random walk* on $G$ is a discrete-time Markov process on the oriented edges such that the probability of going from $e_i$ to $e_j$ is
$$ {:nonum:}
\mathbb{P}(e_i\rightarrow e_j)=\begin{cases}\frac{1}{\deg(\out(e_i))-1} & \text{if }\out(e_i)=\inp(e_j)\text{ and }e_j\neq e_i^{-1},\\
0 & \text{otherwise.}
\end{cases}
$$
In particular, the assumption that $G$ has minimum degree at least $2$ guarantees that the denominator is always positive. Moreover, one can also see a non-backtracking random walk as a process on $V$, but in this case the probability that the walker moves from a vertex $v$ to one of its neighbors depends on the vertex she came from. Hence, this process is not Markovian on $V$.
Non-backtracking random walks are encoded by the *non-backtracking graph* or *Hashimoto graph* of $G$, denoted $\mathcal{G}$, which is the directed graph whose vertices are the $2M$ oriented edges of $G$, and which has a directed edge from $e_i$ to $e_j$ if and only if $$ {:nonum:}
\out(e_i)=\inp(e_j) \text{ and } e_j\neq e_i^{-1},
$$ i.e., if and only if a non-backtracking random walk can go from $e_i$ to $e_j$ in one step. The adjacency matrix of $\mathcal{G}$ is the $2M\times 2M$ matrix $\mathcal{A}$ with $(0,1)$–entries such that
$$ {:nonum:}
\mathcal{A}_{ij}=1\iff \out(e_i)=\inp(e_j) \text{ and } e_j\neq e_i^{-1},
$$
and its transpose $\mathcal{A}^\top$ is the *non-backtracking matrix* of $G$ introduced by Hashimoto :cite:hashimoto1989zeta::. Moreover, a random walk on $\mathcal{G}$ is precisely a non-backtracking random walk on $G$. Since each vertex $e_i$ of $\mathcal{G}$ has (out-)degree $$ {:nonum:}
\deg_{\mathcal{G}}(e_i)=\deg(\out(e_i))-1\geq 1,
$$ the random walk Laplacian of $\mathcal{G}$ is well-defined, and it is called the *non-backtracking Laplacian* of $G$. It can be written as
$$ {:nonum:}
\mathcal{L}\coloneqq\id-\mathcal{D}^{-1}\mathcal{A}=\id-\mathcal{T},
$$
where $\id$ denotes the identity matrix, $\mathcal{D}$ is the degree matrix of $\mathcal{G}$ and has diagonal entries $$ {:nonum:}
\mathcal{D}_{ii}:=\deg_{\mathcal{G}}(e_i),
$$
and $\mathcal{T}\coloneqq\mathcal{D}^{-1}\mathcal{A}$ is the transition probability matrix of the non-backtracking random walk on $G$.
We introduced the non-backtracking Laplacian in :cite:JMT2023::, together with J. Jost. Its spectral properties were further investigated in :cite:MZZ::, its connection to graph colorings was studied in :cite:maximal-colouring::, and it has been applied to vertex clustering in :cite:bolla2025clustering::. The computations in Table 2 of :cite:JMT2023:: 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 $\mathcal{L}$ spectrum. Moreover, in the same paper we showed that the presence of certain cycle configurations produces real eigenvalues of $\mathcal L$.
For the non-backtracking matrix, the Ihara–Bass formula :cite:bass1992ihara,terras2010zeta,Kempton2016::,
$$ {:label: eq-Ihara}
\det(\id-u\mathcal{A})=(1-u^2)^{M-N}\det\bigl(\id-uA+u^2(D-\id)\bigr),
$$
where $A$ and $D$ are the adjacency and degree matrices of $G$, gives at least $2M-2N$ real
eigenvalues for each of $\mathcal A$ and $\mathcal A^\top$,
counted with algebraic multiplicity. If $G$ is $d$–regular, then
$$ {:nonum:}
\mathcal L=\mathrm{Id}-\frac{1}{d-1}\mathcal A.
$$
Therefore, in this case, $\mathcal L$ also has at least $2M-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 $\mathcal L$. It is therefore natural to ask whether the lower bound $2M-2N$
nevertheless holds for the non-backtracking Laplacian.
Motivated by numerical experiments, we conjectured in 2022 that $\mathcal L$ always has at least $2M-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 Exercise 13 of :cite:Mulas2025LectureNotes::.
Here we prove this conjecture, and we refine it as follows.
:theorem: {
:title: Theorem 4.1 and Corollary 5.2
:nonum:
}
Let $G$ be a simple graph on $N$ nodes and $M$ edges, with minimum degree at least $2$. Let $c$ be the number of connected components of $G$, and let $b$ be the number of bipartite ones. Then, the number of real eigenvalues of the non-backtracking Laplacian of $G$, counted with algebraic multiplicity, is at least
$$ {:nonum:}
2M-2N+2c+2b.
$$
Moreover, this bound is sharp.
::
:html: {
:path: figs/explorer.html
:label: fig-explorer
}
:caption: The eigenvalues of $\mathcal{L}$ for the graph on the left, which can be edited, counted with algebraic multiplicity and compared with the bounds of :ref:thm-refined::, :ref:thm-split:: and :ref:thm-upper::. No eigenvalue lies in the shaded disk $|1-\lambda|<1/(\Delta-1)$. The bar below the plot shows all $2M$ eigenvalues, real ones first, with the lower and upper bounds marked.
::
For connected regular graphs, we also determine exactly when the above bound is attained. Recall that a connected $d$–regular graph is *Ramanujan* :cite:lubotzky1988ramanujan,murty2003ramanujan:: if every adjacency eigenvalue $\mu\neq\pm d$ satisfies $$ {:nonum:}
|\mu|\leq 2\sqrt{d-1}.
$$ We call it *strictly Ramanujan* if every adjacency eigenvalue $\mu\neq\pm d$ satisfies $$ {:nonum:}
|\mu|<2\sqrt{d-1}.
$$
We show that, for a connected regular graph $G$, the non-backtracking Laplacian has exactly $2M-2N+2+2b$ real eigenvalues if and only if $G$ 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 :ref:thm-split::, we show that at least $\class{nbl lk lk-ex-low}{M-N+2c}$ of them lie in $\class{nbl lk lk-ex-low}{[0,1)}$ and at least $\class{nbh lk lk-ex-high}{M-N+2b}$ lie in $\class{nbh lk lk-ex-high}{(1,2]}$.
For completeness, we also prove in :ref:thm-upper:: that
$\mathcal L$ has at most $2M\class{nbc lk lk-ex-cplx}{-2c-2b}$ real eigenvalues, counted with algebraic multiplicity, and that this bound is attained by the cycle $C_4$.
### Structure of the paper {
:nonum:
}
In :ref:section-prelimnaries::, we fix the notation and establish some preliminary results, including :ref:lemma-LA:: from indefinite linear algebra. In :ref:section-2M-2N::, we prove :ref:thm-2022::, which settles our 2022 conjecture. In :ref:section-refined::, we refine this bound by taking into account the connected and bipartite components of the graph, thus proving :ref:thm-refined::. In :ref:section-sharpness::, 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 :ref:section-signs::, we show how the real eigenvalues split around $1$. Finally, in :ref:section-upper::, we prove an upper bound on the number of real eigenvalues of the non-backtracking Laplacian.
## Notation and preliminaries {
:label: section-prelimnaries
}
Throughout the paper, we fix a simple graph $G=(V,E)$ on $N$ nodes and $M$ edges, with minimum degree at least $2$, and we use the same notation as in the introduction. In particular, $\mathcal{G}=(\mathcal{V},\mathcal{E})$ denotes the non-backtracking graph of $G$, whose vertices are the $2M$ oriented edges $e_1,\ldots,e_{2M}$ of $G$, labeled so that
$$ {:nonum:}
e_{M+i}=e_i^{-1},\quad \text{for } i=1,\ldots,M.
$$
Moreover, $\mathcal{A}$ and $\mathcal{D}$ denote the adjacency and degree matrices of $\mathcal{G}$, while $\mathcal{L}=\id-\mathcal{D}^{-1}\mathcal{A}$ and $\mathcal{T}=\mathcal{D}^{-1}\mathcal{A}$ denote the non-backtracking Laplacian and the transition matrix of the non-backtracking random walk on $G$.
We identify each vector $f\in\mathbb{C}^{2M}$ with the function
$$ {:nonum:}
\begin{aligned}
f\colon\mathcal{V} &\rightarrow \mathbb{C}\\
e_i&\mapsto f_i.
\end{aligned}
$$
In these terms, the transition matrix acts as
$$ {:label: eq-mathcalT}
(\mathcal{T}f)([v,w])=\frac{1}{\deg w-1}\sum_{z\sim w,\,z\neq v}f([w,z]),
$$
for every $[v,w]\in \mathcal{V}$, where $z\sim w$ means that $z$ and $w$ are adjacent in $G$.
Given a real symmetric matrix $K\in\mathbb{R}^{r\times r}$, the *$K$-product* on $\mathbb{C}^r$ is defined as
$$ {:nonum:}
(\mathbf{x},\mathbf{y})_K\coloneqq\langle\mathbf{x},K\mathbf{y}\rangle=\overline{\mathbf{x}}^\top K\mathbf{y},
$$
where $\langle\cdot,\cdot\rangle$ is the standard inner product on $\mathbb{C}^r$. A matrix $R\in\mathbb{R}^{r\times r}$ is said to be *self-adjoint with respect to the $K$-product*, or *$K$-self-adjoint*, if $$ {:nonum:}
(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
$$ {:nonum:}
R^\top K=KR.
$$
As in :cite:JMT2023::, we let $P$ be the $2M\times 2M$ matrix
$$ {:nonum:}
P\coloneqq\begin{pmatrix}0&\id\\ \id&0\end{pmatrix},
$$
where each block has size $M\times M$. Since $e_{M+i}=e_i^{-1}$, we have that $$ {:nonum:}
(Pf)(e)=f(e^{-1}) \text{ for each }e\in\mathcal{V}.
$$
Moreover, by Theorem 3.8 of :cite:JMT2023::, $\mathcal{L}$ is $P$-self-adjoint, that is,
$$ {:label: eq-LP}
\mathcal{L}^\top P=P\mathcal{L}.
$$
We now introduce the matrix
$$ {:nonum:}
H\coloneqq P(\id-\mathcal{L})=P\mathcal{T}.
$$ Its entries are
$$ {:nonum:}
H_{ij}=\begin{cases}
\frac{1}{\deg(\inp(e_i))-1} & \text{if } \inp(e_i)=\inp(e_j) \text{ and } e_i\neq e_j,\\
0 & \text{otherwise.}
\end{cases}
$$
In particular, $H$ is real and symmetric. Moreover, $\mathcal{L}$ is $H$-self-adjoint. In fact, by :ref:eq-LP:: and since $\mathcal{L}$ commutes with $\id-\mathcal{L}$,
$$ {:label: eq-LH}
\mathcal{L}^\top H=\mathcal{L}^\top P(\id-\mathcal{L})=P\mathcal{L}(\id-\mathcal{L})=P(\id-\mathcal{L})\mathcal{L}=H\mathcal{L}.
$$
The matrix $H$ plays a central role in the proofs of our main results, for the following reason. By :ref:lemma-LA:: below, if a real matrix $R$ is self-adjoint with respect to the $K$-product of a real symmetric invertible matrix $K$, then $R$ has at most $2\min\bigl(n_+(K),n_-(K)\bigr)$ non-real eigenvalues, where $n_+(K)$ and $n_-(K)$ denote the numbers of positive and negative eigenvalues of $K$, counted with multiplicity. By :ref:eq-LP::, $\mathcal{L}$ is $P$-self-adjoint. However, $P$ has eigenvalues $1$ and $-1$, each with multiplicity $M$, so in this case the lemma only says that $\mathcal{L}$ has at most $2M$ non-real eigenvalues, which is trivial since $\mathcal{L}$ is a $2M\times 2M$ matrix. The advantage of considering $H$ is that $\mathcal{L}$ is also $H$-self-adjoint, by :ref:eq-LH::, and $H$ has only $N$ positive eigenvalues and $2M-N$ negative ones, by :ref:lemma-H:: below. Since every vertex of $G$ has degree at least $2$, we have that $$ {:nonum:}
2M=\sum_{v\in V}\deg v\geq 2N,
$$ and therefore
$$ {:label: eq-minN}
\min\bigl(n_+(H),n_-(H)\bigr)=\min\bigl(N,2M-N\bigr)=N.
$$
Hence, by :ref:lemma-LA::, $\mathcal{L}$ has at most $2N$ non-real eigenvalues, that is, at least $2M-2N$ real ones. This is the content of :ref:thm-2022::. For the refinement in :ref:thm-refined::, we then use the connected and bipartite components of $G$ to reduce the number of positive eigenvalues of $H$ that need to be taken into account.
We first prove the claim on the eigenvalues of $H$.
:lemma: {:label: lemma-H}
The matrix $H$ is invertible. Moreover,
$$ {:nonum:}
n_+(H)=N\qquad\text{and}\qquad n_-(H)=2M-N.
$$
::
:proof:
By definition of $H$, we have that $H_{ij}=0$ whenever $\inp(e_i)\neq\inp(e_j)$. Hence, if we order the oriented edges according to their input, $H$ is block diagonal, with one block $H_v$ of size $\deg v\times\deg v$ for each $v\in V$. Moreover,
$$ {:nonum:}
H_v=\frac{1}{\deg v-1}\bigl(J_{\deg v}-\id\bigr),
$$
where $J_{\deg v}$ denotes the $\deg v\times\deg v$ matrix whose entries are all equal to $1$. Since $J_{\deg v}$ has eigenvalue $\deg v$ with multiplicity $1$, and eigenvalue $0$ with multiplicity $\deg v-1$, the block $H_v$ has eigenvalue $1$ with multiplicity $1$, and eigenvalue $-1/(\deg v-1)$ with multiplicity $\deg v-1$. The eigenvalues of $H$, with multiplicity, are those of the blocks $H_v$. Since none of them is zero, $H$ is invertible, and
$$ {:nonum:}
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 $R$, we let $n_{\mathbb{R}}(R)$ denote the number of real eigenvalues of $R$, counted with algebraic multiplicity.
:lemma: {:label: lemma-LA}
Let $K\in\mathbb{R}^{r\times r}$ be symmetric and invertible, and let $R\in\mathbb{R}^{r\times r}$ be $K$-self-adjoint. Then, $R$ has at most $2\min\bigl(n_+(K),n_-(K)\bigr)$ non-real eigenvalues, counted with algebraic multiplicity. Equivalently,
$$ {:nonum:}
n_{\mathbb{R}}(R)\geq r-2\min\bigl(n_+(K),n_-(K)\bigr).
$$
::
:proof:
Since $R$ is $K$-self-adjoint, it follows from page 77 of :cite:gohberg2006indefinite:: (see the inequality following equation (5.2.4) and the comment after it, where $A=R$, $H=K$ and $i_-(H)=n_-(K)$ in our notation) that $n_-(K)$ is at least half the number of non-real eigenvalues of $R$, counted with algebraic multiplicity. Since $R$ is also $(-K)$-self-adjoint, and since $n_-(-K)=n_+(K)$, the same holds for $n_+(K)$. Therefore, the number of non-real eigenvalues of $R$ is at most $2\min\bigl(n_+(K),n_-(K)\bigr)$.
::
## The bound 2M − 2N {
:label: section-2M-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-2N$ real eigenvalues. As anticipated in :ref:section-prelimnaries::, this follows by combining the $H$-self-adjointness of $\mathcal{L}$ with :ref:lemma-H:: and :ref:lemma-LA::.
:theorem: {:label: thm-2022}
Let $G$ be a simple graph on $N$ nodes and $M$ edges, with minimum degree at least $2$. Then, the number of real eigenvalues of the non-backtracking Laplacian of $G$, counted with algebraic multiplicity, is at least
$$ {:nonum:}
2M-2N.
$$
::
:proof:
By :ref:eq-LH::, $\mathcal{L}$ is $H$-self-adjoint, and by :ref:lemma-H::, $H$ is a real symmetric invertible matrix with $n_+(H)=N$ and $n_-(H)=2M-N$. As observed in :ref:eq-minN::, the minimum degree assumption implies that
$$ {:nonum:}
\min\bigl(n_+(H),n_-(H)\bigr)=N.
$$
Applying :ref:lemma-LA:: with $R=\mathcal{L}$ and $K=H$ yields
$$ {:nonum:}
n_{\mathbb{R}}(\mathcal{L})\geq 2M-2N.
$$
::
## The refined bound {
:label: section-refined
}
In this section, we refine :ref:thm-2022:: by taking into account the connected and bipartite components of $G$. These give explicit eigenvectors of $\mathcal{L}$ with real eigenvalues, which allow us to reduce the number of positive eigenvalues of $H$ that need to be taken into account in :ref:lemma-LA::.
:theorem: {:label: thm-refined}
Let $G$ be a simple graph on $N$ nodes and $M$ edges, with minimum degree at least $2$. Let $c$ be the number of connected components of $G$, and let $b$ be the number of bipartite ones. Then, the number of real eigenvalues of the non-backtracking Laplacian of $G$, counted with algebraic multiplicity, is at least
$$ {:nonum:}
2M-2N+2c+2b.
$$
::
:proof:
For each connected component $C$ of $G$, let $V(C)$ be the vertex set of $C$, let $E(C)$ be its edge set, and let $\mathbbm{1}_C\colon\mathcal{V}\to\{0,1\}$ be the indicator function of the oriented edges of $C$. If $C$ is bipartite, fix a function $s_C\colon V(C)\to\{1,-1\}$ that takes opposite values on adjacent vertices, and let
$$ {:nonum:}
\begin{aligned}
\sigma_C\colon\mathcal{V}&\to\{0,1,-1\}\\
[v,w]&\mapsto\begin{cases}
s_C(v), & \text{if } [v,w] \text{ is an oriented edge of } C,\\
0, & \text{otherwise.}
\end{cases}
\end{aligned}
$$
By :ref:eq-mathcalT:: we have that, for every $[v,w]\in\mathcal{V}$,
$$ {:nonum:}
\begin{aligned}
(\mathcal{T}\mathbbm{1}_C)([v,w])&=\frac{1}{\deg w-1}\sum_{z\sim w,\,z\neq v}\mathbbm{1}_C([w,z])\\
&=\begin{cases}
1 & \text{if } [v,w] \text{ is an oriented edge of } C,\\
0 & \text{otherwise.}
\end{cases}
\end{aligned}
$$
Hence, $\mathcal{T}\mathbbm{1}_C=\mathbbm{1}_C$. Similarly, for every $[v,w]\in\mathcal{V}$, by definition of $P$, and since $[v,w]$ and $[w,v]$ belong to the same connected component,
$$ {:nonum:}
(P\mathbbm{1}_C)([v,w])=\mathbbm{1}_C([w,v])=\mathbbm{1}_C([v,w]).
$$
Hence, $P\mathbbm{1}_C=\mathbbm{1}_C$. Moreover, if $C$ is bipartite and $[v,w]$ is in $C$, then $s_C(w)=-s_C(v)$. Since each oriented edge $[w,z]$ with $z\sim w$ also belongs to $C$, this implies that, by :ref:eq-mathcalT::,
$$ {:nonum:}
\begin{aligned}
(\mathcal{T}\sigma_C)([v,w])&=\frac{1}{\deg w-1}\sum_{z\sim w,\,z\neq v}\sigma_C([w,z])\\ &=\frac{1}{\deg w-1}\sum_{z\sim w,\,z\neq v}s_C(w)\\ &=-s_C(v),
\end{aligned}
$$
and by definition of $P$,
$$ {:nonum:}
(P\sigma_C)([v,w])=\sigma_C([w,v])=s_C(w)=-s_C(v).
$$
Together with the fact that both $\mathcal{T}\sigma_C$ and $P\sigma_C$ vanish outside $C$, this implies that
$$ {:nonum:}
\mathcal{T}\sigma_C=-\sigma_C\qquad\text{and}\qquad P\sigma_C=-\sigma_C.
$$
Since $H=P\mathcal{T}$ and $\mathcal{L}=\id-\mathcal{T}$, from the above equalities it follows that
$$ {:nonum:}
H\mathbbm{1}_C=\mathbbm{1}_C,\qquad\mathcal{L}\mathbbm{1}_C=\mathbf{0},\qquad H\sigma_C=\sigma_C,\qquad\mathcal{L}\sigma_C=2\sigma_C.
$$
Now, let $W\subseteq\mathbb{C}^{2M}$ be the span of the functions $\mathbbm{1}_C$, for all connected components $C$, and $\sigma_C$, for all bipartite components $C$. These $c+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 $C$,
$$ {:nonum:}
\begin{aligned}
\langle\mathbbm{1}_C,\sigma_C\rangle&=\sum_{e\in\mathcal{V}}\mathbbm{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$. Moreover, $H\mathbf{w}=\mathbf{w}$ for every $\mathbf{w}\in W$, and since $W$ is spanned by eigenvectors of $\mathcal{L}$, it is $\mathcal{L}$-invariant, that is, $\mathcal{L}\mathbf{w}\in W$ for every $\mathbf{w}\in W$.
Now, for all $\mathbf{w}\in W$ and $\mathbf{x}\in\mathbb{C}^{2M}$, we have that
$$ {:nonum:}
(\mathbf{w},\mathbf{x})_H=\overline{\mathbf{w}}^\top H\mathbf{x}=\bigl(H\overline{\mathbf{w}}\bigr)^\top \mathbf{x}=\overline{H\mathbf{w}}^\top \mathbf{x}=\overline{\mathbf{w}}^\top \mathbf{x}=\langle \mathbf{w},\mathbf{x}\rangle,
$$
where the second equality holds because $H$ is symmetric, the third because $H$ is real, and the fourth because $H\mathbf{w}=\mathbf{w}$.
Therefore, if we let $W^\perp$ be the orthogonal complement of $W$ with respect to the standard inner product, then $W^\perp$ is also $\mathcal{L}$-invariant. In fact, let $\mathbf{x}\in W^\perp$ and $\mathbf{w}\in W$. Then, since $\mathcal{L}\mathbf{w}\in W$, we have that
$$ {:nonum:}
\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 $\mathcal{L}$ is $H$-self-adjoint, and the last one because $\mathbf{x}\in W^\perp$. Hence, $\mathcal{L}\mathbf{x}\in W^\perp$.
Now, let $Q$ be a real orthogonal matrix whose first $c$ columns are the vectors $\mathbbm{1}_C/\|\mathbbm{1}_C\|$, whose next $b$ columns are the vectors $\sigma_C/\|\sigma_C\|$, and whose remaining $2M-c-b$ columns form an orthonormal basis of $W^\perp$, which can be chosen real since $W$ is spanned by real vectors. In other words, $Q$ is the change of basis to an orthonormal basis adapted to the decomposition $\mathbb{C}^{2M}=W\oplus W^\perp$. Since both summands are $\mathcal{L}$-invariant, $Q^\top\mathcal{L}Q$ is block diagonal, and since the first $c+b$ columns of $Q$ are eigenvectors of $\mathcal{L}$, with eigenvalue $0$ for the first $c$ ones and $2$ for the next $b$ ones,
$$ {:nonum:}
Q^\top\mathcal{L}Q=\begin{pmatrix}\mathcal{L}_W&0\\0&\mathcal{L}_0\end{pmatrix},
$$
where $\mathcal{L}_W$ is the diagonal matrix with $c$ diagonal entries equal to $0$ and $b$ diagonal entries equal to $2$, and $\mathcal{L}_0$ is a real matrix of size $(2M-c-b)\times(2M-c-b)$.
Similarly, let $\mathbf{q}_j$ denote the $j$-th column of $Q$. Then $(Q^\top HQ)_{ij}=(\mathbf{q}_i,\mathbf{q}_j)_H$, and by the identity above, $(\mathbf{q}_i,\mathbf{q}_j)_H=\langle\mathbf{q}_i,\mathbf{q}_j\rangle$, which is $1$ if $i=j$ and $0$ otherwise, whenever $\mathbf{q}_i\in W$ or $\mathbf{q}_j\in W$. Hence
$$ {:nonum:}
Q^\top HQ=\begin{pmatrix}\id&0\\0&H_0\end{pmatrix},
$$
where $H_0$ is a real symmetric matrix of size $(2M-c-b)\times(2M-c-b)$.
Since $H$ is invertible, so is $H_0$. Moreover, by Sylvester's law of inertia and :ref:lemma-H::,
$$ {:nonum:}
n_+(H_0)=n_+(H)-(c+b)=N-c-b
$$
and
$$ {:nonum:}
n_-(H_0)=n_-(H)=2M-N.
$$
Since $Q^\top=Q^{-1}$, the identity $\mathcal{L}^\top H=H\mathcal{L}$ implies that
$$ {:nonum:}
(Q^\top\mathcal{L}Q)^\top(Q^\top HQ)=Q^\top\mathcal{L}^\top HQ=Q^\top H\mathcal{L}Q=(Q^\top HQ)(Q^\top\mathcal{L}Q),
$$
and comparing the lower right blocks gives $\mathcal{L}_0^\top H_0=H_0\mathcal{L}_0$. That is, $\mathcal{L}_0$ is $H_0$-self-adjoint. By :ref:eq-minN::, we have that $$ {:nonum:}
N-c-b\leq N\leq 2M-N,
$$ and therefore :ref:lemma-LA:: implies that $\mathcal{L}_0$ has at most $2(N-c-b)$ non-real eigenvalues, counted with algebraic multiplicity.
Finally, since $Q^\top\mathcal{L}Q$ is block diagonal,
$$ {:nonum:}
\det(t\,\id-\mathcal{L})=\det(t\,\id-\mathcal{L}_W)\cdot\det(t\,\id-\mathcal{L}_0)=t^c(t-2)^b\det(t\,\id-\mathcal{L}_0).
$$
Hence, every non-real eigenvalue of $\mathcal{L}$ is an eigenvalue of $\mathcal{L}_0$, with the same algebraic multiplicity, and therefore
$$ {:nonum:}
n_{\mathbb{R}}(\mathcal{L})\geq 2M-2(N-c-b)=2M-2N+2c+2b.
$$
::
## Sharpness {
:label: section-sharpness
}
In this section, we show that the bound in :ref:thm-refined:: is sharp. For connected regular graphs, we first determine exactly when it is attained: by :ref:thm-sharpness::, this happens if and only if the graph is strictly Ramanujan. As a consequence, in :ref:cor-sharp:: we obtain several explicit families of graphs attaining the bound.
:theorem: {:label: thm-sharpness}
Let $G$ be a connected $d$-regular graph with $d\geq 2$, and let $\kappa$ be the number of adjacency eigenvalues $\mu\neq\pm d$ of $G$ with $|\mu|\geq 2\sqrt{d-1}$, counted with multiplicity. Then,
$$ {:nonum:}
n_{\mathbb{R}}(\mathcal{L})=2M-2N+2+2b+2\kappa.
$$
In particular, equality in :ref:thm-refined:: holds if and only if $G$ is strictly Ramanujan, that is, every adjacency eigenvalue $\mu\ne\pm d$ satisfies $|\mu|<2\sqrt{d-1}$.
::
:proof:
Let $G$ be a connected $d$-regular graph on $N$ nodes and $M$ edges, with $d\geq 2$. Since $G$ is connected, we have that $c=1$, and therefore the quantity in :ref:thm-refined:: is
$$ {:nonum:}
2M-2N+2+2b,
$$
where $b=1$ if $G$ is bipartite, and $b=0$ otherwise.
Now, let $\mu_1,\ldots,\mu_N$ be the eigenvalues of the adjacency matrix $A$ of $G$, listed with multiplicity, and given $\mu\in\mathbb{R}$, let
$$ {:nonum:}
q_\mu(t)\coloneqq t^2-\frac{\mu}{d-1}\,t+\frac{1}{d-1}.
$$
Since $G$ is $d$-regular, we have that $D=d\,\id$ and
$$ {:nonum:}
\mathcal{T}=\frac{1}{d-1}\mathcal{A}.
$$
Hence, the Ihara–Bass formula :ref:eq-Ihara:: becomes
$$ {:nonum:}
\det(\id-u\mathcal{A})=(1-u^2)^{M-N}\prod_{j=1}^N\bigl(1-\mu_ju+(d-1)u^2\bigr).
$$
For $t\neq 0$, substituting $u=1/((d-1)t)$ and multiplying both sides by $t^{2M}$, we obtain
$$ {:nonum:}
\det(t\,\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)/2$ is non-negative. We now count the real roots of each factor, with multiplicity.
The first factor has $2(M-N)$ real roots, namely $1/(d-1)$ and $-1/(d-1)$, each with multiplicity $M-N$.
Since $G$ is connected and $d$-regular, $d$ is a simple eigenvalue of $A$. Moreover, $-d$ is an eigenvalue of $A$ if and only if $G$ is bipartite, in which case it is also simple. The corresponding quadratic factors are
$$ {:nonum:}
\class{nbl lk lk-ra-qd}{q_d(t)=(t-1)\left(t-\frac{1}{d-1}\right)}\qquad\text{and}\qquad \class{nbh lk lk-ra-qmd}{q_{-d}(t)=(t+1)\left(t+\frac{1}{d-1}\right)},
$$
which have two real roots each. Hence, the eigenvalues $\pm d$ contribute $\class{nbl lk lk-ra-qd}{2}+\class{nbh lk lk-ra-qmd}{2b}$ real roots.
For every other eigenvalue $\mu\neq\pm d$ of $A$, the discriminant of $q_\mu$ is
$$ {:nonum:}
\left(\frac{\mu}{d-1}\right)^2-\frac{4}{d-1}=\frac{\mu^2-4(d-1)}{(d-1)^2}.
$$
Therefore, $q_\mu$ has two real roots, counted with multiplicity, if $|\mu|\geq 2\sqrt{d-1}$, and two non-real roots if $|\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,
$$ {:nonum:}
n_{\mathbb{R}}(\mathcal{T})=2(M-N)+\class{nbl lk lk-ra-qd}{2}+\class{nbh lk lk-ra-qmd}{2b}+2\kappa.
$$
Since $\mathcal{L}=\id-\mathcal{T}$, this implies that
$$ {:nonum:}
n_{\mathbb{R}}(\mathcal{L})=2M-2N+2+2b+2\kappa.
$$
In particular, $\mathcal{L}$ has exactly $2M-2N+2+2b$ real eigenvalues if and only if $\kappa=0$, that is, if and only if $G$ is strictly Ramanujan.
::
:html: {
:path: figs/ramanujan.html
:label: fig-ramanujan
}
:caption: The eigenvalues $t$ of $\mathcal{T}$ for a connected $d$-regular graph, as in the proof of :ref:thm-sharpness::. Each adjacency eigenvalue $\mu$ of $G$ contributes the two roots of $q_\mu$, which are real if $|\mu|\geq 2\sqrt{d-1}$ and lie on the dashed circle $|t|=1/\sqrt{d-1}$ otherwise, and the first factor contributes $\pm 1/(d-1)$, each $M-N$ times. The slider moves one value of $\mu$, whose two roots are circled.
::
:corollary: {:label: cor-sharp}
The bound in :ref:thm-refined:: is attained by the following graphs:
:itemize:
:-: the cycle graph $C_N$, for every $N\geq 3$;
:-: the complete graph $K_N$, for every $N\geq 3$;
:-: the complete bipartite graph $K_{r,r}$, for every $r\geq 2$.
::
In particular, the bound in :ref:thm-refined:: is sharp.
::
:proof:
Since all these graphs are connected and regular, by :ref:thm-sharpness:: it suffices to show that they are strictly Ramanujan.
:itemize:
:-: The cycle $C_N$ is $2$-regular, and its adjacency eigenvalues are $2\cos(2\pi j/N)$, for $j=0,\ldots,N-1$. All of them except $\pm 2$ satisfy $|\mu|<2=2\sqrt{2-1}$.
:-: The complete graph $K_N$ is $(N-1)$-regular, and its only adjacency eigenvalue other than $N-1$ is $-1$, which satisfies $1<2\sqrt{N-2}$ for $N\geq 3$.
:-: The complete bipartite graph $K_{r,r}$ is $r$-regular, and its only adjacency eigenvalue other than $\pm r$ is $0$, which satisfies $0<2\sqrt{r-1}$ for $r\geq 2$.
::
This proves the claim.
::
## Splitting the real eigenvalues around 1 {
:label: section-signs
}
:ref:thm-refined:: counts the real eigenvalues of $\mathcal{L}$. In this section, we show how many of them must lie on each side of $1$. Equivalently, we count the positive and the negative real eigenvalues of $\mathcal{T}=\id-\mathcal{L}$.
Recall from Theorem 4.1 of :cite:JMT2023:: that every eigenvalue $\lambda$ of $\mathcal{L}$ satisfies $$ {:nonum:}
|1-\lambda|\geq \frac{1}{\Delta-1},
$$ where $\Delta$ is the largest degree of $G$. Hence, the real eigenvalues of $\mathcal{L}$ in $[0,1)$ actually lie in $[0,1-1/(\Delta-1)]$, and those in $(1,2]$ lie in $[1+1/(\Delta-1),2]$.
For a real symmetric matrix $K$, we define its *signature* as $$ {:nonum:}
\operatorname{sig}(K)\coloneqq n_+(K)-n_-(K).
$$ For a real square matrix $R$, we let $n_>(R)$ and $n_<(R)$ denote the numbers of positive and negative real eigenvalues of $R$, counted with algebraic multiplicity.
The following lemma, which refines :ref:lemma-LA::, is needed for the proof of :ref:thm-split:: below.
:lemma: {:label: lemma-signsplit}
Let $K\in\mathbb{R}^{r\times r}$ be symmetric and invertible, and let $R\in\mathbb{R}^{r\times r}$ be invertible and $K$-self-adjoint. Then,
$$ {:nonum:}
n_>(R)\geq\frac{\bigl|\operatorname{sig}(K)+\operatorname{sig}(KR)\bigr|}{2}\qquad\text{and}\qquad n_<(R)\geq\frac{\bigl|\operatorname{sig}(K)-\operatorname{sig}(KR)\bigr|}{2}.
$$
::
:proof:
The matrix $KR$ is real, symmetric and invertible, since $$ {:nonum:}
(KR)^\top=R^\top K=KR.
$$ By the canonical form for $K$-self-adjoint matrices Theorem 5.1.1 of :cite:gohberg2006indefinite::, there is an invertible matrix $S$ such that $S^{-1}RS$ and $S^*KS$ are block diagonal with matching blocks, as follows. Each Jordan block $J_m(\lambda)$ of a real eigenvalue $\lambda$ is paired with $\varepsilon P_m$, where $P_m$ is the $m\times m$ matrix with ones on the anti-diagonal and zeros elsewhere, and $\varepsilon\in\{1,-1\}$. Each pair of Jordan blocks $J_m(\lambda)\oplus J_m(\overline{\lambda})$ of a non-real eigenvalue $\lambda$ is paired with $P_{2m}$. Since $$ {:nonum:}
S^*KRS=(S^*KS)(S^{-1}RS),
$$ the matrices $S^*KS$ and $S^*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 $P_m$ has signature $1$ if $m$ is odd and $0$ if $m$ is even, and so does $P_mJ_m(\lambda)$ multiplied by $\operatorname{sgn}(\lambda)$, for real $\lambda\neq0$. For a pair of non-real eigenvalues, both blocks have signature $0$, since the span of the first $m$ basis vectors of the block is isotropic for both forms and has half the dimension. Therefore
$$ {:nonum:}
\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 $p$ and $q$ be the sums of $\varepsilon$ over such blocks with $\lambda>0$ and with $\lambda<0$, respectively. Then, $\operatorname{sig}(K)=p+q$ and $\operatorname{sig}(KR)=p-q$. Finally, $|p|$ is at most the number of blocks with $\lambda>0$, which is at most $n_>(R)$, and similarly $|q|\leq n_<(R)$.
::
Using :ref:lemma-signsplit::, we can now refine :ref:thm-refined:: as follows.
:theorem: {:label: thm-split}
Let $G$ be a simple graph on $N$ nodes and $M$ edges, with minimum degree at least $2$. Let $c$ be the number of connected components of $G$, and let $b$ be the number of bipartite ones. Then, $\mathcal{T}$ has at least $M-N+2c$ positive and at least $M-N+2b$ negative real eigenvalues, counted with algebraic multiplicity. Equivalently, $\mathcal{L}$ has at least $M-N+2c$ real eigenvalues in $[0,1)$ and at least $M-N+2b$ real eigenvalues in $(1,2]$.
::
:proof:
We use the notation of the proof of :ref:thm-refined::. Let $\mathcal{T}_0\coloneqq \id-\mathcal{L}_0$, so that $Q^\top\mathcal{T}Q$ is block diagonal with blocks $\id-\mathcal{L}_W$ and $\mathcal{T}_0$, and $Q^\top HQ=Q^\top P\mathcal{T}Q$ has blocks $\id$ and $H_0$.
Since $P\mathbbm{1}_C=\mathbbm{1}_C$ and $P\sigma_C=-\sigma_C$, the matrix $P$ maps $W$ to itself, and since $P$ is symmetric, it also maps $W^\perp$ to itself. Hence $Q^\top PQ$ is block diagonal, with a diagonal first block $P_W$ having $c$ entries equal to $1$ and $b$ entries equal to $-1$, and a second block $P_0$. Comparing the second blocks in $$ {:nonum:}
Q^\top HQ=(Q^\top PQ)(Q^\top\mathcal{T}Q)
$$ and in :ref:eq-LP:: gives
$$ {:nonum:}
H_0=P_0\mathcal{T}_0\qquad\text{and}\qquad \mathcal{T}_0^\top P_0=P_0\mathcal{T}_0.
$$
The matrix $P$ has eigenvalues $1$ and $-1$, each with multiplicity $M$. By Sylvester's law of inertia, $n_+(P_0)=M-c$ and $n_-(P_0)=M-b$, and from the proof of :ref:thm-refined::, $n_+(H_0)=N-c-b$ and $n_-(H_0)=2M-N$. Hence,
$$ {:nonum:}
\operatorname{sig}(P_0)=b-c\qquad\text{and}\qquad\operatorname{sig}(H_0)=2N-2M-c-b.
$$
Since $H_0$ is invertible, so is $\mathcal{T}_0$. :ref:lemma-signsplit:: with $K=P_0$ and $R=\mathcal{T}_0$ gives
$$ {:nonum:}
n_>(\mathcal{T}_0)\geq\frac{|(b-c)+(2N-2M-c-b)|}{2}=M-N+c
$$
and
$$ {:nonum:}
n_<(\mathcal{T}_0)\geq\frac{|(b-c)-(2N-2M-c-b)|}{2}=M-N+b,
$$
where we used $M\geq N$. Finally, the first block $\id-\mathcal{L}_W$ contributes the eigenvalue $1$ with multiplicity $c$ and the eigenvalue $-1$ with multiplicity $b$. The statement for $\mathcal{L}$ follows from $\mathcal{L}=\id-\mathcal{T}$ and the fact that all eigenvalues of $\mathcal{T}$ have modulus at most $1$, since $\mathcal{T}$ is row-stochastic.
::
Adding the two bounds of :ref:thm-split:: gives :ref:thm-refined::. Both bounds are attained by the strictly Ramanujan graphs of :ref:thm-sharpness::\: in the proof of that theorem, the factor $$ {:nonum:}
\bigl(t^2-1/(d-1)^2\bigr)^{M-N}
$$ contributes $M-N$ positive and $M-N$ negative roots, the eigenvalue $d$ of $A$ contributes the positive roots $1$ and $1/(d-1)$, and the eigenvalue $-d$, present exactly when $G$ is bipartite, contributes the negative roots $-1$ and $-1/(d-1)$.
:remark:
The results of this section do not depend on the particular weights $1/(\deg v-1)$, and they hold for any weighted matrix $\mathcal{T}_f\coloneqq C_f\mathcal{A}$, where $f$ is a positive function on the vertices and $C_f$ is the diagonal matrix with diagonal entries $(C_f)_{ee}\coloneqq f(\out(e))$. In fact, as in :ref:lemma-H::, $P\mathcal{T}_f$ is symmetric with $N$ positive and $2M-N$ negative eigenvalues, therefore :ref:lemma-signsplit:: shows that $\mathcal{T}_f$ has at least $\class{nbl lk lk-wt-pos}{M-N}$ positive and at least $\class{nbh lk lk-wt-neg}{M-N}$ negative real eigenvalues. The refinement by $2c$ and $2b$ can also be obtained, using the Perron–Frobenius Theorem in place of the explicit eigenvectors $\mathbbm{1}_C$ and $\sigma_C$. In particular, $\mathcal{T}$ corresponds to $f(v)=1/(\deg v-1)$, while $f\equiv 1$ gives the transpose of the non-backtracking matrix. Note, however, that the location of the real eigenvalues of $\id-\mathcal{T}$ in $[0,1)$ and $(1,2]$ uses the fact that $\mathcal{T}$ is row-stochastic, and it does not extend to arbitrary weights.
::
:html: {
:path: figs/weights.html
:label: fig-weights
}
:caption: The eigenvalues of $\mathcal{T}_f=C_f\mathcal{A}$ as the weights move from $f\equiv 1$ to $f(v)=1/(\deg v-1)$, which gives $\mathcal{T}$. At every step at least $M-N$ eigenvalues are real and positive and at least $M-N$ are real and negative. The dashed circle is $|t|=1$.
::
## An upper bound {
:label: section-upper
}
We now complement :ref:thm-refined:: with an upper bound on the number of real eigenvalues of $\mathcal{L}$.
:theorem: {:label: thm-upper}
Let $G$ be a simple graph on $N$ nodes and $M$ edges, with minimum degree at least $2$. Let $c$ be the number of connected components of $G$, and let $b$ be the number of bipartite ones. Then, the number of real eigenvalues of the non-backtracking Laplacian of $G$, counted with algebraic multiplicity, is at most
$$ {:nonum:}
2M-2c-2b.
$$ Moreover, this bound is attained by the cycle $C_4$.
::
:proof:
Since $\mathcal{L}=\id-\mathcal{T}$, it suffices to show that $\mathcal{T}$ has at least $2c+2b$ non-real eigenvalues, counted with algebraic multiplicity.
If we order the oriented edges of $G$ according to the connected components of $G$, then $\mathcal{T}$ is block diagonal, with one block $\mathcal{T}_C$ for each connected component $C$, and $\mathcal{T}_C$ is the transition matrix of the non-backtracking random walk on $C$. Hence, it suffices to show that each $\mathcal{T}_C$ has at least two non-real eigenvalues, and at least four if $C$ is bipartite. To this end, we use the following three facts.
:enumerate: {:class: paren-roman}
:-: All eigenvalues of $\mathcal{T}_C$ are non-zero. In fact, $\mathcal{T}=PH$ is invertible, since $P^2=\id$ and $H$ is invertible by :ref:lemma-H::, and the eigenvalues of $\mathcal{T}_C$ are eigenvalues of $\mathcal{T}$.
:-: Since $\mathcal{T}_C$ is row-stochastic, all eigenvalues $t$ of $\mathcal{T}_C$ satisfy $|t|\leq 1$. Moreover, for the same reason, $1$ is an eigenvalue of $\mathcal{T}_C$, with the constant functions as eigenfunctions.
:-: We have that $\operatorname{tr}(\mathcal{T}_C^2)=0$. In fact,
$$ {:nonum:}
\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 $e$ and $e'$ range over the oriented edges of $C$. If $(\mathcal{T}_C)_{ee'}(\mathcal{T}_C)_{e'e}\neq 0$, then both factors are non-zero, that is, a non-backtracking random walk can go from $e$ to $e'$ and from $e'$ to $e$. The first step requires $e'$ to start at the output of $e$, and the second one requires $e'$ to end at the input of $e$, therefore $e'=e^{-1}$. But the step from $e$ to $e^{-1}$ is excluded by the definition of a non-backtracking random walk. Hence, all terms in the above sum vanish.
::
Now, let $t_1,\ldots,t_m$ be the eigenvalues of $\mathcal{T}_C$, listed with algebraic multiplicity. Then, by (iii),
$$ {:label: eq-trace}
\sum_{k=1}^m t_k^2=\operatorname{tr}(\mathcal{T}_C^2)=0.
$$
By (i), every real eigenvalue $t_k$ of $\mathcal{T}_C$ satisfies $t_k^2>0$. Hence, by :ref:eq-trace::, $\mathcal{T}_C$ has at least one non-real eigenvalue. Since $\mathcal{T}_C$ is real, its non-real eigenvalues appear in complex conjugate pairs, and therefore $\mathcal{T}_C$ has at least two non-real eigenvalues.
Now, assume that $C$ is bipartite. Let $V(C)$ denote the vertex set of $C$, and let $M_C$ denote the number of edges of $C$. We want to show that, in this case, $\mathcal{T}_C$ cannot have exactly one pair of complex conjugate non-real eigenvalues. Since $C$ is bipartite, there exists a function $s\colon V(C)\to\{1,-1\}$ that takes opposite values on adjacent vertices. Hence, we can define the $2M_C\times 2M_C$ diagonal matrix $Z_C$ with diagonal entries
$$ {:nonum:}
(Z_C)_{ee}\coloneqq s(\inp(e)),
$$
for each oriented edge $e$ of $C$.
If $(\mathcal{T}_C)_{ee'}\neq 0$, then a non-backtracking random walk can go from $e$ to $e'$, implying that $\inp(e')=\out(e)$, and therefore $s(\inp(e'))=-s(\inp(e))$. Therefore, since $Z_C$ is diagonal, for all oriented edges $e,e'$ of $C$ we have that
$$ {:nonum:}
\begin{aligned}
(Z_C\mathcal{T}_CZ_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(\inp(e))\,(\mathcal{T}_C)_{ee'}\,s(\inp(e'))\\
&=-(\mathcal{T}_C)_{ee'},
\end{aligned}
$$
where the last equality follows from the previous observation if $(\mathcal{T}_C)_{ee'}\neq 0$, and is trivial if $(\mathcal{T}_C)_{ee'}=0$. Hence, $$ {:nonum:}
Z_C\mathcal{T}_CZ_C=-\mathcal{T}_C.
$$
Since $Z_C^2=\id$, it follows that $\mathcal{T}_C$ and $-\mathcal{T}_C$ are similar, and therefore the eigenvalues of $\mathcal{T}_C$, with multiplicity, are invariant under $t\mapsto -t$. In particular, since $1$ is an eigenvalue of $\mathcal{T}_C$ by (ii), so is $-1$.
Now assume, by contradiction, that $\mathcal{T}_C$ has exactly two non-real eigenvalues, $t$ and $\overline{t}$. By the above invariance, $-t$ is also a non-real eigenvalue of $\mathcal{T}_C$, therefore $-t\in\{t,\overline{t}\}$. Since $t\neq 0$ by (i), we have that $-t\neq t$, and therefore $-t=\overline{t}$. This means that $t$ is purely imaginary, that is, $t=i\gamma$ for some $\gamma\in\mathbb{R}$ with $\gamma\neq 0$. Moreover, $|\gamma|=|t|\leq 1$ by (ii).
We now separate, in :ref:eq-trace::, one copy of the eigenvalue $1$, one copy of the eigenvalue $-1$, and the two eigenvalues $i\gamma$ and $-i\gamma$. Denoting by $I$ the set of indices of the remaining eigenvalues, which are all real, we obtain
$$ {:nonum:}
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 $|\gamma|\leq 1$, we have that $2-2\gamma^2\geq 0$, and by (i), $t_k^2>0$ for every $k\in I$. Hence, both $2-2\gamma^2$ and the sum over $I$ must vanish, that is, $\gamma^2=1$ and $I=\emptyset$. Therefore, the only eigenvalues of $\mathcal{T}_C$ are $1$, $-1$, $i$ and $-i$, each with multiplicity one. Since $\mathcal{T}_C$ is a $2M_C\times 2M_C$ matrix, this implies that $M_C=2$. However, since every vertex of $C$ has degree at least $2$, we have $$ {:nonum:}
2M_C=\sum_{v\in V(C)}\deg v\geq 2|V(C)|,
$$ implying that $M_C\geq|V(C)|\geq 3$. This is a contradiction, and therefore $\mathcal{T}_C$ has at least four non-real eigenvalues.
Finally, for the cycle $C_4$, we have that $M=N=4$ and $c=b=1$, therefore
$$ {:nonum:}
2M-2N+2c+2b=4=2M-2c-2b.
$$
Together with :ref:thm-refined::, this shows that $\mathcal{L}$ has exactly $4$ real eigenvalues, and that the bound is attained.
::
## Declaration of AI assistance {
:nonum:
}
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 {
:nonum:
}
Raffaella Mulas is supported by the Dutch Research Council (NWO) through the grant VI.Veni.232.002 (Grant ID: :url:https://doi.org/10.61686/NLUFV33835::).
:references:
@article{Kempton2016,
author={Kempton, M.},
title={Non-Backtracking Random Walks and a Weighted Ihara’s Theorem},
journal={Open Journal of Discrete Mathematics},
publisher={Scientific Research Publishing},
volume={6},
number={4},
pages={207–226},
year={2016},
}
@book{gohberg2006indefinite,
author={Gohberg, I. and Lancaster, P. and Rodman, L.},
title={Indefinite linear algebra and applications},
publisher={Springer Science & Business Media},
year={2006},
}
@book{chung,
author={Chung, F.},
title={Spectral graph theory},
publisher={American Mathematical Soc.},
year={1997},
}
@book{brouwer,
author={Brouwer, A.E. and Haemers, W.H.},
title={Spectra of graphs},
publisher={Springer Science & Business Media},
year={2011},
}
@article{torres2021nonbacktracking,
author={Torres, L. and Chan, K.S. and Tong, H. and Eliassi-Rad, T.},
title={Nonbacktracking eigenvalues under node removal: X-centrality and targeted immunization},
journal={SIAM Journal on Mathematics of Data Science},
publisher={SIAM},
volume={3},
number={2},
pages={656–675},
year={2021},
}
@article{bordenave2018nonbacktracking,
author={Bordenave, C. and Lelarge, M. and Massoulié, L.},
title={Nonbacktracking spectrum of random graphs: Community detection and nonregular Ramanujan graphs},
journal={Annals of probability: An official journal of the Institute of Mathematical Statistics},
publisher={Institute of Mathematical Statistics},
volume={46},
number={1},
pages={1–71},
year={2018},
}
@book{terras2010zeta,
author={Terras, A.},
title={Zeta functions of graphs: A stroll through the garden},
publisher={Cambridge University Press},
series={Cambridge studies in advanced mathematics},
volume={128},
year={2010},
}
@incollection{hashimoto1989zeta,
author={Hashimoto, K.},
title={Zeta functions of finite graphs and representations of p-adic groups},
booktitle={Automorphic Forms and Geometry of Arithmetic Varieties},
publisher={Elsevier},
series={Advanced Studies in Pure Mathematics},
volume={15},
pages={211–280},
year={1989},
}
@article{bass1992ihara,
author={Bass, H.},
title={The Ihara-Selberg zeta function of a tree lattice},
journal={International Journal of Mathematics},
publisher={World Scientific},
volume={3},
number={06},
pages={717–797},
year={1992},
}
@article{krzakala2013spectral,
author={Krzakala, F. and Moore, C. and Mossel, E. and Neeman, J. and Sly, A. and Zdeborová, L. and Zhang, P.},
title={Spectral redemption in clustering sparse networks},
journal={Proceedings of the National Academy of Sciences},
publisher={National Acad Sciences},
volume={110},
number={52},
pages={20935–20940},
year={2013},
}
@article{martin2014localization,
author={Martin, T. and Zhang, X. and Newman, M.E.J.},
title={Localization and centrality in networks},
journal={Physical Review E},
publisher={APS},
volume={90},
number={5},
pages={052808},
year={2014},
}
@article{shrestha2015message,
author={Shrestha, M. and Scarpino, S.V. and Moore, C.},
title={Message-passing approach for recurrent-state epidemic models on networks},
journal={Physical Review E},
publisher={APS},
volume={92},
number={2},
pages={022821},
year={2015},
}
@article{castellano2018relevance,
author={Castellano, C. and Pastor-Satorras, R.},
title={Relevance of backtracking paths in recurrent-state epidemic spreading on networks},
journal={Physical Review E},
publisher={APS},
volume={98},
number={5},
pages={052313},
year={2018},
}
@misc{Mulas2025LectureNotes,
author={Mulas, R.},
title={Spectral Theory of Graphs and Hypergraphs},
year={2025},
howpublished={Lecture notes for the BeyondTheEdge MSCA Doctoral Network, Marseille, France},
note={Available at https://cdn.prod.website-files.com/673b1c6a31679f06b3cef571/68d3daeb1b89a52be5dee00e_Marseille-LectureNotes-RM.pdf (Accessed October 2026)},
}
@article{JMT2023,
author={Jost, J. and Mulas, R. and Torres, L.},
title={Spectral theory of the non-backtracking Laplacian for graphs},
journal={Discrete Mathematics},
volume={346},
number={10},
pages={113536},
year={2023},
}
@book{BookJMZ,
author={Jost, J. and Mulas, R. and Zhang, D.},
title={Spectra of Discrete Structures},
publisher={Cambridge University Press},
series={Cambridge Studies in Advanced Mathematics},
number={221},
year={2026},
}
@article{backhausz2015ramanujan,
author={Backhausz, Á. and Szegedy, B. and Virág, B.},
title={Ramanujan graphings and correlation decay in local algorithms},
journal={Random Structures & Algorithms},
publisher={Wiley Online Library},
volume={47},
number={3},
pages={424–435},
year={2015},
}
@article{cooper2009,
author={Cooper, Y.},
title={Properties determined by the Ihara zeta function of a graph},
journal={The Electronic Journal of Combinatorics},
volume={16},
number={1},
pages={R84},
year={2009},
}
@article{torres2019non,
author={Torres, L. and Suárez-Serrato, P. and Eliassi-Rad, T.},
title={Non-backtracking cycles: length spectrum theory and graph mining applications},
journal={Applied Network Science},
publisher={Springer},
volume={4},
number={1},
pages={1–35},
year={2019},
}
@article{coste2021eigenvalues,
author={Coste, S. and Zhu, Y.},
title={Eigenvalues of the non-backtracking operator detached from the bulk},
journal={Random Matrices: Theory and Applications},
publisher={World Scientific},
volume={10},
number={03},
pages={2150028},
year={2021},
}
@article{glover2021some,
author={Glover, C. and Kempton, M.},
title={Some spectral properties of the non-backtracking matrix of a graph},
journal={Linear Algebra and its Applications},
publisher={Elsevier},
volume={618},
pages={37–57},
year={2021},
}
@article{pastor2020localization,
author={Pastor-Satorras, R. and Castellano, C.},
title={The localization of non-backtracking centrality in networks and its physical consequences},
journal={Scientific reports},
publisher={Nature Publishing Group},
volume={10},
number={1},
pages={1–12},
year={2020},
}
@article{Arrigo1,
author={Arrigo, F. and Higham, D.J. and Noferini, V.},
title={Beyond non-backtracking: non-cycling network centrality measures},
journal={Proceedings. Mathematical, Physical, and Engineering Sciences},
volume={476},
year={2020},
}
@article{Arrigo2,
author={Arrigo, F. and Higham, D.J. and Noferini, V. and Wood, R.},
title={Weighted enumeration of nonbacktracking walks on weighted graphs},
journal={SIAM Journal on Matrix Analysis and Applications},
publisher={SIAM},
volume={45},
number={1},
pages={397–418},
year={2024},
}
@article{Gronford1,
author={Grindrod, P. and Higham, D.J. and Noferini, V.},
title={The Deformed Graph Laplacian and Its Applications to Network Centrality Analysis},
journal={SIAM Journal on Matrix Analysis and Applications},
volume={39},
number={1},
pages={310-341},
year={2018},
doi={10.1137/17M1112297},
url={https://doi.org/10.1137/17M1112297},
}
@article{Mellor1,
author={Mellor, A. and Grusovin, A.},
title={Graph comparison via the nonbacktracking spectrum},
journal={Phys. Rev. E},
publisher={American Physical Society},
volume={99},
pages={052309},
year={2019},
month={may},
doi={10.1103/PhysRevE.99.052309},
url={https://link.aps.org/doi/10.1103/PhysRevE.99.052309},
}
@article{bolla2025non,
author={Bolla, M.},
title={The non-backtracking random walk and its usage for vertex clustering},
journal={arXiv preprint arXiv:2512.24434},
year={2025},
}
@inproceedings{bolla2025clustering,
author={Bolla, M. and Reittu, H. and Abdelkhalek, F.},
title={Clustering the nodes of sparse edge-weighted graphs via non-backtracking spectra},
booktitle={Future of Information and Communication Conference},
pages={81–99},
year={2025},
organization={Springer},
}
@article{MZZ,
author={Mulas, R. and Zhang, D. and Zucal, G.},
title={There is no going back: Properties of the non-backtracking Laplacian},
journal={Linear Algebra Appl.},
volume={680},
pages={341–370},
year={2024},
}
@article{maximal-colouring,
author={Mulas, R.},
title={Maximal colourings for graphs},
journal={Graphs and Combinatorics},
volume={40},
number={93},
year={2024},
doi={10.1007/s00373-024-02823-3},
}
@article{lubotzky1988ramanujan,
author={Lubotzky, A. and Phillips, R. and Sarnak, P.},
title={Ramanujan graphs},
journal={Combinatorica},
publisher={Springer-Verlag Berlin/Heidelberg},
volume={8},
number={3},
pages={261–277},
year={1988},
}
@article{murty2003ramanujan,
author={Murty, M.R.},
title={Ramanujan graphs},
journal={Journal of the Ramanujan Mathematical Society},
publisher={THE RAMANUJAN MATHEMATICAL SOCIETY},
volume={18},
number={1},
pages={33–52},
year={2003},
}
::
Let \(G\) be a simple graph on \(N\) nodes and \(M\) edges, with minimum degree at least \(2\). We prove that the non-backtracking Laplacian of \(G\) has at least \(2M-2N+2c+2b\) real eigenvalues, counted with algebraic multiplicity, where \(c\) is the number of connected components of \(G\) and \(b\) is the number of bipartite ones. More precisely, at least \(M-N+2c\) of them lie in \([0,1)\) and at least \(M-N+2b\) lie in \((1,2]\). We show that the bound \(2M-2N+2c+2b\) is sharp, and that a connected \(d\)-regular graph attains it if and only if it is strictly Ramanujan, i.e., every adjacency eigenvalue \(\mu\ne\pm d\) satisfies \(|\mu|<2\sqrt{d-1}\). For completeness, we also show that the non-backtracking Laplacian has at most \(2M-2c-2b\) real eigenvalues.
While most of the spectral theory of simple graphs concerns symmetric matrices, such as the adjacency matrix and the graph Laplacians (we refer to [3,4, 16] 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 [8], in the context of zeta functions of graphs, and they have since proved useful in many areas, including algebraic graph theory [7,9, 18], the study of Ramanujan graphings [17], epidemic spreading [12,13], community detection [10,6, 28], and centrality measures [11,5]. We refer to [19,20, 21, 22, 23, 24, 25, 26, 27] 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)\) be a simple graph on \(N\) nodes and \(M\) edges, with minimum degree at least \(2\). Each edge of \(G\) admits two orientations, and we write \([v,w]\) for the oriented edge with input\(\inp([v,w])\coloneqq v\) and output\(\out([v,w])\coloneqq w\). Its inverse is \([v,w]^{-1}\coloneqq[w,v]\). This gives \(2M\) oriented edges, which we label as \(e_1,\ldots,e_{2M}\) in such a way that
A non-backtracking random walk on \(G\) is a discrete-time Markov process on the oriented edges such that the probability of going from \(e_i\) to \(e_j\) is
In particular, the assumption that \(G\) has minimum degree at least \(2\) guarantees that the denominator is always positive. Moreover, one can also see a non-backtracking random walk as a process on \(V\), but in this case the probability that the walker moves from a vertex \(v\) to one of its neighbors depends on the vertex she came from. Hence, this process is not Markovian on \(V\).
Non-backtracking random walks are encoded by the non-backtracking graph or Hashimoto graph of \(G\), denoted \(\mathcal{G}\), which is the directed graph whose vertices are the \(2M\) oriented edges of \(G\), and which has a directed edge from \(e_i\) to \(e_j\) if and only if
$$
\out(e_i)=\inp(e_j) \text{ and } e_j\neq e_i^{-1},
$$
i.e., if and only if a non-backtracking random walk can go from \(e_i\) to \(e_j\) in one step. The adjacency matrix of \(\mathcal{G}\) is the \(2M\times 2M\) matrix \(\mathcal{A}\) with \((0,1)\)–entries such that
$$
\mathcal{A}_{ij}=1\iff \out(e_i)=\inp(e_j) \text{ and } e_j\neq e_i^{-1},
$$
and its transpose \(\mathcal{A}^\top\) is the non-backtracking matrix of \(G\) introduced by Hashimoto [8]. Moreover, a random walk on \(\mathcal{G}\) is precisely a non-backtracking random walk on \(G\). Since each vertex \(e_i\) of \(\mathcal{G}\) has (out-)degree
where \(\id\) denotes the identity matrix, \(\mathcal{D}\) is the degree matrix of \(\mathcal{G}\) and has diagonal entries
$$
\mathcal{D}_{ii}:=\deg_{\mathcal{G}}(e_i),
$$
and \(\mathcal{T}\coloneqq\mathcal{D}^{-1}\mathcal{A}\) is the transition probability matrix of the non-backtracking random walk on \(G\).
We introduced the non-backtracking Laplacian in [15], together with J. Jost. Its spectral properties were further investigated in [29], its connection to graph colorings was studied in [30], and it has been applied to vertex clustering in [28]. The computations in Table 2 of [15] 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 \(\mathcal{L}\) spectrum. Moreover, in the same paper we showed that the presence of certain cycle configurations produces real eigenvalues of \(\mathcal L\).
For the non-backtracking matrix, the Ihara–Bass formula [9,7, 1],
where \(A\) and \(D\) are the adjacency and degree matrices of \(G\), gives at least \(2M-2N\) real eigenvalues for each of \(\mathcal A\) and \(\mathcal A^\top\), counted with algebraic multiplicity. If \(G\) is \(d\)–regular, then
$$
\mathcal L=\mathrm{Id}-\frac{1}{d-1}\mathcal A.
$$
Therefore, in this case, \(\mathcal L\) also has at least \(2M-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 \(\mathcal L\). It is therefore natural to ask whether the lower bound \(2M-2N\) nevertheless holds for the non-backtracking Laplacian. Motivated by numerical experiments, we conjectured in 2022 that \(\mathcal L\) always has at least \(2M-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 Exercise 13 of [14].
Here we prove this conjecture, and we refine it as follows.
Theorem: Theorem 4.1 and Corollary 5.2
Let \(G\) be a simple graph on \(N\) nodes and \(M\) edges, with minimum degree at least \(2\). Let \(c\) be the number of connected components of \(G\), and let \(b\) be the number of bipartite ones. Then, the number of real eigenvalues of the non-backtracking Laplacian of \(G\), counted with algebraic multiplicity, is at least
$$
2M-2N+2c+2b.
$$
Moreover, this bound is sharp.
Click empty space to add a node. Click two nodes to add or remove the edge between them. Drag a node to move it.
Widget 1.1. The eigenvalues of \(\mathcal{L}\) for the graph on the left, which can be edited, counted with algebraic multiplicity and compared with the bounds of Theorem 4.1,Theorem 6.2 and Theorem 7.1. No eigenvalue lies in the shaded disk \(|1-\lambda|<1/(\Delta-1)\). The bar below the plot shows all \(2M\) eigenvalues, real ones first, with the lower and upper bounds marked.
For connected regular graphs, we also determine exactly when the above bound is attained. Recall that a connected \(d\)–regular graph is Ramanujan[31,32] if every adjacency eigenvalue \(\mu\neq\pm d\) satisfies
$$
|\mu|\leq 2\sqrt{d-1}.
$$
We call it strictly Ramanujan if every adjacency eigenvalue \(\mu\neq\pm d\) satisfies
$$
|\mu|<2\sqrt{d-1}.
$$
We show that, for a connected regular graph \(G\), the non-backtracking Laplacian has exactly \(2M-2N+2+2b\) real eigenvalues if and only if \(G\) 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 \(\class{nbl lk lk-ex-low}{M-N+2c}\) of them lie in \(\class{nbl lk lk-ex-low}{[0,1)}\) and at least \(\class{nbh lk lk-ex-high}{M-N+2b}\) lie in \(\class{nbh lk lk-ex-high}{(1,2]}\).
For completeness, we also prove in Theorem 7.1 that \(\mathcal L\) has at most \(2M\class{nbc lk lk-ex-cplx}{-2c-2b}\) real eigenvalues, counted with algebraic multiplicity, and that this bound is attained by the cycle \(C_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.
2. Notation and preliminaries
Throughout the paper, we fix a simple graph \(G=(V,E)\) on \(N\) nodes and \(M\) edges, with minimum degree at least \(2\), and we use the same notation as in the introduction. In particular, \(\mathcal{G}=(\mathcal{V},\mathcal{E})\) denotes the non-backtracking graph of \(G\), whose vertices are the \(2M\) oriented edges \(e_1,\ldots,e_{2M}\) of \(G\), labeled so that
Moreover, \(\mathcal{A}\) and \(\mathcal{D}\) denote the adjacency and degree matrices of \(\mathcal{G}\), while \(\mathcal{L}=\id-\mathcal{D}^{-1}\mathcal{A}\) and \(\mathcal{T}=\mathcal{D}^{-1}\mathcal{A}\) denote the non-backtracking Laplacian and the transition matrix of the non-backtracking random walk on \(G\).
We identify each vector \(f\in\mathbb{C}^{2M}\) with the function
where \(\langle\cdot,\cdot\rangle\) is the standard inner product on \(\mathbb{C}^r\). A matrix \(R\in\mathbb{R}^{r\times r}\) is said to be self-adjoint with respect to the \(K\)-product, or \(K\)-self-adjoint, if
$$
(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
$$
R^\top K=KR.
$$
As in [15], we let \(P\) be the \(2M\times 2M\) matrix
In particular, \(H\) is real and symmetric. Moreover, \(\mathcal{L}\) is \(H\)-self-adjoint. In fact, by (2.2) and since \(\mathcal{L}\) commutes with \(\id-\mathcal{L}\),
The matrix \(H\) plays a central role in the proofs of our main results, for the following reason. By Lemma 2.2 below, if a real matrix \(R\) is self-adjoint with respect to the \(K\)-product of a real symmetric invertible matrix \(K\), then \(R\) has at most \(2\min\bigl(n_+(K),n_-(K)\bigr)\) non-real eigenvalues, where \(n_+(K)\) and \(n_-(K)\) denote the numbers of positive and negative eigenvalues of \(K\), counted with multiplicity. By (2.2),\(\mathcal{L}\) is \(P\)-self-adjoint. However, \(P\) has eigenvalues \(1\) and \(-1\), each with multiplicity \(M\), so in this case the lemma only says that \(\mathcal{L}\) has at most \(2M\) non-real eigenvalues, which is trivial since \(\mathcal{L}\) is a \(2M\times 2M\) matrix. The advantage of considering \(H\) is that \(\mathcal{L}\) is also \(H\)-self-adjoint, by (2.3), and \(H\) has only \(N\) positive eigenvalues and \(2M-N\) negative ones, by Lemma 2.1 below. Since every vertex of \(G\) has degree at least \(2\), we have that
Hence, by Lemma 2.2,\(\mathcal{L}\) has at most \(2N\) non-real eigenvalues, that is, at least \(2M-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 \(G\) to reduce the number of positive eigenvalues of \(H\) that need to be taken into account.
We first prove the claim on the eigenvalues of \(H\).
Lemma 2.1.
The matrix \(H\) is invertible. Moreover,
$$
n_+(H)=N\qquad\text{and}\qquad n_-(H)=2M-N.
$$
Proof.
By definition of \(H\), we have that \(H_{ij}=0\) whenever \(\inp(e_i)\neq\inp(e_j)\). Hence, if we order the oriented edges according to their input, \(H\) is block diagonal, with one block \(H_v\) of size \(\deg v\times\deg v\) for each \(v\in V\). Moreover,
where \(J_{\deg v}\) denotes the \(\deg v\times\deg v\) matrix whose entries are all equal to \(1\). Since \(J_{\deg v}\) has eigenvalue \(\deg v\) with multiplicity \(1\), and eigenvalue \(0\) with multiplicity \(\deg v-1\), the block \(H_v\) has eigenvalue \(1\) with multiplicity \(1\), and eigenvalue \(-1/(\deg v-1)\) with multiplicity \(\deg v-1\). The eigenvalues of \(H\), with multiplicity, are those of the blocks \(H_v\). Since none of them is zero, \(H\) is invertible, and
We now state the linear algebra fact used in the proofs of our main results. Given a real square matrix \(R\), we let \(n_{\mathbb{R}}(R)\) denote the number of real eigenvalues of \(R\), counted with algebraic multiplicity.
Lemma 2.2.
Let \(K\in\mathbb{R}^{r\times r}\) be symmetric and invertible, and let \(R\in\mathbb{R}^{r\times r}\) be \(K\)-self-adjoint. Then, \(R\) has at most \(2\min\bigl(n_+(K),n_-(K)\bigr)\) non-real eigenvalues, counted with algebraic multiplicity. Equivalently,
Since \(R\) is \(K\)-self-adjoint, it follows from page 77 of [2] (see the inequality following equation (5.2.4) and the comment after it, where \(A=R\),\(H=K\) and \(i_-(H)=n_-(K)\) in our notation) that \(n_-(K)\) is at least half the number of non-real eigenvalues of \(R\), counted with algebraic multiplicity. Since \(R\) is also \((-K)\)-self-adjoint, and since \(n_-(-K)=n_+(K)\), the same holds for \(n_+(K)\). Therefore, the number of non-real eigenvalues of \(R\) is at most \(2\min\bigl(n_+(K),n_-(K)\bigr)\).
3. The bound 2M − 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-2N\) real eigenvalues. As anticipated in Section 2, this follows by combining the \(H\)-self-adjointness of \(\mathcal{L}\) with Lemma 2.1 and Lemma 2.2.
Theorem 3.1.
Let \(G\) be a simple graph on \(N\) nodes and \(M\) edges, with minimum degree at least \(2\). Then, the number of real eigenvalues of the non-backtracking Laplacian of \(G\), counted with algebraic multiplicity, is at least
$$
2M-2N.
$$
Proof.
By (2.3),\(\mathcal{L}\) is \(H\)-self-adjoint, and by Lemma 2.1,\(H\) is a real symmetric invertible matrix with \(n_+(H)=N\) and \(n_-(H)=2M-N\). As observed in (2.4), the minimum degree assumption implies that
$$
\min\bigl(n_+(H),n_-(H)\bigr)=N.
$$
Applying Lemma 2.2 with \(R=\mathcal{L}\) and \(K=H\) yields
$$
n_{\mathbb{R}}(\mathcal{L})\geq 2M-2N.
$$
4. The refined bound
In this section, we refine Theorem 3.1 by taking into account the connected and bipartite components of \(G\). These give explicit eigenvectors of \(\mathcal{L}\) with real eigenvalues, which allow us to reduce the number of positive eigenvalues of \(H\) that need to be taken into account in Lemma 2.2.
Theorem 4.1.
Let \(G\) be a simple graph on \(N\) nodes and \(M\) edges, with minimum degree at least \(2\). Let \(c\) be the number of connected components of \(G\), and let \(b\) be the number of bipartite ones. Then, the number of real eigenvalues of the non-backtracking Laplacian of \(G\), counted with algebraic multiplicity, is at least
$$
2M-2N+2c+2b.
$$
Proof.
For each connected component \(C\) of \(G\), let \(V(C)\) be the vertex set of \(C\), let \(E(C)\) be its edge set, and let \(\mathbbm{1}_C\colon\mathcal{V}\to\{0,1\}\) be the indicator function of the oriented edges of \(C\). If \(C\) is bipartite, fix a function \(s_C\colon V(C)\to\{1,-1\}\) that takes opposite values on adjacent vertices, and let
$$
\begin{aligned}
\sigma_C\colon\mathcal{V}&\to\{0,1,-1\}\\
[v,w]&\mapsto\begin{cases}
s_C(v), & \text{if } [v,w] \text{ is an oriented edge of } C,\\
0, & \text{otherwise.}
\end{cases}
\end{aligned}
$$
By (2.1) we have that, for every \([v,w]\in\mathcal{V}\),
$$
\begin{aligned}
(\mathcal{T}\mathbbm{1}_C)([v,w])&=\frac{1}{\deg w-1}\sum_{z\sim w,\,z\neq v}\mathbbm{1}_C([w,z])\\
&=\begin{cases}
1 & \text{if } [v,w] \text{ is an oriented edge of } C,\\
0 & \text{otherwise.}
\end{cases}
\end{aligned}
$$
Hence, \(\mathcal{T}\mathbbm{1}_C=\mathbbm{1}_C\). Similarly, for every \([v,w]\in\mathcal{V}\), by definition of \(P\), and since \([v,w]\) and \([w,v]\) belong to the same connected component,
Hence, \(P\mathbbm{1}_C=\mathbbm{1}_C\). Moreover, if \(C\) is bipartite and \([v,w]\) is in \(C\), then \(s_C(w)=-s_C(v)\). Since each oriented edge \([w,z]\) with \(z\sim w\) also belongs to \(C\), this implies that, by (2.1),
Now, let \(W\subseteq\mathbb{C}^{2M}\) be the span of the functions \(\mathbbm{1}_C\), for all connected components \(C\), and \(\sigma_C\), for all bipartite components \(C\). These \(c+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 \(C\),
Therefore, \(\dim W=c+b\). Moreover, \(H\mathbf{w}=\mathbf{w}\) for every \(\mathbf{w}\in W\), and since \(W\) is spanned by eigenvectors of \(\mathcal{L}\), it is \(\mathcal{L}\)-invariant, that is, \(\mathcal{L}\mathbf{w}\in W\) for every \(\mathbf{w}\in W\).
Now, for all \(\mathbf{w}\in W\) and \(\mathbf{x}\in\mathbb{C}^{2M}\), we have that
where the second equality holds because \(H\) is symmetric, the third because \(H\) is real, and the fourth because \(H\mathbf{w}=\mathbf{w}\).
Therefore, if we let \(W^\perp\) be the orthogonal complement of \(W\) with respect to the standard inner product, then \(W^\perp\) is also \(\mathcal{L}\)-invariant. In fact, let \(\mathbf{x}\in W^\perp\) and \(\mathbf{w}\in W\). Then, since \(\mathcal{L}\mathbf{w}\in W\), we have that
where the first and third equalities follow from the above identity, the second one holds because \(\mathcal{L}\) is \(H\)-self-adjoint, and the last one because \(\mathbf{x}\in W^\perp\). Hence, \(\mathcal{L}\mathbf{x}\in W^\perp\).
Now, let \(Q\) be a real orthogonal matrix whose first \(c\) columns are the vectors \(\mathbbm{1}_C/\|\mathbbm{1}_C\|\), whose next \(b\) columns are the vectors \(\sigma_C/\|\sigma_C\|\), and whose remaining \(2M-c-b\) columns form an orthonormal basis of \(W^\perp\), which can be chosen real since \(W\) is spanned by real vectors. In other words, \(Q\) is the change of basis to an orthonormal basis adapted to the decomposition \(\mathbb{C}^{2M}=W\oplus W^\perp\). Since both summands are \(\mathcal{L}\)-invariant, \(Q^\top\mathcal{L}Q\) is block diagonal, and since the first \(c+b\) columns of \(Q\) are eigenvectors of \(\mathcal{L}\), with eigenvalue \(0\) for the first \(c\) ones and \(2\) for the next \(b\) ones,
where \(\mathcal{L}_W\) is the diagonal matrix with \(c\) diagonal entries equal to \(0\) and \(b\) diagonal entries equal to \(2\), and \(\mathcal{L}_0\) is a real matrix of size \((2M-c-b)\times(2M-c-b)\).
Similarly, let \(\mathbf{q}_j\) denote the \(j\)-th column of \(Q\). Then \((Q^\top HQ)_{ij}=(\mathbf{q}_i,\mathbf{q}_j)_H\), and by the identity above, \((\mathbf{q}_i,\mathbf{q}_j)_H=\langle\mathbf{q}_i,\mathbf{q}_j\rangle\), which is \(1\) if \(i=j\) and \(0\) otherwise, whenever \(\mathbf{q}_i\in W\) or \(\mathbf{q}_j\in W\). Hence
and comparing the lower right blocks gives \(\mathcal{L}_0^\top H_0=H_0\mathcal{L}_0\). That is, \(\mathcal{L}_0\) is \(H_0\)-self-adjoint. By (2.4), we have that
$$
N-c-b\leq N\leq 2M-N,
$$
and therefore Lemma 2.2 implies that \(\mathcal{L}_0\) has at most \(2(N-c-b)\) non-real eigenvalues, counted with algebraic multiplicity.
Finally, since \(Q^\top\mathcal{L}Q\) is block diagonal,
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 \(G\) be a connected \(d\)-regular graph with \(d\geq 2\), and let \(\kappa\) be the number of adjacency eigenvalues \(\mu\neq\pm d\) of \(G\) with \(|\mu|\geq 2\sqrt{d-1}\), counted with multiplicity. Then,
In particular, equality in Theorem 4.1 holds if and only if \(G\) is strictly Ramanujan, that is, every adjacency eigenvalue \(\mu\ne\pm d\) satisfies \(|\mu|<2\sqrt{d-1}\).
Proof.
Let \(G\) be a connected \(d\)-regular graph on \(N\) nodes and \(M\) edges, with \(d\geq 2\). Since \(G\) is connected, we have that \(c=1\), and therefore the quantity in Theorem 4.1 is
$$
2M-2N+2+2b,
$$
where \(b=1\) if \(G\) is bipartite, and \(b=0\) otherwise.
Now, let \(\mu_1,\ldots,\mu_N\) be the eigenvalues of the adjacency matrix \(A\) of \(G\), listed with multiplicity, and given \(\mu\in\mathbb{R}\), let
Note that the exponent \(M-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)\) real roots, namely \(1/(d-1)\) and \(-1/(d-1)\), each with multiplicity \(M-N\).
Since \(G\) is connected and \(d\)-regular, \(d\) is a simple eigenvalue of \(A\). Moreover, \(-d\) is an eigenvalue of \(A\) if and only if \(G\) is bipartite, in which case it is also simple. The corresponding quadratic factors are
In particular, \(\mathcal{L}\) has exactly \(2M-2N+2+2b\) real eigenvalues if and only if \(\kappa=0\), that is, if and only if \(G\) is strictly Ramanujan.
Widget 5.1. The eigenvalues \(t\) of \(\mathcal{T}\) for a connected \(d\)-regular graph, as in the proof of Theorem 5.1. Each adjacency eigenvalue \(\mu\) of \(G\) contributes the two roots of \(q_\mu\), which are real if \(|\mu|\geq 2\sqrt{d-1}\) and lie on the dashed circle \(|t|=1/\sqrt{d-1}\) otherwise, and the first factor contributes \(\pm 1/(d-1)\), each \(M-N\) times. The slider moves one value of \(\mu\), whose two roots are circled.
Corollary 5.2.
The bound in Theorem 4.1 is attained by the following graphs:
the cycle graph \(C_N\), for every \(N\geq 3\);
the complete graph \(K_N\), for every \(N\geq 3\);
the complete bipartite graph \(K_{r,r}\), for every \(r\geq 2\).
Since all these graphs are connected and regular, by Theorem 5.1 it suffices to show that they are strictly Ramanujan.
The cycle \(C_N\) is \(2\)-regular, and its adjacency eigenvalues are \(2\cos(2\pi j/N)\), for \(j=0,\ldots,N-1\). All of them except \(\pm 2\) satisfy \(|\mu|<2=2\sqrt{2-1}\).
The complete graph \(K_N\) is \((N-1)\)-regular, and its only adjacency eigenvalue other than \(N-1\) is \(-1\), which satisfies \(1<2\sqrt{N-2}\) for \(N\geq 3\).
The complete bipartite graph \(K_{r,r}\) is \(r\)-regular, and its only adjacency eigenvalue other than \(\pm r\) is \(0\), which satisfies \(0<2\sqrt{r-1}\) for \(r\geq 2\).
This proves the claim.
6. Splitting the real eigenvalues around 1
Theorem 4.1 counts the real eigenvalues of \(\mathcal{L}\). In this section, we show how many of them must lie on each side of \(1\). Equivalently, we count the positive and the negative real eigenvalues of \(\mathcal{T}=\id-\mathcal{L}\).
Recall from Theorem 4.1 of [15] that every eigenvalue \(\lambda\) of \(\mathcal{L}\) satisfies
$$
|1-\lambda|\geq \frac{1}{\Delta-1},
$$
where \(\Delta\) is the largest degree of \(G\). Hence, the real eigenvalues of \(\mathcal{L}\) in \([0,1)\) actually lie in \([0,1-1/(\Delta-1)]\), and those in \((1,2]\) lie in \([1+1/(\Delta-1),2]\).
For a real symmetric matrix \(K\), we define its signature as
For a real square matrix \(R\), we let \(n_>(R)\) and \(n_<(R)\) denote the numbers of positive and negative real eigenvalues of \(R\), 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\in\mathbb{R}^{r\times r}\) be symmetric and invertible, and let \(R\in\mathbb{R}^{r\times r}\) be invertible and \(K\)-self-adjoint. Then,
The matrix \(KR\) is real, symmetric and invertible, since
$$
(KR)^\top=R^\top K=KR.
$$
By the canonical form for \(K\)-self-adjoint matrices Theorem 5.1.1 of [2], there is an invertible matrix \(S\) such that \(S^{-1}RS\) and \(S^*KS\) are block diagonal with matching blocks, as follows. Each Jordan block \(J_m(\lambda)\) of a real eigenvalue \(\lambda\) is paired with \(\varepsilon P_m\), where \(P_m\) is the \(m\times m\) matrix with ones on the anti-diagonal and zeros elsewhere, and \(\varepsilon\in\{1,-1\}\). Each pair of Jordan blocks \(J_m(\lambda)\oplus J_m(\overline{\lambda})\) of a non-real eigenvalue \(\lambda\) is paired with \(P_{2m}\). Since
$$
S^*KRS=(S^*KS)(S^{-1}RS),
$$
the matrices \(S^*KS\) and \(S^*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 \(P_m\) has signature \(1\) if \(m\) is odd and \(0\) if \(m\) is even, and so does \(P_mJ_m(\lambda)\) multiplied by \(\operatorname{sgn}(\lambda)\), for real \(\lambda\neq0\). For a pair of non-real eigenvalues, both blocks have signature \(0\), since the span of the first \(m\) basis vectors of the block is isotropic for both forms and has half the dimension. Therefore
where both sums run over the Jordan blocks of odd size belonging to real eigenvalues \(\lambda\). Let \(p\) and \(q\) be the sums of \(\varepsilon\) over such blocks with \(\lambda>0\) and with \(\lambda<0\), respectively. Then, \(\operatorname{sig}(K)=p+q\) and \(\operatorname{sig}(KR)=p-q\). Finally, \(|p|\) is at most the number of blocks with \(\lambda>0\), which is at most \(n_>(R)\), and similarly \(|q|\leq n_<(R)\).
Let \(G\) be a simple graph on \(N\) nodes and \(M\) edges, with minimum degree at least \(2\). Let \(c\) be the number of connected components of \(G\), and let \(b\) be the number of bipartite ones. Then, \(\mathcal{T}\) has at least \(M-N+2c\) positive and at least \(M-N+2b\) negative real eigenvalues, counted with algebraic multiplicity. Equivalently, \(\mathcal{L}\) has at least \(M-N+2c\) real eigenvalues in \([0,1)\) and at least \(M-N+2b\) real eigenvalues in \((1,2]\).
Proof.
We use the notation of the proof of Theorem 4.1. Let \(\mathcal{T}_0\coloneqq \id-\mathcal{L}_0\), so that \(Q^\top\mathcal{T}Q\) is block diagonal with blocks \(\id-\mathcal{L}_W\) and \(\mathcal{T}_0\), and \(Q^\top HQ=Q^\top P\mathcal{T}Q\) has blocks \(\id\) and \(H_0\).
Since \(P\mathbbm{1}_C=\mathbbm{1}_C\) and \(P\sigma_C=-\sigma_C\), the matrix \(P\) maps \(W\) to itself, and since \(P\) is symmetric, it also maps \(W^\perp\) to itself. Hence \(Q^\top PQ\) is block diagonal, with a diagonal first block \(P_W\) having \(c\) entries equal to \(1\) and \(b\) entries equal to \(-1\), and a second block \(P_0\). Comparing the second blocks in
The matrix \(P\) has eigenvalues \(1\) and \(-1\), each with multiplicity \(M\). By Sylvester's law of inertia, \(n_+(P_0)=M-c\) and \(n_-(P_0)=M-b\), and from the proof of Theorem 4.1,\(n_+(H_0)=N-c-b\) and \(n_-(H_0)=2M-N\). Hence,
where we used \(M\geq N\). Finally, the first block \(\id-\mathcal{L}_W\) contributes the eigenvalue \(1\) with multiplicity \(c\) and the eigenvalue \(-1\) with multiplicity \(b\). The statement for \(\mathcal{L}\) follows from \(\mathcal{L}=\id-\mathcal{T}\) and the fact that all eigenvalues of \(\mathcal{T}\) have modulus at most \(1\), since \(\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
$$
\bigl(t^2-1/(d-1)^2\bigr)^{M-N}
$$
contributes \(M-N\) positive and \(M-N\) negative roots, the eigenvalue \(d\) of \(A\) contributes the positive roots \(1\) and \(1/(d-1)\), and the eigenvalue \(-d\), present exactly when \(G\) is bipartite, contributes the negative roots \(-1\) and \(-1/(d-1)\).
Remark 6.3.
The results of this section do not depend on the particular weights \(1/(\deg v-1)\), and they hold for any weighted matrix \(\mathcal{T}_f\coloneqq C_f\mathcal{A}\), where \(f\) is a positive function on the vertices and \(C_f\) is the diagonal matrix with diagonal entries \((C_f)_{ee}\coloneqq f(\out(e))\). In fact, as in Lemma 2.1,\(P\mathcal{T}_f\) is symmetric with \(N\) positive and \(2M-N\) negative eigenvalues, therefore Lemma 6.1 shows that \(\mathcal{T}_f\) has at least \(\class{nbl lk lk-wt-pos}{M-N}\) positive and at least \(\class{nbh lk lk-wt-neg}{M-N}\) negative real eigenvalues. The refinement by \(2c\) and \(2b\) can also be obtained, using the Perron–Frobenius Theorem in place of the explicit eigenvectors \(\mathbbm{1}_C\) and \(\sigma_C\). In particular, \(\mathcal{T}\) corresponds to \(f(v)=1/(\deg v-1)\), while \(f\equiv 1\) gives the transpose of the non-backtracking matrix. Note, however, that the location of the real eigenvalues of \(\id-\mathcal{T}\) in \([0,1)\) and \((1,2]\) uses the fact that \(\mathcal{T}\) is row-stochastic, and it does not extend to arbitrary weights.
Widget 6.1. The eigenvalues of \(\mathcal{T}_f=C_f\mathcal{A}\) as the weights move from \(f\equiv 1\) to \(f(v)=1/(\deg v-1)\), which gives \(\mathcal{T}\). At every step at least \(M-N\) eigenvalues are real and positive and at least \(M-N\) are real and negative. The dashed circle is \(|t|=1\).
7. An upper bound
We now complement Theorem 4.1 with an upper bound on the number of real eigenvalues of \(\mathcal{L}\).
Theorem 7.1.
Let \(G\) be a simple graph on \(N\) nodes and \(M\) edges, with minimum degree at least \(2\). Let \(c\) be the number of connected components of \(G\), and let \(b\) be the number of bipartite ones. Then, the number of real eigenvalues of the non-backtracking Laplacian of \(G\), counted with algebraic multiplicity, is at most
$$
2M-2c-2b.
$$
Moreover, this bound is attained by the cycle \(C_4\).
Proof.
Since \(\mathcal{L}=\id-\mathcal{T}\), it suffices to show that \(\mathcal{T}\) has at least \(2c+2b\) non-real eigenvalues, counted with algebraic multiplicity.
If we order the oriented edges of \(G\) according to the connected components of \(G\), then \(\mathcal{T}\) is block diagonal, with one block \(\mathcal{T}_C\) for each connected component \(C\), and \(\mathcal{T}_C\) is the transition matrix of the non-backtracking random walk on \(C\). Hence, it suffices to show that each \(\mathcal{T}_C\) has at least two non-real eigenvalues, and at least four if \(C\) is bipartite. To this end, we use the following three facts.
All eigenvalues of \(\mathcal{T}_C\) are non-zero. In fact, \(\mathcal{T}=PH\) is invertible, since \(P^2=\id\) and \(H\) is invertible by Lemma 2.1, and the eigenvalues of \(\mathcal{T}_C\) are eigenvalues of \(\mathcal{T}\).
Since \(\mathcal{T}_C\) is row-stochastic, all eigenvalues \(t\) of \(\mathcal{T}_C\) satisfy \(|t|\leq 1\). Moreover, for the same reason, \(1\) is an eigenvalue of \(\mathcal{T}_C\), with the constant functions as eigenfunctions.
We have that \(\operatorname{tr}(\mathcal{T}_C^2)=0\). In fact,
where \(e\) and \(e'\) range over the oriented edges of \(C\). If \((\mathcal{T}_C)_{ee'}(\mathcal{T}_C)_{e'e}\neq 0\), then both factors are non-zero, that is, a non-backtracking random walk can go from \(e\) to \(e'\) and from \(e'\) to \(e\). The first step requires \(e'\) to start at the output of \(e\), and the second one requires \(e'\) to end at the input of \(e\), therefore \(e'=e^{-1}\). But the step from \(e\) to \(e^{-1}\) is excluded by the definition of a non-backtracking random walk. Hence, all terms in the above sum vanish.
Now, let \(t_1,\ldots,t_m\) be the eigenvalues of \(\mathcal{T}_C\), listed with algebraic multiplicity. Then, by (iii),
By (i), every real eigenvalue \(t_k\) of \(\mathcal{T}_C\) satisfies \(t_k^2>0\). Hence, by (7.1),\(\mathcal{T}_C\) has at least one non-real eigenvalue. Since \(\mathcal{T}_C\) is real, its non-real eigenvalues appear in complex conjugate pairs, and therefore \(\mathcal{T}_C\) has at least two non-real eigenvalues.
Now, assume that \(C\) is bipartite. Let \(V(C)\) denote the vertex set of \(C\), and let \(M_C\) denote the number of edges of \(C\). We want to show that, in this case, \(\mathcal{T}_C\) cannot have exactly one pair of complex conjugate non-real eigenvalues. Since \(C\) is bipartite, there exists a function \(s\colon V(C)\to\{1,-1\}\) that takes opposite values on adjacent vertices. Hence, we can define the \(2M_C\times 2M_C\) diagonal matrix \(Z_C\) with diagonal entries
$$
(Z_C)_{ee}\coloneqq s(\inp(e)),
$$
for each oriented edge \(e\) of \(C\).
If \((\mathcal{T}_C)_{ee'}\neq 0\), then a non-backtracking random walk can go from \(e\) to \(e'\), implying that \(\inp(e')=\out(e)\), and therefore \(s(\inp(e'))=-s(\inp(e))\). Therefore, since \(Z_C\) is diagonal, for all oriented edges \(e,e'\) of \(C\) we have that
where the last equality follows from the previous observation if \((\mathcal{T}_C)_{ee'}\neq 0\), and is trivial if \((\mathcal{T}_C)_{ee'}=0\). Hence,
$$
Z_C\mathcal{T}_CZ_C=-\mathcal{T}_C.
$$
Since \(Z_C^2=\id\), it follows that \(\mathcal{T}_C\) and \(-\mathcal{T}_C\) are similar, and therefore the eigenvalues of \(\mathcal{T}_C\), with multiplicity, are invariant under \(t\mapsto -t\). In particular, since \(1\) is an eigenvalue of \(\mathcal{T}_C\) by (ii), so is \(-1\).
Now assume, by contradiction, that \(\mathcal{T}_C\) has exactly two non-real eigenvalues, \(t\) and \(\overline{t}\). By the above invariance, \(-t\) is also a non-real eigenvalue of \(\mathcal{T}_C\), therefore \(-t\in\{t,\overline{t}\}\). Since \(t\neq 0\) by (i), we have that \(-t\neq t\), and therefore \(-t=\overline{t}\). This means that \(t\) is purely imaginary, that is, \(t=i\gamma\) for some \(\gamma\in\mathbb{R}\) with \(\gamma\neq 0\). Moreover, \(|\gamma|=|t|\leq 1\) by (ii).
We now separate, in (7.1), one copy of the eigenvalue \(1\), one copy of the eigenvalue \(-1\), and the two eigenvalues \(i\gamma\) and \(-i\gamma\). Denoting by \(I\) the set of indices of the remaining eigenvalues, which are all real, we obtain
Since \(|\gamma|\leq 1\), we have that \(2-2\gamma^2\geq 0\), and by (i), \(t_k^2>0\) for every \(k\in I\). Hence, both \(2-2\gamma^2\) and the sum over \(I\) must vanish, that is, \(\gamma^2=1\) and \(I=\emptyset\). Therefore, the only eigenvalues of \(\mathcal{T}_C\) are \(1\),\(-1\),\(i\) and \(-i\), each with multiplicity one. Since \(\mathcal{T}_C\) is a \(2M_C\times 2M_C\) matrix, this implies that \(M_C=2\). However, since every vertex of \(C\) has degree at least \(2\), we have
$$
2M_C=\sum_{v\in V(C)}\deg v\geq 2|V(C)|,
$$
implying that \(M_C\geq|V(C)|\geq 3\). This is a contradiction, and therefore \(\mathcal{T}_C\) has at least four non-real eigenvalues.
Finally, for the cycle \(C_4\), we have that \(M=N=4\) and \(c=b=1\), therefore
$$
2M-2N+2c+2b=4=2M-2c-2b.
$$
Together with Theorem 4.1, this shows that \(\mathcal{L}\) has exactly \(4\) 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
Kempton, M. (2016)
Non-Backtracking Random Walks and a Weighted Ihara’s Theorem