# Spectral properties of the non-backtracking matrix of a graph

Cory Glover111Department of Mathematics, Brigham Young University, Provo UT,
USA<EMAIL_ADDRESS>and Mark Kempton222Department of Mathematics,
Brigham Young University, Provo UT, USA<EMAIL_ADDRESS>
###### Abstract

We investigate the spectrum of the non-backtracking matrix of a graph. In
particular, we show how to obtain eigenvectors of the non-backtracking matrix
in terms of eigenvectors of a smaller matrix. Furthermore, we find an
expression for the eigenvalues of the non-backtracking matrix in terms of
eigenvalues of the adjacency matrix, and use this to upper-bound the spectral
radius of the non-backtracking matrix, and to give a lower bound on the
spectrum. We also investigate properties of a graph that can be determined by
the spectrum. Specifically, we prove that the number of components, the number
of degree 1 vertices, and whether or not the graph is bipartite are all
determined by the spectrum of the non-backtracking matrix.

##  1 Introduction

Spectral techniques are ubiquitous in the study of random walks on graphs. For
instance, it is well known that the adjacency matrix of a graph can be used to
enumerate walks, and eigenvalues of the transition probability matrix can be
used to bound the mixing rate and mixing time of a simple random walk. In
recent years, the study of _non-backtracking_ random walks has gained
considerable interest. A non-backtracking random walk is a random walk on a
graph with the added requirement that each step cannot travel to the vertex
visited on the immediate previous step. Just as the adjacency matrix can be
used to enumerate simple walks, a matrix called the _non-backtracking matrix_
of a graph can be defined, which can be used to enumerate non-backtracking
walks in the graph (see Section 2 for details). The non-backtracking matrix
and its spectral properties have been the object of considerable study
recently. Bordenave et. al. [3] and. Newman [17] used them for community
detection on a graph. Centrality measures using non-backtracking random walks
have been discussed by Arrigo et al and Lin and Zhang [2, 12]. Pan, Jiang and
Xu have used them to maximize influence on social networks [19].

In this paper, we study the spectral properties of the non-backtracking matrix
of a graph. It is well-known that the spectrum of a non-backtracking matrix is
connected to the spectrum of the adjacency matrix using Ihara’s Theorem [1, 9,
15, 22] (see 2). Specifically, many have noted the relationship between the
non-backtracking spectrum and a (usually) smaller matrix we will denote $K$
(see Section 4) [11, 12, 22]. Bordenave et al also have studied non-
backtracking spectrum of Erdos-Renyi random graphs [3].

The spectrum of the non-backtracking matrix is well understood for regular
graphs, with explicit expressions for eigenvalues from Ihara’s Theorem, and
work of Lubetsky and Peres [15] gives explicit constructions of eigenvectors
for regular graphs. Our main goals are to: 1) develop deeper understanding
into the eigenvalues and eigenvectors of the non-backtracking matrix,
especially for irregular graphs, 2) identify bounds on the non-backtracking
spectrum of a graph, and 3) relate spectral properties of the non-backtracking
matrix to structural properties of the graph. Our first main result is to give
a new proof of Ihara’s Theorem. Our approach not only tells us the spectrum of
the non-backtracking matrix, but also gives a decomposition of the non-
backtracking matrix from which eigenvectors can be determined in terms of
eigenvectors of a smaller matrix. We furthermore use eigenvectors of the
matrix $K$ mentioned above to develop a formula that (under the right
conditions) gives the eigenvalues of the non-backtracking matrix in terms of
eigenvalues of the adjacency matrix for irregular graphs. Using this
expression, we bound the spectral radius of the non-backtracking matrix.
Finally, we prove that various structural properties of the graph, such as
number of components, number of degree 1 vertices, and bipartiteness are
completely determined by the non-backtracking spectrum.

The remainder of the paper is organized as follows. In Section 2, we will
define the non-backtracking matrix and review key facts known about its
spectrum. In Section 3, we will investigate the non-backtracking spectrum of
trees and cycles, as well as graphs with pendant cycles. In Section 4, we will
relate the non-backtracking matrix to a block diagonal matrix. This block
diagonal construction will give our alternate proof to Ihara’s Theorem.
Lastly, Section 5 will discuss upper bounds on the non-backtracking spectrum
in terms of the spectral radius of the adjacency matrix. Additionally, we will
derive a lower bound on the minimum modulus of the non-backtracking spectrum.
Finally, we will identify properties of the non-backtracking spectrum of
bipartite graphs.

##  2 The Non-Backtracking Matrix

Let $G=(V,E)$ be a graph with vertices $V$ and edges $E$. Let $n$ and $m$ be
the number of vertexs and edges of $G$ respectively. Given a starting vertex
on $G$, a sample random walk of length $k$ is a collection of vertices
$(v_{1},...,v_{k})$, where $v_{i}$ is chosen uniformly at random from the
neighbors of $v_{i-1}$. A non-backtracking random walk (NBRW) is a walk where
$v_{i}$ is chosen uniformly from the set of neighbors to $v_{i-1}$ excluding
$v_{i-2}$, for all $i>2$. In order to consider a NBRW as a Markov chain, we
consider an equivalent random walk along the edges of the directed graph
$\hat{G}$. We define $\hat{G}$ to have a directed edge from $i\rightarrow j$
and $j\rightarrow i$ if $i\sim j$ in $G$, and that $i\rightarrow j$ only
connects to an edge $k\rightarrow l$ if $l\neq i$ and $j=k$ (see Figure 1). To
encapsulate this Markov chain in a matrix, we define the non-backtracking
matrix $B$ of $G$ such that

$B((u,v),(x,y))=\begin{cases}1&v=x\text{ and }u\neq y\\\
0&\text{otherwise}\end{cases}$ (1)

where $(u,v)$ and $(x,y)$ are edges between $u\sim v$ and $x\sim y$
respectively. It has previously been proven that the spectrum of $B$ can be
found using Ihara’s Theorem (see [8, 10]).

######  Theorem 2.1 (Ihara’s Theorem).

Given a graph $G$ with $n$ vertexs and $m$ edges, let $B$ be the non-
backtracking matrix of $G$ as defined above. Let $A$ denote the adjacency
matrix of $G$ and $D$ the degree matrix. Then

$\text{det}(I-uB)=(1-u^{2})^{m-n}\text{det}(u^{2}(D-I)-uA+I).$ (2)

Figure 1: A NBRW along the 4-cycle can be considered a Markov chain by
performing a simple random walk along the directed edges on the right graph
with a non-backtracking condition.

Thus the eigenvalues of $B$ all either $\pm 1$ or solutions to
$\text{det}(\mu^{2}I-\mu A+(D-I))=0$. Our goal is identify properties of the
spectrum of $B$, denoted $\sigma(B)$, for a given graph $G$. When $G$ is
$d$-regular (each vertex has degree $d$), then Ihara’s Theorem works out in a
straightforward way to give the spectrum of $B$ (see [1, 9, 16]). This we
state in the following theorem. Similar results have been obtained for
bipartite biregular graphs [9].

######  Theorem 2.2.

Let $G$ be a $d$-regular graph and $A$ the adjacency matrix of $G$. Then the
eigenvalues of $B$ are

$\pm 1,\frac{\lambda_{i}\pm\sqrt{\lambda_{i}^{2}-4(d-1)}}{2},(i=1,...,n)$

where $\lambda_{i}\in\sigma(A)$ and $\pm 1$ each have multiplicity $m-n$.

In general it is useful to know when $B$ is irreducible. Throughout the paper,
we will use this condition to employ the Perron-Frobenius theorem.

######  Proposition 2.3.

Let $G$ be a connected graph that is not a cycle and $d_{\min}\geq 2$. Then
$B$ is irreducible.

###### Proof.

Since $B$ represents a directed graph $\hat{G}$, it suffices to show that the
graph represented by two directed edges between each vertex with the non-
backtracking constraint is strongly connected. Denote $i$ as the directed edge
from $a\rightarrow b$ and $-i$ as the directed edge from $b\rightarrow a$
where $a$ and $b$ are vertices of the original graph $G$. Note that if $G$ is
connected, a simple random walk is irreducible on $G$. Assume that a path
exists on $\hat{G}$ between $i$ and $-i$ for every $i$ in $\hat{G}$. Then a
simple random walk across $\hat{G}$ will have the ability to backtrack after a
finite number of steps. Combining this with the connectedness of $G$ implies
that $\hat{G}$ must be strongly connected. Hence it is sufficient to show that
there is a path from $i$ to $-i$ for every $i$ in $\hat{G}$.

Since $G$ is not a cycle, there must exist at least one vertex with degree
greater than or equal to 3. We examine a walk across $\hat{G}$ beginning at
directed edge $i$. Assume that $i$ is pointing towards a vertex $a$ of degree
at least 3. Assume that we take the shortest path from $i$ to some directed
edge pointing towards $a$ which is not the trivial path of length 0. If this
path arrives at an edge $k$ pointing towards $a$ such that $k\neq i$, then we
can take a step from $k$ to $-i$ since $G$ is connected. If this path arrives
at $i$, then take a step onto a directed edge $j$ which is not in the current
path. We are guaranteed such $j$ exists since $a$ has degree 2. Take the
shortest path from $j$ to another directed edge pointing towards $a$ that is
not $j$ itself. If this path arrives at some directed edge $l\neq i$, then we
can take a step from $l$ to $-i$ since $G$ is connected. If this path arrives
at $i$, then at some point along the path from $j$ to $i$ we intersected at
some edge $r$ from the first shortest path found. When arriving at $r$, rather
than continue to $i$ via $r$, step to $-r$. Then by the existence of the path
from $i$ to $r$, there must exist a path from $-r$ to $-i$. Hence a path
always exist between $i$ and $-i$.

Now assume that $i$ is pointing towards a vertex $b$ of degree 2. Then a
random walk on $\hat{G}$ beginning at $i$ can only travel to one edge. Since
$G$ is connected and $G$ is not a cycle, there exists a path from $i$ to some
edge $k$ which points to a vertex of degree at least 3. Thus, by the previous
statement, a path exists between $k$ and $-k$. Then there is clearly a path
from $-k$ to $-i$. Hence there is a path from $i$ to $-i$. Hence, $G$ is
strongly connected and $B$ is irreducible. ∎

##  3 Examples with few edges

It is clear that as $G$ gets more and more dense, $B$ becomes larger. However,
when $m$ is close to $n$, $B$ is relatively small. In this section, we examine
the spectrum of $B$ specifically when $m\leq n$.

###  3.1 Trees

A tree is a connected graph which contains no cycles. Trees have been found to
be difficult to distinguish using the spectrum of $A$, since Schwenk showed
that many large trees have the same spectrum [20]. In the case of the non-
backtracking matrix, all trees have the same spectrum. To show this, we first
find the characteristic polynomial of the edge adjacency matrix $C$ where the
$G$ is a directed tree, with all edges pointing towards a root vertex and use
this expression to find the non-backtracking spectrum of a tree. We define $C$
as

$C((u,v),(x,y))=\begin{cases}1&v=x\\\ 0&\text{otherwise}\end{cases}.$ (3)

######  Remark 1.

The non-backtracking spectrum of a tree was first explicitly found by Torres
[22]. His proof method uses properties of non-backtracking random walks. We
will use cofactor expansion to show the same result. Additionally we will give
an alternate proof to one of his corollaries using cofactor expansion.

######  Lemma 3.1.

Let $G$ be a directed tree with $n$ vertexs where all edges eventually point
to one root vertex. Let $C$ be the edge adjacency matrix of $G$. Then
$\text{det}(\lambda I-C)=\lambda^{n-1}$.

###### Proof.

Note that a row representing any edge pointing directly to the root vertex of
$G$ will have all 0 entries. Choose an edge $j$ pointing to the root and
perform cofactor expansion across this row of $\lambda I-C$ corresponding to
$j$. This gives $\text{det}(\lambda I-C)=\lambda\text{det}(\lambda
I-C_{\neq\\{j\\}})$, where $C_{\neq\\{j\\}}$ is $C$ with the row and columns
for $j$ deleted. By induction, continue on every edge pointing to the root.
The new $\hat{C}$ will then consist of $k$ directed trees with all edges
pointing to a root. Repeat by induction. Thus, $\text{det}(\lambda
I-C)=\lambda^{n-1}$. ∎

######  Theorem 3.2 ([22]).

Let $B$ be the non-backtracking matrix of a tree $G$. Then $\text{det}(\lambda
I-B)=\lambda^{2n-1}$.

###### Proof.

Let $G$ be a graph with $n$ vertexs and $k$ leaves. Let the $i^{th}$ row of
$B$ represent an edge pointing towards a leaf in $G$. Every entry of this row
will be 0. We write $B$ such that the first $k$ rows represent the $k$ edges
pointing towards the $k$ leaves of the graphs. We cofactor expansion choosing
the first row of $\text{det}(\lambda I-B)$. Then $\text{det}(\lambda
I-B)=\lambda\text{det}(\lambda I-B_{\neq 1})$ where $B_{\neq 1}$ is $B$
without the $1^{st}$ row or column. Continuing we get that $\text{det}(\lambda
I-B)=\lambda^{k}\text{det}(\lambda I-B_{\neq\\{1,...,k\\}})$.

Let the $i^{th}$ row of $B_{\neq\\{1,...,k\\}}$ represent the edge pointing to
the parent of a leaf vertex. Since all rows representing edges pointing to
leaf vertexs have been removed, the $i^{th}$ row will only have one nonzero
entry $\lambda$. Thus, $\text{det}(\lambda
I-B)=\lambda^{k+1}\text{det}(\lambda I-B_{\neq\\{1,...,k,i\\}})$. Continue
this process for the parents of all leaf vertexs and then for parents of
parents. This continues until $B_{\neq\\{1,...,k,i_{1},i_{2},...,i_{j}\\}}$
represents an adjacency matrix of a directed tree of $n-1$ edges. By Lemma
3.1, we get that $\text{det}(\lambda I-B)=\lambda^{2(n-1)}$. ∎

######  Corollary 3.2.1 ([22]).

Let $G$ be a graph with $m$ edges and $T$ be a tree with $n$ vertices. Let $B$
be the non-backtracking matrix of $G$. Define $\hat{G}$ as the graph
constructed by joining $G$ and $T$ on one vertex. Define $\hat{B}$ be the non-
backtracking matrix of $\hat{G}$. Then $\sigma(\hat{B})$ is $\sigma(B)$ along
with eigenvalue 0 with algebraic multiplicity $2(n-1)$.

###### Proof.

Order the entries of $\hat{B}$ such that the last $2(n-1)$ entries represent
edges in the tree $T$. Consider the matrix $\lambda I-\hat{B}$. We can use the
same method in Theorem 3.2 to find that $\text{det}(\lambda
I-\hat{B})=\lambda^{2(n-1)}\text{det}(\lambda
I-\hat{B}_{\neq\\{2m+1,2m+2,...,2m+2(n-1)\\}})=\lambda^{2(n-1)}\text{det}(\lambda
I-B)$. The result follows. ∎

###  3.2 Cycles

In the case $\sigma(K)=\sigma(B)$, we have that $G$ is a cycle $C_{n}$. The
spectrum of the adjacency matrix of $C_{n}$ is known to be the $2\cos(2\pi
j/n)$ for $j=\\{0,...,n-1\\}$ (see [4]). Similarly, the non-backtracking
spectrum of $C_{n}$ can be explicitly calculated. First, we note the following
fact about the spectrum of directed cycles:

######  Lemma 3.3 ([4]).

Let $D_{n}$ be a directed $n$-cycle with adjacency matrix $A$. Then
$\sigma(A)$ consists of the $n^{th}$ complex roots of unity.

In Figure 1, we see that changing each of the edges of $C_{n}$ to be two
directed edges creates two directed cycles $D_{n}$. Given the non-backtracking
condition, these two directed cycles can be considered disjoint. Using this
fact, [22] calculates the non-backtracking spectrum of $C_{n}$ explicity.

######  Theorem 3.4 ([22]).

Let $C_{n}$ be an undirected cycle with $n$ vertices. Let $B$ be the non-
backtracking matrix of $C_{n}$. Then the eigenvalues of $B$ are $e^{2\pi j/n}$
for $j=0,...,n-1$ and each eigenvalue has multiplicity 2.

With an understanding of the non-backtracking spectrum of cycles, we can
expand to graphs with "pendant" cycles. By this we mean a graph $G$ made from
connecting a graph $\hat{G}$ at one vertex with a cycle $C_{n}$, as in Figure
2. We can guarantee that the non-backtracking spectra of graphs with pendant
cycles contain eigenvalues from the non-backtracking spectrum of $C_{n}$.

Figure 2: A graph with an pendant cycle takes any graph and attachs a cycle of
length $n$ to one vertex of the graph.

######  Theorem 3.5.

Let $\hat{G}$ be a graph with $2m$ edges and let $C_{n}$ be a cycle. Let $G$
be a graph created by joining $\hat{G}$ and $C_{n}$ at exactly one vertex. Let
$B$ be the non-backtracking matrix of $G$. Then $e^{2\pi j/n}\in\sigma(B)$ for
$j=0,...,n-1$.

###### Proof.

We construct $B$ such that the first $2m$ rows and columns correspond to the
edges in the graph $\hat{G}$ and the last $2n$ rows and columns correspond to
the edges in $C_{n}$. We know that the non-backtracking matrix of a cycle can
be written as a block diagonal matrix. So

$B=\begin{bmatrix}B_{1}&Q&Q\\\ \textbf{*}&D_{n}&0\\\
\textbf{*}&0&D_{n}\end{bmatrix}$

where $B_{1}$ is the non-backtracking matrix of $\hat{G}$ and the bottom-right
$2\times 2$ block matrix is the non-backtracking matrix of $C_{n}$. Since
$\hat{G}$ and $C_{n}$ are joined at exactly one vertex, there are $d_{r}$ rows
in the first $2m$ rows of $B$ that have nonzero entries in $Q$, where $d_{r}$
is the degree of the vertex joining $\hat{G}$ and $C_{n}$. In fact, we can
define $Q$ as a block of zeros with one column containing non-zero entries.
This column will be identical in the block above each $D_{n}$ block, as each
edge pointing towards the cycle points to each of the two directed cycles
formed on the directed edges. We define a vector

$\displaystyle\mathbf{x}$
$\displaystyle=\begin{bmatrix}0&\dotsb&0&\mathbf{y}&-\mathbf{y}\end{bmatrix}^{T}$

where the first $2m$ entries are 0, and $\mathbf{y}=\begin{bmatrix}1&e^{2\pi
ji/n}&e^{2(2)\pi ji/n}&\dotsb&e^{2(n-1)\pi ji/n}\end{bmatrix}^{T}$. We then we
recall that $D_{n}\mathbf{y}=e^{2\pi ij/n}\mathbf{y}$. Thus we see that

