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.
Best Answer
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^-$.