# Hashimoto Matrix (Non-backtracking operator) and the Graph Laplacian

The question is: how can we recover the graph Laplacian or its spectrum from the Hashimoto Matrix (also commonly called the Non-backtracking operator)?

To make the question as self-contained as possible, here I give the main definitions:

Let $W$ be a given symmetric adjacency matrix of graph $G = (V,E)$.

Let $D$ be a diagonal matrix such that $D_{ii} = d_i$, where $d_i$ is the degree of vertex $i$, i.e. $d_i = \sum_i^n w_{ij}$

Then,

• The Laplacian matrix $L$ is defined as $$L=D-W$$

• The Hashimoto matrix $B$ is defined as $$B_{(i \rightarrow j), (k \rightarrow l)} = \begin{cases} 1 & j=k \text{ and } i\neq l \\ 0 & \text{ otherwise } \end{cases}$$ Observation: See that the Hashimoto Matrix is a kind of directed linear graph of $G$.

Is there an operator such that we can recover $L$ from $B$, i.e. an operator $\mathcal{M}$ such that $\mathcal{M}(B) = L$?

Is there any relation between the spectrum of $B$ and $L$?

Answers with references are highly appreciated.

• You should give ample time on math.stackexchange before posting here - days, not hours. – Chris Godsil Oct 1 '15 at 21:28

It is convenient to use another representation of the Laplacian, namely $$L={\mathcal I}{\mathcal I}^T$$ where $\mathcal I$ is the signed incidence matrix of any orientation of the graph. Now, you may want to take the positive and negative part of $\mathcal I$, thus obtaining $\mathcal I^+$ and ${\mathcal I}^-$ and $\mathcal I=\mathcal I^+-\mathcal I^-$. If you do some computations, you will find that your Hashimoto Matrix is just $({\mathcal I}^+)^T\mathcal I^-$.
Concerning your second question: Of course the spectrum of $\mathcal I^T \mathcal I$ agrees with that of $L=\mathcal I\mathcal I^T$ (possibly up to the 0), but in general I see no reason why the spectrum of $\mathcal I^T \mathcal I= (\mathcal I^+)^T \mathcal I^- + (\mathcal I^-)^T \mathcal I^- + (\mathcal I^+)^T \mathcal I^+ + (\mathcal I^-)^T \mathcal I^+$ should bear any resemblance to that of its first addend $(\mathcal I^+)^T \mathcal I^-$.
In this paper, we talk about some properties the Hashimoto spectrum determines. Since it determines the Ihara zeta function, it at least determines some mild things about the signed Laplacian $|L|$, e.g., the product of the eigenvalues of $|L|$. See Sec 2.1.