$\displaystyle B\mathbf{x}$ $\displaystyle=\begin{bmatrix}B_{1}&Q&Q\\\
\textbf{*}&D_{n}&0\\\ \textbf{*}&0&D_{n}\end{bmatrix}\begin{bmatrix}0\\\
\mathbf{y}\\\
-\mathbf{y}\end{bmatrix}=\begin{bmatrix}Q\mathbf{y}-Q\mathbf{y}\\\
D_{n}\mathbf{y}\\\ -D_{n}\mathbf{y}\end{bmatrix}=\begin{bmatrix}0\\\ e^{2\pi
ij/n}\mathbf{y}\\\ -e^{2\pi ij/n}\mathbf{y}\end{bmatrix}=e^{2\pi
ij/n}\begin{bmatrix}0\\\ \mathbf{y}\\\ -\mathbf{y}\end{bmatrix}=e^{2\pi
ij/n}\mathbf{x}.$

So $e^{2\pi ij/n}\in\sigma(B)$. ∎

We define a specific subset of these graphs with pendant cycles where both
$\hat{G}$ and $C_{n}$ are cycles. We will call these graphs pinwheel graphs.
An example of a pinwheel graph can be found in Figure 3.

Figure 3: An example of a pinwheel graph with two 3-cycles connected at one
vertex.

######  Corollary 3.5.1.

Let $G$ be a pinwheel graph made by connecting $p$ cycles of length $k$ at one
vertex. Let $B$ be its non-backtracking matrix. Then $e^{2\pi
ij/k}\in\sigma(B)$ with multiplicity $p$ for $j\in\\{0,...,k-1\\}$, $e^{2\pi
ij/(2k)}$ with multiplicity $p-1$ for all $j\in\\{1,3,5,...,2k-1\\}$, and the
$k^{th}$ complex roots of $2p-1$ are in $\sigma(B)$ with multiplicity 1. These
capture the entirety of $\sigma(B)$ and the spectral radius of $B$ is
$|(2p-1)^{1/k}|$.

###### Proof.

We can write $B$ such that

$\displaystyle B=$ $\displaystyle\begin{bmatrix}C_{k}&0&R&R&\dotsb&R&R\\\
0&C_{k}&R&R&\dotsb&R&R\\\ R&R&C_{k}&0&\dotsb&R&R\\\ R&R&0&C_{k}&\dotsb&R&R\\\
\vdots&\vdots&\vdots&\vdots&\ddots&\vdots&\vdots\\\ R&R&R&R&\dotsb&C_{k}&0\\\
R&R&R&R&\dotsb&0&C_{k}\end{bmatrix}$

where $R$ is a block of all zeros, with the exception of the last row, which
has a 1 in the first entry of the row, and zeroes everywhere else. By
straightforward computation, we can see that

$\begin{bmatrix}\mathbf{y}&-\mathbf{y}&0&0&0&0&\dotsb&0&0\end{bmatrix}^{T}$
$\begin{bmatrix}0&0&\mathbf{y}&-\mathbf{y}&0&0&\dotsb&0&0\end{bmatrix}^{T}$
$\vdots$
$\begin{bmatrix}0&0&0&0&0&0&\dotsb&\mathbf{y}&-\mathbf{y}\end{bmatrix}^{T}$

are all eigenvectors with eigenvalue $e^{2\pi ij/k}$ where
$C_{k}\mathbf{y}=e^{2\pi ij/k}\mathbf{y}$. Thus, each root of unity $e^{2\pi
ij/k}$ has at least algebraic multiplicity $p$.

Let $C_{2k}\mathbf{z}=e^{2\pi ij/2k}\mathbf{z}$ for $j\in\\{1,3,5,...,2k-1\\}$
and $\mathbf{z}=\begin{bmatrix}z_{1}&z_{2}\end{bmatrix}^{T}$ where $z_{i}$ is
the $i^{th}$ half of the eigenvector $\mathbf{z}$. Then
$z_{1}=\begin{bmatrix}\alpha_{1}&\dotsb&\alpha_{k}\end{bmatrix}^{T}$ and
$z_{2}=\begin{bmatrix}\beta_{1}&\dotsb&\beta_{k}\end{bmatrix}^{T}$. Since
$C_{2k}$ is a circulant matrix, then $\alpha_{l}=e^{2\pi ij/2k}\alpha_{l+1}$
for all $l\in\\{1,...,k-1\\}$, $\beta_{l}=e^{2\pi ij/2k}\beta_{l+1}$ for all
$l\in\\{1,...,k-1\\}$, $\alpha_{k}=e^{2\pi ij/2k}\beta_{1}$, and
$\beta_{k}=e^{2\pi ij/2k}\alpha_{1}$. Lastly define the vector

$\mathbf{v}_{1}=\begin{bmatrix}(p-1)z_{1}&-(p-1)z_{2}&-z_{1}&z_{2}&-z_{1}&z_{2}&\dotsb&-z_{1}&z_{2}\end{bmatrix}^{T}.$

Then we see through direct calculation that

$\displaystyle
B\mathbf{v}_{1}=\begin{bmatrix}-(p-1)\mathbf{r}&\mathbf{r}&\dotsb&\mathbf{r}\end{bmatrix}=e^{2\pi
ij/2k}\mathbf{v}_{1}$

where
$\mathbf{r}=\begin{bmatrix}\mathbf{r}_{1}&\mathbf{r}_{2}\end{bmatrix}^{T}$,
$\mathbf{r}_{1}=\begin{bmatrix}-\alpha_{2}&\dotsb&-\alpha_{k}&-\beta_{1}\end{bmatrix}^{T}$
and
$\mathbf{r}_{2}=\begin{bmatrix}\beta_{2}&\dotsb&\beta_{k}&\alpha_{1}\end{bmatrix}^{T}$.
So $\mathbf{v}_{1}$ is an eigenvector of $B$ with associated eigenvalue
$e^{2\pi ij/2k}$. Similarly, we define

$\mathbf{v}_{2}=\begin{bmatrix}-z_{1}&z_{2}&(p-1)z_{1}&-(p-1)z_{2}&-z_{1}&z_{2}&\dotsb&-z_{1}&z_{2}\end{bmatrix}$

and so on for $\mathbf{v}_{i}$ where $i\in\\{1,...,p\\}$. By a similar
calculation, we see that $B\mathbf{v}_{i}=e^{2\pi ij/2k}\mathbf{v}_{i}$ for
all $i$. We now show the set $\\{\mathbf{v}_{1},...,\mathbf{v}_{p-1}\\}$ is
linearly independent. Let $0=\sum_{i=1}^{n-1}\gamma_{i}\mathbf{v}_{i}$. Note
that last two entries of this summation give that
$\sum_{i=1}^{p-1}\gamma_{i}z_{1}=0$ and $\sum_{i=1}^{p-1}\gamma_{i}z_{2}=0$.
Then the first entry gives that
$\gamma_{1}(p-1)z_{1}=\sum_{i=2}^{p-1}\gamma_{i}z_{1}$. From the second to
last entry, this must mean that $\gamma_{1}(p-1)z_{1}=-\gamma_{1}z_{1}$. Since
$z_{1}\neq 0$ and $p-1$ is fixed, then $\gamma_{1}=0$. The third entry then
gives that $\gamma_{2}(p-1)z_{1}=\sum_{i=3}^{p-1}\gamma_{i}z_{1}$. Again, by
the second to last entry, we get that $\gamma_{2}(p-1)z_{1}=-\gamma_{2}z_{1}$.
So $\gamma_{2}=0$. Continuing through every odd entry in order of
$\sum_{i=1}^{p-1}\gamma_{i}\mathbf{v}_{i}$, we get that $\gamma_{i}=0$ for all
$i=\\{1,...,p-1\\}$. Thus, the set
$\\{\mathbf{v}_{1},\dotsb,\mathbf{v}_{p-1}\\}$ must be linearly independent.
Thus, $e^{2\pi ij/2k}$ must have algebraic multiplicity at least $p-1$.

We now let $\lambda=(2p-1)^{1/k}$ be one of the $k^{th}$ complex roots of
$2p-1$. Then we define
$\mathbf{w}=\begin{bmatrix}\lambda&\lambda^{2}&\dotsb\lambda^{k}&\lambda&\dotsb&\lambda^{k}&\dotsb&\lambda&\dotsb&\lambda^{k}\end{bmatrix}$
where $\mathbf{w}\in\mathbb{C}^{2pk}$. Then we see that

$\displaystyle B\mathbf{w}$
$\displaystyle=\begin{bmatrix}\lambda^{2}&\dotsb&\lambda^{k+1}&\lambda^{2}&\dotsb&\lambda^{k+1}&\dotsb&\lambda^{2}&\dotsb&\lambda^{k+1}\end{bmatrix}=\lambda\mathbf{w}.$

Since there are $k$ complex roots of $2p-1$, there are $k$ unique eigenvalues
with at least algebraic multiplicity 1. Further since $\mathbf{w}$ is positive
and $B$ is nonnegative and irreducible by Propostion 2.3, then
$|(2p-1)^{1/k}|$ must be the spectral radius of $B$.

To summarize, we have the following eigenvalues: $e^{2\pi ij/k}$ for
$j\in\\{0,...,k-1\\}$ with multiplicity at least $p$, $e^{2\pi il/2k}$ for
$l\in\\{1,3,...,2k-1\\}$ with multiplicity at least $p-1$, and the $k$ roots
$(2p-1)^{1/k}$ with multiplicity at least $1$. We then see that
$pk+(p-1)k+k=2pk$. Since $B\in M_{2pk}$, then all the multiplicities mentioned
must be exact. ∎

##  4 The $K$ Matrix

The eigenvalues of $B$ coming from the equation 2 in Ihara’s Theorem can be
found independent of $B$. We define

