# Graph with complex eigenvalues

The question I am wondering about is:

Can the discrete Laplacian have complex eigenvalues on a graph?

Clearly, there are two cases where it is obvious that this is impossible.

1.) The graph is finite 2.) The underlying space is $$\ell^2$$, since then the discrete Laplacian is self-adjoint.

Thus, my question requires us to look at an infinite graph and a large space.

Hence: Does there exist an infinite graph such that the discrete Laplacian on $$\ell^{\infty}$$ has complex eigenvalues?

Thank you very much

BTW: My casual use of complex in the above text refers to $$\mathbb C \backslash \mathbb R$$

• you do not want to consider a directed graph, do you? – Carlo Beenakker Aug 22 at 9:59
• but a directed graph has complex eigenvalues, see for example www.4124039.com/q/74744/11260 – Carlo Beenakker Aug 22 at 10:51
• And as the link in Carlo's comment shows, there are indeed finite directed graphs with complex eigenvalues, so something is not right with your "clearly this is impossible for finite graphs". – M. Winter Aug 22 at 12:17
• @MartinHairer if $T$ is a shift operator on $l^\infty(\mathbb{Z})$, then its spectrum is the unit circle, thus Laplacian $T+T^{-1}-2$ has real eigenvalues, does not it? – Fedor Petrov Aug 22 at 13:45
• Oops... I had checked that an infinite binary tree works (see answer below) and then was too quick in thinking that the degenerate case of the unary tree' $\mathbb Z$ works for the same reason when of course it doesn't... – Martin Hairer Aug 22 at 15:51

Take the infinite binary tree $$T_2 = (V,E)$$, viewed as a bi-infinite backbone' $$B \approx \mathbb Z$$ with binary trees dangling off $$B$$. For every vertex $$v \in V$$ on the tree, there then is a closest element $$\pi(v) \in \mathbb Z$$ on the backbone and we write $$d(v)$$ for the distance from $$v$$ to $$\pi(v)$$. We then set $$A(v) = \exp(i\theta (\pi(v) + d(v)))$$ and check that $$\Delta A = \lambda A$$ with $$\lambda = 2 e^{i\theta} + e^{-i\theta} - 2$$.
If I understand the question correctly, you may have non-real eigenvalues even if the underlying space is $$\ell^2$$. It will be the case if the discrete laplacian is not essentially self-adjoint (or, in other words, its deficiency indices are non-zero): in this case every non-real number will be an eigenvalue. To construct such a graph one may take an infinite tree such that the branching number suitably exploses at infinity. For example, Proposition 1.2 in https://arxiv.org/abs/1005.0165 produces an explicit example in $$\ell^2$$ (and then in $$\ell^\infty$$ as well).