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}$


  • 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.

  • $\begingroup$ You should give ample time on math.stackexchange before posting here - days, not hours. $\endgroup$ Oct 1, 2015 at 21:28

3 Answers 3


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


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

One can say some things, but it follows from computations on small graphs that one spectrum does not determine the other. For instance, compare Tables 2.1 and 5.1 in my paper with C. Durfee. The T column in the first table counts graphs of order n not determined by their Hashimoto spectrum, and the L column in the latter table does the same for the Laplacian.

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.


The Hashimoto matrix is the nonsymmetric 0/1 part of the matrix in the last line above -- the symmetric 0/1 part of they same matrix contains the backtracking walks.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.