$K=\begin{bmatrix}A&D-I\\\ -I&0\end{bmatrix}$

which has characteristic polynomial $\text{det}(\mu^{2}I-\mu A+(D-I))$. Using
$K$, we can create a decomposition of $B$ that clearly organizes the spectrum
of $B$ and gives an alternate proof of Ihara’s Theorem.

######  Remark 2.

Lubetzky and Peres showed the matrix $B$ is unitarily similar to a block
diagonal matrix showing which clearly shows the spectrum of $B$ as well as the
eigenvectors.

######  Theorem 4.1 ([15]).

Let $G$ be a connected $d$-regular graph ($d\geq 3)$ on $n$ vertices. Let
$N=dn$ and $\lambda_{i}\in\sigma(A)$, with $\lambda_{1}=d$. Then the operator
$B$ is unitarily similar to

$\Lambda=\text{diag}\Biggl{(}d-1,\begin{bmatrix}\theta_{2}&\alpha_{2}\\\
0&\theta_{2}^{\prime}\end{bmatrix},...,\begin{bmatrix}\theta_{n}&\alpha_{n}\\\
0&\theta_{n}^{\prime}\end{bmatrix},-1,...,-1,1,...,1\Biggr{)}$

where $|\alpha_{i}|<2(d-1)$ for $i$, $\theta_{i}$ and $\theta_{i}^{\prime}$
are defined as the solutions of

$\theta^{2}-\lambda_{i}\theta+d-1=0$

and $-1$ has multiplicity $N/2-n$ and $1$ has multiplicity $N/2-n+1$.

While we are unable to make such a similarity for a general graph $G$, we will
decompose $B$ in a similar manner into a block diagonal matrix to see the
eigenvalues more clearly.

######  Remark 3.

Torres succeeded in diagonalizing $B$ if the eigenvalues $\mu\in\sigma(B)$
such that $|\mu|>1$ are simple. We will not use this requirement in our proof.

To create this decomposition, we need to relate the matrices $B$ and $K$
outside of just their spectrum. Define $S\in M_{2m\times n}$ and $T\in
M_{n\times 2m}$ where

$\displaystyle S((u,v),x)=\begin{cases}1&v=x\\\ 0&\text{otherwise}\end{cases}$
$\displaystyle T(x,(u,v))=\begin{cases}1&x=u\\\
0&\text{otherwise}\end{cases}.$ (4)

Define $\tau\in M_{2m\times 2m}$ to be the non-backtracking operator

$\displaystyle\tau((u,v),(x,y))$ $\displaystyle=\begin{cases}1&v=x\text{ and
}u=y\\\ 0&\text{otherwise}\end{cases}.$ (5)

Matrix multiplication then gives the following identities:

$\displaystyle C$ $\displaystyle=ST,$ $\displaystyle B$
$\displaystyle=ST-\tau,$ $\displaystyle D$ $\displaystyle=T\tau S,$
$\displaystyle A$ $\displaystyle=TS.$ (6)

Using these identities it is clear that

$B\begin{bmatrix}S&T^{T}\end{bmatrix}=\begin{bmatrix}S&T^{T}\end{bmatrix}K.$
(7)

Before creating our decomposition, we also need to understand the eigenvectors
of $B$ for eigenvalues $\pm 1$. Lubetzky and Peres [15] show that these
eigenvectors come from $\mathscr{E}_{-1}\cap\text{Null(ST)}$ and
$\mathscr{E}_{1}\cap\text{Null}(ST)$ respectively, where $\mathscr{E}_{i}$ is
the eigenspace of $\tau$ corresponding to eigenvalue $i$. They further show
that $\text{dim}(\mathscr{E}_{-1}\cap\text{Null(ST)})=m-n+1$ and
$\text{dim}(\mathscr{E}_{1}\cap\text{Null(ST)})=m-n$ or $m-n+1$ if $G$ is
bipartite. With this we create our decomposition.

######  Theorem 4.2.

Let $G$ be a connected graph and $B$ its non-backtracking matrix. Let $R\in
M_{2m\times 2(m-n)}$ where the columns of $R$ are linearly independent and the
first $m-n$ columns of $R$ are taken from
$\mathscr{E}_{-1}\cap\text{Null}(ST)$ and the rest are taken from
$\mathscr{E}_{1}\cap\text{Null}(ST)$. Then

$BX=X\left[\begin{array}[]{ccc}K&0&0\\\ 0&I_{m-n}&0\\\
0&0&-I_{m-n}\end{array}\right]$

and $X=\begin{bmatrix}S&T^{T}&R\end{bmatrix}$.

###### Proof.

This follows directly from matrix multiplication and the properties of the
columns of $R$. ∎

######  Remark 4.

It clearly follows from the previous theorem that $\text{det}(\mu I-B)$ is
just the characteristic polynomial of this block diagonal decomposition.
Hence, Ihara’s Theorem is an immediate corollary of the above theorem. Even
more, Theorem 4.2 does not just give the eigenvalues of $B$ but also the
eigenvectors. Let $\mathbf{x}$ be an eigenvector of $K$. Then

$\displaystyle BX\begin{bmatrix}\mathbf{x}\\\ 0\\\ 0\end{bmatrix}$
$\displaystyle=X\begin{bmatrix}K&0&0\\\ 0&I_{m-n}&0\\\
0&0&-I_{m-n}\end{bmatrix}\begin{bmatrix}x\\\ 0\\\
0\end{bmatrix}=X\begin{bmatrix}K\mathbf{x}\\\ 0\\\ 0\end{bmatrix}=\mu
X\begin{bmatrix}\mathbf{x}\\\ 0\\\ 0\end{bmatrix}.$

Hence we know all the eigenvectors of $B$ associated with eigenvalues of $K$
are of the form $X\begin{bmatrix}\mathbf{x}&0&0\end{bmatrix}^{T}$.
Additionally, from the construction of $R$, we see that the eigenvectors for
$\pm 1$ are $\mathbf{y}\in\mathscr{E}_{-1}\cap\text{Null}(ST)$ and
$\mathbf{z}\in\mathscr{E}_{1}\cap\text{Null}(ST)$ respectively.

##  5 Properties of $\sigma(B)$ using $\sigma(K)$

With a decomposition of $B$ in terms of $K$, we now want to better understand
the eigenvalues of $K$. Our goal in this section is to use properties of $K$
in order to place bounds on the eigenvalues of $B$. Using the Gershgorin
Theorem we immediately have a bound on the spectral radius of $B$ in terms of
the degree of $G$ [7].

######  Proposition 5.1.

Let $G$ be a connected graph with $B$ the non-backtracking matrix and
$d_{\max}$ the maximum of degree of $G$. Then $\rho(B)\leq d_{\max}-1$ with
equality if and only if $G$ is regular.

We will show a stronger bound using the matrix $K$ and its relationship with
$B$. Immediately from the structure of $K$, we can learn some information
about its eigenvalue-eigenvector pairs.

######  Proposition 5.2.

Let $G$ be a graph and $K$ as defined above. Then the following are true:

  1. (i)

Every eigenvector of $K$ is of the form
$\begin{bmatrix}-\mu\mathbf{y}&\mathbf{y}\end{bmatrix}^{T}$ where
$\mu\in\sigma(K)$,

  2. (ii)

$1\in\sigma(K)$ with geometric multiplicity equal to the number of connected
components of $G$,

  3. (iii)

the nullity of $K$ is the number of degree 1 vertices, and

  4. (iv)

$K$ is invertible with inverse $K^{-1}=\begin{bmatrix}0&-I\\\
(D-I)^{-1}&(D-I)^{-1}A\end{bmatrix}$ if and only if $d_{\min}\geq 2$.

###### Proof.

  1. (i)

Assume that $\mu\in\sigma(K)$ with eigenvector
$\begin{bmatrix}\mathbf{x}&\mathbf{y}\end{bmatrix}^{T}$. Then

$\displaystyle\mu\begin{bmatrix}\mathbf{x}\\\
\mathbf{y}\end{bmatrix}=\begin{bmatrix}A&D-I\\\
-I&0\end{bmatrix}\begin{bmatrix}\mathbf{x}\\\
\mathbf{y}\end{bmatrix}=\begin{bmatrix}A\mathbf{x}+(D-I)\mathbf{y}\\\
-\mathbf{x}\end{bmatrix}.$

Then bottom block gives that $\mathbf{x}=-\mu\mathbf{y}$, so the eigenvector
must be of the form $\begin{bmatrix}-\mu\mathbf{y}&\mathbf{y}\end{bmatrix}$.

  2. (ii)

Let $\mathbf{x}=\begin{bmatrix}\mathbf{1}&-\mathbf{1}\end{bmatrix}$ where
$\mathbf{1}\in M_{n\times 1}$ is an all-ones vector. Then

$\displaystyle K\mathbf{x}=\begin{bmatrix}A\mathbf{1}-(D-I)\mathbf{1}\\\
-\mathbf{1}\end{bmatrix}=\begin{bmatrix}\mathbf{k}-\mathbf{k}+\mathbf{1}\\\
-\mathbf{1}\end{bmatrix}=\mathbf{x}$

where $\mathbf{k}$ is the degree vector of $G$. Thus, $K\mathbf{x}=\mathbf{x}$
and $1\in\sigma(K)$.

Let $(1,\begin{bmatrix}-\mathbf{y}&\mathbf{y}\end{bmatrix}^{T})$ be a general
eigenvalue-eigenvector pair for $1\in\sigma(K)$. Then
$\mathbf{y}-A\mathbf{y}+(D-I)\mathbf{y}=0$. Rearranging we see that
$(D-A)\mathbf{y}=0$. So $\mathbf{y}\in\text{Null}(L)$ where $L$ is the
Laplacian of $G$. So $\text{mult}(1)\leq\text{Nullity}(L)$.

