7
$\begingroup$

Suppose there is a finite undirected graph $G(V,E)$ having $n$ vertices and $m$ edges. The non-backtracking matrix $B$ is indexed by $2m$ directed edges and defined as $$ B(a \to b, c \to d) = \delta_{bc} (1 - \delta_{ad}) \, . $$ The adjacency matrix $A$ is defined as usual.

I learned that the Ihara–Bass formula was established in the context of graph zeta functions. At present I only make sense of an elementary proof without diving into graph zeta functions. By this proof, I learned that if $u^2 \neq 1$ then $$ \det(I-uB) = \left(1-u^2\right)^{m-n} \det\left(I - u A + u^2\left[D-I\right]\right) \, , $$ where $D$ is the degree matrix.

As a corollary, all roots of the polynomial $\det(B - \lambda I)$, except those being $\pm 1$, are roots of the polynomial $\det\left(\lambda^2 I - \lambda A + \left[D-I\right]\right)$.

For all simple graphs, we have $ \det(D - A) = 0 $. But for trees, the non-backtracking matrix has no eigenvalues other than $0$, which leads to $ \det(I - B) = \det(I) = 1 $. Thus the polynomial $\det\left(\lambda^2 I - \lambda A + \left[D-I\right]\right)$ can not be used to search the eigenvalues of $B$ being $1$.


Can the corollary be extended to search the eigenvalues of $B$ being $\pm 1$?

The motivation behind this question is to get the whole spectrum of the non-backtracking matrix of a graph with a much smaller matrix.

$\endgroup$
0

1 Answer 1

1
$\begingroup$

(I don't have enough reputation to comment).

There are generalizations of Ihara-Bass result for adjacency matrix $A$ with $A_{ij}$ being some real number(see this paper, p. 13 and further). But even there $u$ should not be equal to $|1/x|$, where $x$ is an entry of the adjacency matrix.

Although it is not an answer, it seems there should be this restriction

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .