Digraph Laplacian spectra: Counterexamples to the 2005 polygon conjecture

Let ${\mathrm{\Lambda }}_n$ be the set of all eigenvalues of standardized Laplacian matrices of order $n$. In 2005, a polygon $S_n\subseteq {\mathrm{\Lambda }}_n$ was constructed, and it was conjectured that ${\mathrm{\Lambda }}_n=S_n$. We observe that $S_n$ is a zonotope, which gives a short proof of $S_n\subseteq {\mathrm{\Lambda }}_n$, and we describe ${\mathrm{\Lambda }}_n$ as a union, over all vectors $v$, of intersections of zonotopes $Z_i(v)$ built from the ratios $v_j\mathrm{/}{v}_i$. For a vector whose components are the $n$ distinct $n$th roots of unity, every $Z_i(v)$ equals $S_n$. We then show that the conjecture is false for $n=7$: the directed $6$-cycle with one vertex duplicated has an eigenvalue lying $2.1\cdot {10}^{-4}$ beyond one edge of $S_7$. For the analogous digraph of order $n$, the corresponding eigenvalue lies at signed distance ${\delta }_n\sim \frac{{\pi }^2}{2n^4}$ beyond the supporting line of the analogous edge of $S_n$, so the construction yields counterexamples for all sufficiently large $n$; numerically, it does so for every $7\le n\le 300$. We also prove that $S_m\subseteq S_n$ whenever $m\mid n$, with $S_m\setminus \{0,1\}$ lying in the interior of $S_n$ for $n\ge 3m$.