Now assume that $\mathbf{z}\in\text{Null}(L)$. Then $(D-A)\mathbf{z}=0$. So
$\mathbf{z}-A\mathbf{z}+(D-I)\mathbf{z}=0$. Then we see that

$K\begin{pmatrix}-\mathbf{z}&\mathbf{z}\end{pmatrix}^{T}=\begin{pmatrix}-A\mathbf{z}+(D-I)\mathbf{z}\\\
\mathbf{z}\end{pmatrix}=\begin{pmatrix}-\mathbf{z}&\mathbf{z}\end{pmatrix}^{T}.$

Thus the geometric multiplicity of $1\in\sigma(K)$ is the nullity of $L$. By
well-known properties of the Laplacian (see [4]), the geometric multiplicity
of $1\in\sigma(K)$ is the number of connected components in $G$.

  3. (iii)

We have

$\begin{bmatrix}A&D-I\\\ -I&0\end{bmatrix}\begin{bmatrix}0\\\
\mathbf{y}\end{bmatrix}=\begin{bmatrix}0\\\ 0\end{bmatrix}$

if and only if

$\begin{bmatrix}(D-I)\mathbf{y}\\\ 0\end{bmatrix}=\begin{bmatrix}0\\\
0\end{bmatrix}.$

Thus $[0\ \mathbf{y}]^{T}$ is in the nullspace of $K$ if and only if
$(D-I)\mathbf{y}=0$. Note that $D-I$ is diagonal, and so the dimension of its
nullspace is equal to the number of diagonal entries that are 0. From this,
the result follows.

  4. (iv)

Immediately from (iii) we that $K$ is invertible if and only if $d_{\min}\geq
2$. If $d_{\min}\geq 2$, then

$\displaystyle\begin{bmatrix}A&D-I\\\ -I&0\end{bmatrix}\begin{bmatrix}0&-I\\\
(D-I)^{-1}&(D-I)^{-1}A\end{bmatrix}$ $\displaystyle=\begin{bmatrix}I&0\\\
0&I\end{bmatrix}$ $\displaystyle\begin{bmatrix}0&-I\\\
(D-I)^{-1}&(D-I)^{-1}A\end{bmatrix}\begin{bmatrix}A&D-I\\\ -I&0\end{bmatrix}$
$\displaystyle=\begin{bmatrix}I&0\\\ 0&I\end{bmatrix}.$

So $K^{-1}=\begin{bmatrix}0&-I\\\ (D-I)^{-1}&(D-I)^{-1}A\end{bmatrix}.$

∎

######  Remark 5.

Proposition 5.2(iii) can also be proved using the relationship between $B$ and
$K$ and results about the invertibility of $B$ found in [22].

With Proposition 5.2(i), we can create a relationship between the eigenvalues
of $A$ and the eigenvalues of $B$.

######  Proposition 5.3.

Let $\mu\in\sigma(K)$ with eigenvector
$\begin{bmatrix}-\mu\mathbf{y}&\mathbf{y}\end{bmatrix}^{T}$ and let
$\lambda\in\sigma(A)$ such that $A\mathbf{x}=\lambda\mathbf{x}$. If
$\mathbf{x}^{T}\mathbf{y}\neq 0$, then

$\mu=\frac{\lambda\pm\sqrt{\lambda^{2}-4\mathbf{x}^{T}(D-I)\mathbf{y}}}{2}.$

###### Proof.

Recall that $\mu^{2}\mathbf{y}-\mu A\mathbf{y}+(D-I)\mathbf{y}=0$ where
$\mathbf{y}$ is the second half of the eigenvector
$\begin{bmatrix}-\mu\mathbf{y}&\mathbf{y}\end{bmatrix}^{T}$ of $K$
corresponding to eigenvalue $\mu$. Let $\mathbf{x}^{T}$ be an eigenvector of
$A$ with associated eigenvalue $\lambda$, where $\mathbf{x}$ and $\mathbf{y}$
are not orthogonal, and scale $\mathbf{y}$ such that
$\mathbf{x}^{T}\mathbf{y}=1$. Then left multiplying by $\mathbf{x}^{T}$ gives
$\mu^{2}-\mu\lambda+\mathbf{x}^{T}(D-I)\mathbf{y}=0$. With the quadratic
formula, we know that

$\mu=\frac{\lambda\pm\sqrt{\lambda^{2}-4\mathbf{x}^{T}(D-I)\mathbf{y}}}{2}.$

∎

######  Remark 6.

Note that this formula does not necessarily give every eigenvalue $\mu$. If
$K$ is not diagonalizable (for example, $K$ of any cycle), then there will
exist $\mu\in\sigma(K)$ with no corresponding eigenvector
$\begin{bmatrix}-\mu\mathbf{y}&\mathbf{y}\end{bmatrix}^{T}$. Additionally we
are not guaranteed that $\mathbf{x}^{T}\mathbf{y}\neq 0$ for all pairs
$(\mathbf{x},\mathbf{y})$. In fact many $\mathbf{x}$ and $\mathbf{y}$ exist
such that $\mathbf{x}^{T}\mathbf{y}=0$. However the eigenvectors of $A$ form a
basis of $\mathbf{R}^{n}$, so for each $\mu\in\sigma(K)$ with eigenvector
$\begin{bmatrix}-\mu\mathbf{y}&\mathbf{y}\end{bmatrix}^{T}$ there exists some
$i$ such that $A\mathbf{x}_{i}=\lambda_{i}\mathbf{x}_{i}$ where
$\mathbf{x}_{i}^{T}\mathbf{y}\neq 0$.

######  Remark 7.

In the case of a $d$-regular graph $D-I=(d-1)I$ which allows us to use $K$ in
order to provide an alternate proof to Theorem 2.2. To do this we need to
ensure $K$ is diagonalizable. Assume that $d\geq 2$ for a given graph $G$. Let
$\mathbf{x}$ be an eigenvector of $A$ with associated eigenvalue $\lambda$.
Define $\mu_{1}=\frac{\lambda+\sqrt{\lambda^{2}-4(d-1)}}{2}$ and
$\mu_{2}=\frac{\lambda-\sqrt{\lambda^{2}-4(d-1)}}{2}$. This implies that
$\mu_{1}^{2}-\mu_{1}\lambda+(d-1)=0$ and $\mu_{2}^{2}-\mu_{2}\lambda+(d-1)=0$.
Define the vector $\mathbf{v}_{i}=\begin{bmatrix}-\mu_{i}x&x\end{bmatrix}$.
Then we see that

$\displaystyle K\mathbf{v}_{i}$ $\displaystyle=\begin{bmatrix}A&(d-1)I\\\
-I&0\end{bmatrix}\begin{bmatrix}-\mu_{i}\mathbf{x}\\\
\mathbf{x}\end{bmatrix}=\begin{bmatrix}-\mu_{i}\lambda\mathbf{x}+(d-1)\mathbf{x}\\\
\mu_{i}\mathbf{x}\end{bmatrix}=\begin{bmatrix}-\mu_{i}^{2}\mathbf{x}\\\
\mu_{i}\mathbf{x}\end{bmatrix}=\mu_{i}\mathbf{v}_{i}.$

Thus, both $\mathbf{v}_{1}$ and $\mathbf{v}_{2}$ are eigenvectors. Since
$\mu_{1}\neq\mu_{2}$, we know that $\mathbf{v}_{1}\neq\mathbf{v}_{2}$.
Further, we know that $A$ is diagonalizable. Thus, $\mu_{i}$ has the same
algebraic and geometric multiplicity. Lastly, there are $2n$ distinct
$\mu_{i}$ since each eigenvector $\mathbf{x}$ of $A$ creates two unique
eigenvalue-eigenvector pairs. Since $K\in M_{2n}$, $K$ is diagonalizable.

Now that we know $K$ is diagonalizable, define $f(x)=x+\frac{1}{x}(d-1)$. Let
$\mu\in\sigma(K)$ be an eigenvalue of $K$. Recall all eigenvectors of $K$ can
be written as $\begin{bmatrix}-\mu\mathbf{y}&\mathbf{y}\end{bmatrix}^{T}$,
implying $-\mu A\mathbf{y}+(d-1)\mathbf{y}=-\mu^{2}\mathbf{y}$. Also note that
$d\geq 2$, so by Proposition 5.2(iii) $\mu\neq 0$ and
$A\mathbf{y}=(\mu+\frac{1}{\mu}(d-1))\mathbf{y}$. So there exists some
$\lambda\in\sigma(A)$ such that $\mu+\frac{1}{\mu}(d-1)=\lambda$. Thus,
$f(\sigma(K))\subset\sigma(A)$.

We also know there are two solutions to the equation
$\mu+\frac{1}{\mu}(d-1)=\lambda$:

$\mu=\frac{\lambda\pm\sqrt{\lambda^{2}-4(d-1)}}{2}.$

Let $\mu_{1},\mu_{2}$ be the two solutions to this equation where $\mu_{1}$
and $\mu_{2}$ are the plus and minus solutions respectively. Assume that
$\begin{bmatrix}-\mu_{1}\mathbf{y}&\mathbf{y}\end{bmatrix}^{T}$ is an
eigenvector of $K$. Then we know that
$A\mathbf{y}=(\mu_{1}+\frac{1}{\mu_{1}}(d-1))\mathbf{y}$ and hence
$A\mathbf{y}=(\mu_{2}+\frac{1}{\mu_{2}}(d-1))\mathbf{y}$. Rearranging we get
$-\mu_{2}^{2}\mathbf{y}=-\mu_{2}A\mathbf{y}+(d-1)\mathbf{y}$. So,
$K\begin{bmatrix}-\mu_{2}\mathbf{y}&\mathbf{y}\end{bmatrix}^{T}=\mu_{2}\begin{bmatrix}-\mu_{2}\mathbf{y}&\mathbf{y}\end{bmatrix}^{T}$.
Similarly, if $\begin{bmatrix}-\mu_{2}\mathbf{y}&\mathbf{y}\end{bmatrix}^{T}$
is an eigenvector of $K$ with eigenvalue $\mu_{2}$, then
$\begin{bmatrix}-\mu_{1}\mathbf{y}&\mathbf{y}\end{bmatrix}^{T}$ is an
eigenvector of $K$. Since $K$ is diagonalizable, then $\mu_{1}$ and $\mu_{2}$
have the same multiplicity. Let $\text{mult}(\mu_{i})$ be the algebraic
multiplicity of $\mu_{i}$. Order the eigenvalues of $K$ such that if $\mu$ and
$\hat{\mu}$ are both solutions of $\lambda=\mu+\frac{1}{\mu}(d-1)$, then
$\mu=\mu_{i}$ and $\hat{\mu}=\mu_{-i}$. Then we know that
$2n=\sum_{i=1}^{2n}\text{mult}(\mu_{i})=\sum_{i=1}^{n}2(\text{mult}(\mu_{i}))=2\sum_{i=1}^{n}\text{mult}(\mu_{i})$.
So $n=\sum_{i=1}^{n}\text{mult}(\mu_{i})$. Then we know that
$|f(\sigma(K))|=\sum_{i=1}^{n}\text{mult}(\mu_{i})=n$. Since $|\sigma(A)|=n$
and $f(\sigma(K))\subseteq\sigma(A)$, $\sigma(A)=f(\sigma(K))$.

Our goal now is to use Proposition 5.3 to bound the spectrum of $B$. We begin
by bounding the "bottom" of the spectrum using a formula similar to that of
Proposition 5.3 but not quite equal.

######  Theorem 5.4.

Let $G$ be a connected graph where $d_{\min}\geq 2$. Then $|\mu|\geq 1$ for
all $\mu\in\sigma(B)$.

###### Proof.

Recall that any $\mu\neq\pm 1$ satisfies the equation $\mu^{2}\mathbf{y}-\mu
A\mathbf{y}+(D-I)\mathbf{y}=0$ for some vector $\mathbf{y}\neq 0$. Assume that
$\|\mathbf{y}\|_{2}=1$. Then left multiplying by $\mathbf{y}^{T}$ gives
$\mu^{2}-\mu\mathbf{y}^{T}A\mathbf{y}+\mathbf{y}^{T}(D-I)\mathbf{y}=0.$ The
quadratic equation then gives

$\mu=\frac{\mathbf{y}^{T}A\mathbf{y}\pm\sqrt{(\mathbf{y}^{T}A\mathbf{y})^{2}-4\mathbf{y}^{T}(D-I)\mathbf{y}}}{2}.$

We work by cases:

  1. 1.

Assume that $(\mathbf{y}^{T}A\mathbf{y})^{2}<4\mathbf{y}^{T}(D-I)\mathbf{y}$.
Then

$\displaystyle|\mu|=\frac{(\mathbf{y}^{T}A\mathbf{y})^{2}}{4}+\mathbf{y}^{T}(D-I)\mathbf{y}-\frac{(\mathbf{y}^{T}A\mathbf{y})^{2}}{4}=\mathbf{y}^{T}D\mathbf{y}-1\geq
2-1=1.$

  2. 2.

Assume that $(\mathbf{y}^{T}A\mathbf{y})^{2}=4\mathbf{y}^{T}(D-I)\mathbf{y}$.
Then

$|\mu|=\Bigg{|}\frac{\mathbf{y}^{T}A\mathbf{y}}{2}\Bigg{|}=\Bigg{|}\sqrt{\mathbf{y}^{T}(D-I)\mathbf{y}}\Bigg{|}\geq\sqrt{2}\geq
1.$

  3. 3.

Assume that $(\mathbf{y}^{T}A\mathbf{y})^{2}>4\mathbf{y}^{T}(D-I)\mathbf{y}$.
If
$\mu=\frac{\mathbf{y}^{T}A\mathbf{y}+\sqrt{(\mathbf{y}^{T}A\mathbf{y})^{2}-4\mathbf{y}^{T}(D-I)\mathbf{y}}}{2}$,
then

$|\mu|=\Bigg{|}\frac{\mathbf{y}^{T}A\mathbf{y}+\sqrt{(\mathbf{y}^{T}A\mathbf{y})^{2}-4\mathbf{y}^{T}(D-I)\mathbf{y}}}{2}\Bigg{|}\geq\Bigg{|}\frac{\mathbf{y}^{T}A\mathbf{y}}{2}\Bigg{|}=|\sqrt{\mathbf{y}^{T}(D-I)\mathbf{y}}|\geq
1.$

Assume
$\mu=\frac{\mathbf{y}^{T}A\mathbf{y}-\sqrt{(\mathbf{y}^{T}A\mathbf{y})^{2}-4\mathbf{y}^{T}(D-I)\mathbf{y}}}{2}$.
Define the function

$g(x)=\Bigg{|}\frac{x-\sqrt{x^{2}-4r}}{2}\Bigg{|}$

on the domain $(-\infty,-2\sqrt{r}]\cup[2\sqrt{r},\infty)$ where
$r=\mathbf{y}^{T}(D-I)\mathbf{y}$. This function is clearly non-increasing. We
also know that
$(\mathbf{y}^{T}A\mathbf{y})^{2}>4\mathbf{y}^{T}(D-I)\mathbf{y}$. So either
$-\mathbf{y}^{T}A\mathbf{y}>2\sqrt{r}$ or
$\mathbf{y}^{T}A\mathbf{y}>2\sqrt{r}$.

First assume that $-\mathbf{y}^{T}A\mathbf{y}>2\sqrt{r}$. Thus,
$\mathbf{y}^{T}A\mathbf{y}<0$. Since $r\geq 1$, we know that
$\mathbf{y}^{T}A\mathbf{y}<2\sqrt{r}$. Since $g$ is non-increasing, then
$g(\mathbf{y}^{T}A\mathbf{y})>g(2\sqrt{r})\geq 1$. Thus, $|\mu|\geq 1$.

Now assume that $\mathbf{y}^{T}A\mathbf{y}>2\sqrt{r}$. Note that if
$g(\mathbf{y}^{T}A\mathbf{y})=1$, then

$\displaystyle 1$
$\displaystyle=\frac{\mathbf{y}^{T}A\mathbf{y}-\sqrt{(\mathbf{y}^{T}A\mathbf{y})^{2}-4\mathbf{y}^{T}(D-I)\mathbf{y}}}{2}$
$\displaystyle\sqrt{(\mathbf{y}^{T}A\mathbf{y})^{2}-4\mathbf{y}^{T}(D-I)\mathbf{y}}$
$\displaystyle=\mathbf{y}^{T}A\mathbf{y}-2$
$\displaystyle(\mathbf{y}^{T}A\mathbf{y})^{2}-4\mathbf{y}^{T}(D-I)\mathbf{y}$
$\displaystyle=(\mathbf{y}^{T}A\mathbf{y})^{2}-4\mathbf{y}^{T}A\mathbf{y}+4$
$\displaystyle\mathbf{y}^{T}(A-(D-I))\mathbf{y}$ $\displaystyle=1$
$\displaystyle\mathbf{y}^{T}(D-A)\mathbf{y}$ $\displaystyle=0.$

Thus, if $g(\mathbf{y}^{T}A\mathbf{y})=1$, then
$\mathbf{y}^{T}A\mathbf{y}=\mathbf{y}^{T}D\mathbf{y}$. Further, we know that
the Laplacian is positive semidefinite [5], so
$\mathbf{y}^{T}D\mathbf{y}\geq\mathbf{y}^{T}A\mathbf{y}$. Since $g$ is non-
increasing, then $g(\mathbf{y}^{T}A\mathbf{y})\geq 1$ for all $\mathbf{y}$. So
$|\mu|\geq 1$.

Thus, $|\mu|\geq 1$ for all $\mu\in\sigma(B)$. ∎

######  Remark 8.

An alternate proof of Theorem 5.4 without using $K$ can be found in [22].

With the fact that the modulus of all $\mu\in\sigma(B)$ are bounded below by
one, we turn our attention to the spectral radius. Our first goal is to show
that the spectral radius of $B$ is strictly greater than 1 when $G$ is not a
cycle and has no dangling vertexs.

######  Proposition 5.5.

Let $G$ be a connected graph such that $G$ is not a tree or cycle and
$d_{\min}\geq 2$. Then $\rho(K)>1$.

###### Proof.

Let $B$ be the non-backtracking matrix. Note that $\rho(B)=\rho(K)$ and
$\rho(K)\geq 1$ since $\sigma(K)\subset\sigma(B)$ and $1\in\sigma(K)$. Assume
that $G$ is not $d$-regular. Since $B$ is nonnegative and irreducible by
Proposition 2.3 and $d_{\min}\geq 2$, then [14] tells us that
$\rho(B)>\min_{i}\sum_{j}b_{ij}\geq 1$. Assume that $G$ is $d$-regular. Since
$G$ is not a cycle, $d\geq 3$. Then by Theorem 2.2,

$\rho(B)=\frac{d+\sqrt{d^{2}-4(d-1)}}{2}\geq\frac{3+1}{2}=2>1.$

So $\rho(B)>1$. Since $\rho(B)=\rho(K)$, then $\rho(K)>1$. ∎

We now turn our attention to upper bounds on the spectrum of $B$. To do this,
we employ Proposition 5.3. Recall that the necessary condition for the
proposition was that $\mathbf{x}^{T}\mathbf{y}\neq 0$ for some eigenvalue-
eigenvector pairs $(\lambda,\mathbf{x})$ and
$(\mu,\begin{bmatrix}-\mu\mathbf{y}&\mathbf{y}\end{bmatrix}^{T})$ of $A$ and
$K$ respectively. To obtain this condition, we show that $\mathbf{y}$ is a
positive vector for the eigenvalue-eigenvector pair
$(\rho(K),\begin{bmatrix}-\rho(K)\mathbf{y}&\mathbf{y}\end{bmatrix}^{T})$.

######  Lemma 5.6.

Let $G$ be a connected graph such that $G$ is not a tree or cycle and
$d_{\min}\geq 2$. Then $y$ is positive for the eigenvector
$\begin{pmatrix}-\rho(K)\mathbf{y}&\mathbf{y}\end{pmatrix}^{T}$.

###### Proof.

Let
$K\begin{bmatrix}-\rho(K)\mathbf{y}&\mathbf{y}\end{bmatrix}^{T}=\rho(K)\begin{bmatrix}-\rho(K)\mathbf{y}&\mathbf{y}\end{bmatrix}^{T}$.
Now scale $\mathbf{y}$ such that there exists some $y_{k}>0$. By the Perron-
Frobenius Theorem and Theorem 4.2, $T^{T}\mathbf{y}\succ\rho(K)S\mathbf{y}$ or
$\rho(K)S\mathbf{y}\succ T^{T}\mathbf{y}$, where $S$ and $T$ are defined as in
equation 4. First assume that $T^{T}\mathbf{y}\succ\rho(K)S\mathbf{y}$. From
the definitions of $T$ and $S$, we get that $y_{i}\geq\rho(K)y_{j}$ for all
$i\sim j$. Choose $y_{k}>0$. Thus for all $i$ such that $i\sim k$,
$\frac{y_{i}}{y_{k}}\geq\rho(K)$. So $y_{i}\neq 0$ for all $i\sim k$ since
$\rho(K)>1$ by Proposition 5.5. Then by similar argument,
$\frac{y_{k}}{y_{i}}\geq\rho(K)$. This implies $\frac{y_{k}}{y_{i}}=1$ which
is a contradiction since $\rho(K)>1$.

Assume that $\rho(S)\mathbf{y}\succ T^{T}\mathbf{y}$. Again, choose $y_{k}>0$.
So for all $i$ such that $i\sim k$, $\rho(K)\frac{y_{i}}{y_{k}}>1$. Since
$\rho(K)>1$, then $y_{i}$ must be positive. Since $G$ is connected, by
induction we get that $y_{j}>0$ for all vertices $j$. Thus $y$ is positive. ∎

######  Theorem 5.7.

Let $G$ be a connected graph with $A$ the adjacency matrix and $B$ the non-
backtracking matrix. If $\rho(A)\geq 2\sqrt{\mathbf{x}^{T}(D-I)\mathbf{y}}$,
then

$\rho(B)\leq\frac{\rho(A)+\sqrt{\rho(A)^{2}-4(d_{\min}-1)}}{2}.$

###### Proof.

Let $G$ be a tree. Then $\rho(B)=0$ by Theorem 3.2 and
$\rho(B)\leq\frac{\rho(A)+\sqrt{\rho(A)^{2}-4(d_{\min}-1)}}{2}$.

Now assume that $G$ is a cycle. Then $\rho(B)=1$ by Theorem 3.4 and
$\frac{2+\sqrt{4-4}}{2}=1\geq\rho(B)$. Now assume that $G$ is a cycle with
dangling vertexs. By Corollary 3.2.1 $\rho(B)$ is the spectral radius of
$G\backslash S$ where $S$ is the set of dangling vertexs. Then by the work
above the result holds.

Assume that $G$ is not a tree or cycle and $d_{\min}\geq 2$. Note that
$\rho(B)\geq\rho(K)$. By the Perron-Frobenius theorem and Lemma 5.6,
$\mathbf{x}^{T}\mathbf{y}\neq 0$. Thus by Proposition 5.3,

$\rho(B)\leq\rho(K)=\frac{\rho(A)\pm\sqrt{\rho(A)^{2}-4\mathbf{x}^{T}(D-I)\mathbf{y}}}{2}\leq\frac{\rho(A)+\sqrt{\rho(A)^{2}-4(d_{\min}-1)}}{2}.$

Now assume that $G$ is not a tree or cycles and has at least one dangling
vertex. By Corollary 3.2.1 $\rho(B)$ is the spectral radius of $G\backslash S$
where $S$ is the set of all dangling vertexs. Then by the same argument as
above the result holds.

∎

There are many bounds shown for the spectral radius of the adjacency matrix of
a graph [6, 13, 18, 21]. Using a bound provided by Das and Kumar [6], we get a
simple bound on the spectral radius of $B$ dependent on the minimum degree
$d_{\min}$, number of vertexs $n$, and number of edges $m$.

######  Corollary 5.7.1.

Let $G$ be a connected graph with $A$ the adjacency matrix and $B$ the non-
backtracking matrix. If $\rho(A)\geq 2\sqrt{\mathbf{x}^{T}(D-I)\mathbf{y}}$,
then

$\rho(B)\leq\frac{\sqrt{2m-n-1}+\sqrt{2m-n-4d_{\min}+3}}{2}.$

###  5.1 Bipartite Graphs

A bipartite graph is a graph where all vertices can be divided into two
subsets, $V_{1}$ and $V_{2}$, where vertices in $V_{1}$ only connect to
vertices in $V_{2}$ and vice versa. It is widely known that the spectrum of
the adjacency matrix can determine the bipartiteness of a graph.

######  Theorem 5.8 ([4]).

Let $G$ be a graph and $A$ its associated adjacency matrix.

  1. (i)

$G$ is bipartite if and only if, for each eigenvalue $\lambda\in\sigma(A)$,
$-\lambda\in\sigma(A)$ with the same multiplicity.

  2. (ii)

If $G$ is connected and $\lambda_{1}$ is the largest eigenvalue of $A$, then
$G$ is bipartite if and only if $-\lambda_{1}$ is an eigenvalue of $A$.

The spectrum of the non-backtracking matrix $B$ also can indicate whether a
graph is bipartite in the same way. Additionally, the same properties hold for
the spectrum of $K$ when $G$ is bipartite.

######  Theorem 5.9.

Let $G$ be a connected graph, $B$ its associated non-backtracking matrix, and
$K$ defined as above. Then the following are equivalent:

  1. (i)

$G$ is a bipartite graph,

  2. (ii)

$\sigma(K)$ is symmetric,

  3. (iii)

$\sigma(B)$ is symmetric,

  4. (iv)

$\lambda_{n}=-\lambda_{1}$ where $\lambda_{i}\in\sigma(K)$, and

  5. (v)

$\mu_{n}=-\mu_{1}$ where $\mu_{i}\in\sigma(B)$,

  6. (vi)

$-1\in\sigma(K)$.

###### Proof.

_$(i)\rightarrow(ii)$_ : Assume that $G$ is bipartite. If $G$ is bipartite,
then the adjacency matrix $A$ can be written as $\begin{bmatrix}0&A_{2}\\\
A_{1}&0\end{bmatrix}$ (see [4]). We know that $A=TS$ by equation 6. Thus for a
bipartite graph, we define the following matrices:

$\displaystyle T_{1}\colon=\begin{cases}1&i_{1}\mapsto(i_{1},i_{2})\\\
0&\text{otherwise}\end{cases},$ $\displaystyle
T_{2}\colon=\begin{cases}1&i_{2}\mapsto(i_{2},i_{1})\\\
0&\text{otherwise}\end{cases},$ $\displaystyle
S_{1}\colon=\begin{cases}1&(i_{2},i_{1})\mapsto i_{1}\\\
0&\text{otherwise}\end{cases},$ $\displaystyle
S_{2}\colon=\begin{cases}1&(i_{1},i_{2})\mapsto i_{2}\\\
0&\text{otherwise}\end{cases}.$

In these matrices, $i_{j}$ represents a vertex in partition $j$ and
$(i_{j},i_{k})$ represents an edge from partition $j$ to partition $k$. Thus
by simple computation, we see that $A=\begin{bmatrix}0&T_{1}S_{2}\\\
T_{2}S_{1}&0\end{bmatrix}$ and the matrix $C=\begin{bmatrix}0&S_{2}T_{2}\\\
S_{1}T_{1}&0\end{bmatrix}$ where $C$ is defined as in equation 3. Hence, the
edges are also divided into two edge partitions.

In order to compute $B$, we also define a matrix

$\displaystyle\tau_{1}\colon=\begin{cases}1&(w,x)_{1}\mapsto(y,z)_{2}\\\
0&\text{otherwise}\end{cases}\text{ and }$
$\displaystyle\tau_{2}\colon=\begin{cases}1&(w,x)_{2}\mapsto(y,z)_{1}\\\
0&\text{otherwise}\end{cases},$

where $(w,x)_{j}$ represents an edge in edge partition $j$. We then see that
$\tau=\begin{bmatrix}0&\tau_{2}\\\ \tau_{1}&0\end{bmatrix}$. So the matrix
$B=\begin{bmatrix}0&S_{2}T_{2}-\tau_{2}\\\
S_{1}T_{1}-\tau_{1}&0\end{bmatrix}$. Defining $B_{j}=S_{j}T_{j}-\tau_{j}$, we
get that $B=\begin{bmatrix}0&B_{2}\\\ B_{1}&0\end{bmatrix}$.

Let $\begin{bmatrix}\mathbf{x}&\mathbf{y}\end{bmatrix}^{T}$ be an eigenvector
of $B$ with corresponding eigenvalue $\mu$. Then

$\displaystyle B\begin{bmatrix}\mathbf{x}&\mathbf{y}\end{bmatrix}^{T}$
$\displaystyle=\mu\begin{bmatrix}\mathbf{x}&\mathbf{y}\end{bmatrix}^{T}$
$\displaystyle\begin{bmatrix}B_{2}\mathbf{y}&B_{1}\mathbf{x}\end{bmatrix}^{T}$
$\displaystyle=\mu\begin{bmatrix}\mathbf{x}&\mathbf{y}\end{bmatrix}^{T}.$

Consider the vector $\begin{bmatrix}\mathbf{x}&-\mathbf{y}\end{bmatrix}^{T}$.
We see that

$\displaystyle B\begin{bmatrix}\mathbf{x}&-\mathbf{y}\end{bmatrix}^{T}$
$\displaystyle=\begin{bmatrix}-B_{2}\mathbf{y}&B_{1}\mathbf{x}\end{bmatrix}^{T}=\begin{bmatrix}-\mu\mathbf{x}&\mu\mathbf{y}\end{bmatrix}^{T}=-\mu\begin{bmatrix}\mathbf{x}&-\mathbf{y}\end{bmatrix}^{T}.$

So $-\mu$ is an eigenvalue of $B$ with eigenvector
$\begin{bmatrix}\mathbf{x}&-\mathbf{y}\end{bmatrix}^{T}$. Hence the spectrum
of $B$ is symmetric around 0.

_$(ii)\rightarrow(iii)$_ : Recall that $\sigma(B)=\sigma(K)\cup\\{\pm 1\\}$.
Since the set of $\pm 1$ is symmetric by Ihara’s theorem, $\sigma(K)$ is
symmetric.

_$(iii)\rightarrow(iv)$_ : Assume $\sigma(K)$ is symmetric. Then
$\lambda_{n}=-\lambda_{1}$ where $\lambda_{1}$ is the spectral radius of
$\sigma(K)$.

_$(iv)\rightarrow(v)$_ : If $G$ is a tree, then the result follows trivially
from Theorem 3.2.

If $G$ is not a tree then $\sigma(K)\subseteq\sigma(B)$. Since
$1\in\sigma(K)$, we know that $\rho(K)\geq 1$. Thus, $\rho(B)\geq 1$. If
$\rho(B)=1$, then the dominant eigenvalue of $B$ must be $\mu_{1}=\pm 1$. From
Ihara’s Theorem, $\pm 1\in\sigma(B)$.

If $\rho(B)\neq 1$, then $\mu_{1}\in\sigma(K)$ by Ihara’s Theorem and
$\mu_{1}=\lambda_{1}$. Thus, $\lambda_{n}=-\mu_{1}$. Then, we know that
$\mu_{n}=-\mu_{1}$.

_$(v)\rightarrow(i)$_ : If $G$ is tree or cycle, the result holds from
Theorems 3.2 and 3.4 respectively. Assume that $G$ is not a tree or cycle and
$\mu_{n}=-\mu_{1}$. Then $|\mu_{n}|=|\mu_{1}|$. By Proposition 2.3 tells us
$B$ is irreducible. Then from the Perron-Frobenius theorem, we know that the
period $d$ of $B$ must be at least 2. Further, since $\mu_{n}=-\mu_{1}$,
$d=2k$ for some $k\in\\{1,2,3,...\\}$. Then every cycle must be of even
length, so $B$ is the adjacency matrix of a directed bipartite graph. So
$B=\begin{bmatrix}0&B_{2}\\\ B_{1}&0\end{bmatrix}$, implying that
$A=\begin{bmatrix}0&A_{2}\\\ A_{1}&0\end{bmatrix}$. Hence $G$ is bipartite.

_$(iii)\rightarrow(vi)$ :_ Recall that $1\in\sigma(K)$ from Theorem 5.2(ii).
Since $\sigma(K)$ is symmetric, $-1\in\sigma(K)$.

_$(vi)\rightarrow(i)$ :_ Since $-1\in\sigma(K)$, we know that
$\begin{pmatrix}\mathbf{y}&\mathbf{y}\end{pmatrix}$ is the associated
eigenvector by Theorem 5.2(i). Thus, $A\mathbf{y}+(D-I)\mathbf{y}=-\mathbf{y}$
implying that $D^{-1}A\mathbf{y}=-\mathbf{y}$. So $-1\in\sigma(D^{-1}A)$. Note
that $D^{-1}A$ is the transition probability matrix of $G$ with spectral
radius 1. Thus, $G$ must be bipartite. ∎

######  Remark 9.

An alternate proof of Theorem 5.9(vi) can be derived directly as a corollary
of Proposition 4.15 of [22].

Recall in Theorem 3.2 we calculated $\sigma(B)$ when $G$ is a tree. Since
$\sigma(K)\supset\sigma(B)$ in the case of a tree, we can use the properties
of bipartite graphs to classify $\sigma(K)$ for trees as well.

######  Corollary 5.9.1.

Let $G$ be a tree. Let $K$ be defined as above. Then $1,-1,0\in\sigma(K)$. The
eigenvalue 0 has multiplicity at least $r$, where $r$ is the number of leaves
in $G$.

## References

  * [1] Noga Alon, Itai Benjamini, Eyal Lubetzky, and Sasha Sodin.  Non-backtracking random walks mix faster.  Communications in Contemporary Mathematics, 9(04):585–603, 2007\.
  * [2] Francesca Arrigo, Peter Grindrod, Desmond J Higham, and Vanni Noferini.  Non-backtracking walk centrality for directed networks.  Journal of Complex Networks, 6(1):54–78, 2018.
  * [3] Charles Bordenave, Marc Lelarge, and Laurent Massoulié.  Non-backtracking spectrum of random graphs: Community detection and non-regular ramanujan graphs.  In 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, pages 1347–1357, 2015.
  * [4] Andries E Brouwer and Willem H Haemers.  Spectra of graphs.  Springer Science & Business Media, 2011.
  * [5] Wei Chen, Ji Liu, Yongxin Chen, Sei Zhen Khong, Dan Wang, Tamer Başar, Li Qiu, and Karl H Johansson.  Characterizing the positive semidefiniteness of signed laplacians via effective resistances.  In 2016 IEEE 55th Conference on Decision and Control (CDC), pages 985–990. IEEE, 2016.
  * [6] Kinkar Ch Das and Pawan Kumar.  Some new bounds on the spectral radius of graphs.  Discrete Mathematics, 281(1-3):149–161, 2004.
  * [7] Roger A Horn and Charles R Johnson.  Matrix analysis.  Cambridge university press, 2012.
  * [8] Yasutaka Ihara.  On discrete subgroups of the two by two projective linear group over p-adic fields.  Journal of the Mathematical Society of Japan, 18(3):219–235, 1966\.
  * [9] Mark Kempton.  Non-backtracking random walks and a weighted ihara’s theorem.  Open Journal of Discrete Mathematics, 6:207–226, 2016.
  * [10] Motoko Kotani and Toshikazu Sunada.  2.-zeta functions of finite graphs.  Journal of Mathematical Sciences-University of Tokyo, 7(1):7–26, 2000.
  * [11] Florent Krzakala, Cristopher Moore, Elchanan Mossel, Joe Neeman, Allan Sly, Lenka Zdeborová, and Pan Zhang.  Spectral redemption in clustering sparse networks.  Proceedings of the National Academy of Sciences, 110(52):20935–20940, 2013.
  * [12] Yuan Lin and Zhongzhi Zhang.  Non-backtracking centrality based random walk on networks.  The Computer Journal, 62(1):63–80, 2019.
  * [13] Bolian Liu.  On an upper bound of the spectral radius of graphs.  Discrete mathematics, 308(23):5317–5324, 2008.
  * [14] Qingbing Liu, Guoliang Chen, and Linlin Zhao.  Some new bounds on the spectral radius of matrices.  Linear algebra and its applications, 432(4):936–948, 2010.
  * [15] Eyal Lubetzky and Yuval Peres.  Cutoff on all ramanujan graphs.  Geometric and Functional Analysis, 26(4):1190–1216, 2016.
  * [16] Eyal Lubetzky, Allan Sly, et al.  Cutoff phenomena for random walks on random regular graphs.  Duke Mathematical Journal, 153(3):475–510, 2010.
  * [17] Mark Newman.  Spectral community detection in sparse networks.  arXiv preprint arXiv:1308.6494, 2013.
  * [18] Vladimir Nikiforov.  Bounds on graph eigenvalues i.  Linear algebra and its applications, 420(2-3):667–671, 2007.
  * [19] Jingzhi Pan, Fei Jiang, and Jin Xu.  Influence maximization in social networks based on non-backtracking random walk.  In 2016 IEEE First International Conference on Data Science in Cyberspace (DSC), pages 260–267, 2016.
  * [20] Allen J Schwenk.  Almost all trees are cospectral.  New directions in the theory of graphs, pages 275–307, 1973.
  * [21] Zoran Stanić.  Inequalities for graph eigenvalues, volume 423.  Cambridge University Press, 2015.
  * [22] Leo Torres.  Non-backtracking spectrum: Unitary eigenvalues and diagonalizability.  arXiv preprint arXiv:2007.13611, 2020.