# Nodal count for graphs with disjoint cycles

Lior Alon  Massachusetts Institute of Technology, Cambridge MA  ,  Ram Band
Israel Institute of Technology (Technion), Haifa, Israel  ,  Gregory
Berkolaiko  Texas A&M University, College Station TX  and  Mark Goresky
Institute for Advanced Study, Princeton N.J.

###### Abstract.

Let $G$ be a simple, connected graph on $n$ verticesand let , and further
assume that $G$ has disjoint cycles (see §3). Let $h$ be a real symmetric
$n\times n$ matrix whose off-diagonal elements $h_{ij}$ are supported on the
edges $(ij)$ of matrix supported on $G$. , and further assume that $h$
satisfies a certain generic condition (cf. §1.2). The eigenvalues of $h$ are
ordered increasingly, $\lambda_{1}\leq\cdots\leq\lambda_{n}$. If , and if
$\phi$ is the eigenvector of $h$ corresponding to $\lambda_{k}$, the nodal
(edge) count $\nu(h,k)$ is the number of edges $(rs)$ such that
$\phi(r)h_{rs}\phi(s)>0$$h_{rs}\phi_{r}\phi_{s}>0$. The nodal surplus is
$\sigma(h,k)=\nu(h,k)-(k-1)$. The signings of $h$ are the real symmetric
matrices obtained from $h$ by changing the sign of some of its off-diagonal
elements, and their nodal surplus is defined similarly. In this paper, we show
that if $G$ has disjoint cycles (see §3) and $h$ is generic in a specific
sense (cf. §1.2) then for each $k$, We show that the distribution of values of
the nodal surplus $\sigma(h^{\prime},k)$ is binomial, as $h^{\prime}$ varies
over the signings of $h$. Part of the proof follows ideas developed by the
first author together with Ram Band and Gregory Berkolaiko in a joint
unpublished project studying a similar question on quantum graphs.

###### Key words and phrases:

spectral graph theory, nodal count, Morse theory

###### 1991 Mathematics Subject Classification:

05C22, 05C50, 47A10, 57R70, 58K05, 49J52, 57Z05

##  1\. Introduction

### 1.1.

Let $G=G([n],E)$ be a simple graph on $n$ ordered vertices
$[n]:=\\{1,2,\ldots,n\\}$ with a set of edges $E$. Write $r\sim s$ if the
vertices $r\neq s$ are connected by an edge $(rs)\in E$. An $n\times n$ matrix
$h$ is supported (resp. strictly supported) on $G$ if for any $r\neq s$,
$h_{rs}\neq 0\implies r\sim s$ (resp. $h_{rs}\neq 0\iff r\sim s$ for $r\neq
s$). Let $\mathcal{S}(G)$ (resp. $\mathcal{H}(G)$) denote the vector space of
real symmetric (resp. Hermitian) matrices supported on $G$. The eigenvalues of
such a symmetric matrix $h\in\mathcal{S}(G)$ are real and ordered,
$\lambda_{1}(h)\leq\lambda_{2}(h)\leq\cdots\leq\lambda_{n}(h)$. We say that
$\phi\in\mathbb{R}^{n}$ is _nowhere-vanishing_ if $\phi_{j}\neq 0$ for all
$j$. If $\phi$ is a nowhere-vanishing eigenvector of $h$, with simple
eigenvalue $\lambda_{k}$, then its nodal (edge) count $\nu(h,k)$ is defined to
be the number of edges $r\sim s$ such that is

${\color[rgb]{0,0,1}\uwave{\nu(h,k)=}}\left|{\color[rgb]{0,0,1}\uwave{\\{(rs)\in
E\ :\
}}\phi_{r}h_{rs}\phi_{s}>{\color[rgb]{1,0,0}\sout{0.}}{\color[rgb]{0,0,1}\uwave{0\\}}}\right|{\color[rgb]{0,0,1}\uwave{.}}$

(If $h_{rs}<0$, as in the case of the graph Laplacian or more generally, a
discrete Schrödinger operator, the nodal (edge) count is the number of edges
on which $\phi$ changes sign.) If the graph $G$ is a tree, the nodal count is
exactly $\nu(h,k)=k-1$ [9], however, this is not the case if $G$ is not a tree
[4]. Consequently the nodal surplus for the $k$-th eigenvalue of a $h$ is
defined to be

$\sigma(h,k):=\nu(h,k)-(k-1),$

and it was proven to be non-negative and bounded by
$\beta=|E|-n+1={\mathrm{rank}}(H_{1}(G))$, the first Betti number of $G$

$0\leq\sigma(h,k)\leq\beta.$

A signing of $h\in\mathcal{S}(G)$ is a symmetric matrix $h^{\prime}$ obtained
from $h$ by changing the sign of some of its off-diagonal elements. A
fundamental problem in graph theory is to determine the distribution of nodal
counts, or nodal surplus for the eigenvalue $\lambda_{k}(h^{\prime})$, as
$h^{\prime}$ varies over all signings of $h$.

For a further introduction to these ideas, we refer the reader to [3].

Following numerical simulations and the quantum graph analog [2], it was
conjectured in [3] that generically, as $\beta\to\infty$ the distribution of
the nodal surplus is expected to obey a universal law, converging to a
Gaussian centered at $\beta/2$ with variance of order $\beta$. It was shown to
hold for complete graphs with matrices that have a dominant diagonal.

### 1.2.

In this paper, we consider a somewhat opposite case, _graphs with disjoint
cycles_. A cycle is a path along the graph starting and ending at the same
vertex, and it is simple if no other vertex is repeated. We say that $G$ has
_disjoint cycles_ if distinct simple cycles do not share any vertex. See §3
and Figure 1.

Figure 1. A graph with disjoint cycles

If $\phi\in\mathbb{R}^{n}$ is an eigenvector of $h\in\mathcal{S}(G)$ in order
to avoid double subscripts we sometimes write $\phi(r)=\phi_{r}$. In this
paper we will often be concerned with real symmetric matrices To define the
nodal count for all signing of $h\in\mathcal{S}(G)$that are , the matrix $h$
need to satisfy the following genericin the following sense , condition:

  1. (*NCC)

The matrix We say $h\in\mathcal{S}(G)$ satisfies the nodal count condition,
abbreviated NCC, if $h$ is strictly supported on $G$, and every eigenvalue of
every signing of $h$ is simple , and the corresponding eigenvector $\phi$ is
nowhere vanishing , that is, $\phi(r)\neq 0$ for all vertices $r$. with
nowhere vanishing eigenvector,

The genericity of (*) is established in Lemma 6.1 In Lemma 6.1 we establish
that a generic matrix in $\mathcal{S}(G)$ satisfies (NCC). The main result of
this paper is the following:

######  Theorem 1.3.

Let $G$ be a simple connected graph with $n$ vertices and disjoint cycles. Let
, and let $h\in\mathcal{S}(G)$ be generic in the sense of (*). For that
satisfy (NCC). Then for any $k$ $(1\leq k\leq n)$ the nodal surplus
distribution of $\lambda_{k}(h^{\prime})$ is binomial, as $h^{\prime}$ varies
over the signings of $h$: the fraction of those signings $h^{\prime}$ such
that $\sigma(k,h^{\prime})=j$ is $2^{-\beta}\binom{\beta}{j}$.

Consequently, as $\beta\to\infty$, this distribution converges to a Gaussian
centered at $\beta/2$ with variance $\beta/4$.

Our theorem was inspired by a related result ([1, Theorem 2.3]) for quantum
graphs with disjoint cycles and $\mathbb{Q}$-linearly independent edge
lengths, where it was shown that the distribution of the nodal surplus for the
first $N$ eigenfunctions eigenvectors converges to a binomial distribution as
$N\to\infty$ (A quantum graph has countably many eigenvalues). However, our
case is different. We consider a fixed value of $k$ (the $k$-th eigenvalue)
and the nodal count distribution over different signings of our operator
(matrix). For example, $\beta$ may be much greater than the term $k-1$ in the
nodal count. (For quantum graphs, on the other hand, $k$ grows to infinity
while $\beta$ is fixed, so the term $k-1$ nodal surplus is a small
perturbation of the linearly growing nodal count.)

### 1.4.

Given a graph $G$ with a matrix $h$ as above, the various signings of $h$ lie
in a single torus111defined (in [5]) by allowing off-diagonal elements
$h_{rs}$ to vary by a phase $e^{i\theta_{rs}}h_{rs}$
$\mathbb{T}_{h}\subset\mathcal{H}(G)$, see equation (1). We may consider the
eigenvalue $\lambda_{k}$ to be a sort of Morse function on $\mathbb{T}_{h}$.
It is a theorem of Berkolaiko [5], further explained by Colin de Verdière [8]
that each signing $h^{\prime}\in\mathbb{T}_{h}$ is a critical point of
$\lambda_{k}$, whose Morse index coincides with the nodal surplus for
$h^{\prime}$. Unfortunately due to the existence of a group of gauge
transformations that acts on $\mathbb{T}_{h}$ and preserves $\lambda_{k}$,
each critical point $h^{\prime}$ is highly degenerate.

The degeneracy in the critical points can be removed by dividing the torus
$\mathbb{T}_{h}$ by the gauge group. The result is a torus $\mathcal{M}_{h}$
whose dimension

$\beta=|E|-n+1={\mathrm{rank}}(H_{1}(G))$

is the first Betti number of $G$. The genericity condition (*NCC) now implies
([3, Thm 3.2]) that for each signing $h^{\prime}$ of $h$ the corresponding
point $[h^{\prime}]\in\mathcal{M}_{h}$ is a nondegenerate critical point of
$\lambda_{k}:\mathcal{M}_{h}\to\mathbb{R}$. One might hope, especially in the
case of a graph with disjoint cycles, that these are the only critical points
of $\lambda_{k}$. If this was the case then we would conclude that
$\lambda_{k}$ is a perfect Morse function, that each critical point
contributes to the homology of $\mathcal{M}_{h}$ in a single degree and hence
the nodal surplus is binomially distributed. A similar situation occurs in [3,
Theorem 3.2 and §3.4 ], where it was proven that the nodal surplus
distribution is binomial when $G$ is a complete graph and $h$ has a dominant
diagonal. It is likely true, for generic graphs with disjoint cycles, that
each $\lambda_{k}$ is a perfect Morse function on $\mathbb{T}_{h}$, but we do
not prove it.

### 1.5.

Instead, we develop a different approach using the combinatorics of the
Boolean lattice (§3.7) and two technical steps: (a) the monotonicity lemma
(Lemma LABEL:lem:_monotonicity5.1), and (b) the local-global theorem (Theorem
7.3). These results allow us to focus on the one dimensional trajectories that
connect neighboring signings $h^{\prime}$ and ${h^{\prime\prime}}$ as
described in Propositions 3.5 and 3.6. The proof is then outlined in §3.7.

### 1.6.

An important ingredient in the proof is the probability current
$\mathbb{J}(h,\phi)$ (Definition 4.1), a real anti-symmetric matrix supported
on $G$, which may be interpreted as a gauge invariant divergence-free vector
field or as a harmonic 1-form. It is defined for every graph any
$h\in\mathcal{H}(G)$ and every eigenvector of $h$ and has a special structure.
It vanishes on every bridge and is constant on the edges of each simple
separated cycle. If the eigenvalue $\lambda$ is simple then $-2\mathbb{J}$ is
the derivative of $\lambda$, cf. Proposition 4.2.

###  1.7. Acknowledgements

The authors are grateful to R. Band and G. Berkolaiko for their encouragement.
Part of the proof follows ideas developed by the first author together with
Band and Berkolaiko in a joint unpublished project studying a similar question
on quantum graphs. We are particularly grateful to G. Berkolaiko for his
meticulous reading of an earlier version of this manuscript and for his many
useful comments and suggestions. We would also like to thank Cynthia Vinzant
for useful conversations.

##  2\. Recollections on graphs

### 2.1.

As in §1 we consider a simple connected graph $G$ on $n$ ordered vertices
numbered $1,2,\cdots,n$. We write
$\mathcal{H}_{n},\mathcal{S}_{n},\mathcal{A}_{n}$ for the Hermitian, real
symmetric, and real antisymmetric $n\times n$ matrices, and we write
$\mathcal{H}(G)$, $\mathcal{S}(G)$, $\mathcal{A}(G)$ for those matrices
supported on $G$. If $(rs)$ is an edge in $G$ write $E[rs]$ for the matrix
that is zero except for $E[rs]_{rs}=1$ and let $A[rs]=E[rs]-E[sr]$ be the
corresponding antisymmetric matrix.

### 2.2.

Each edge $(rs)$ of $G$ has a natural orientation ($+$ or $-$) which is the
sign of $s-r$. The space $C_{1}(G;\mathbb{R})$ of 1-chains consists of finite
linear combinations of oriented edges

$\gamma=\sum_{\begin{subarray}{c}{r\sim s}\\\
{r<s}\end{subarray}}\gamma_{rs}(rs)\ \text{ with }\ \gamma_{rs}\in\mathbb{R}.$

The space $C_{0}(G,\mathbb{R})$ of 0-chains consists of formal finite linear
combinations $\sum_{r=1}^{n}a_{r}(r)$ of vertices with $\partial:C_{1}(G)\to
C_{0}(G)$ defined by $\partial(rs)=(s)-(r)$. We may consider $\mathcal{A}(G)$
to be the space of 1-forms $\Omega^{1}(G;\mathbb{R})$, dual to $C_{1}(G)$ with
respect to the bilinear pairing

$\int_{\gamma}\alpha:=\sum_{\begin{subarray}{c}{r\sim s}\\\
{r<s}\end{subarray}}\gamma_{rs}\alpha_{rs}$

where $\gamma\in C_{1}(G;\mathbb{R})$ and $\alpha\in\mathcal{A}(G)$.

The space of real valued functions defined on the vertices of $G$ is denoted
$\Omega^{0}(G,\mathbb{R})\cong\mathbb{R}^{n}$. The differential
$d:\Omega^{0}(G)\to\Omega^{1}(G)$ is

$(d\theta)_{rs}=\begin{cases}\theta(s)-\theta(r)&\text{if }r\sim s\\\
0&\text{otherwise}\end{cases}$

Its adjoint with respect to the natural inner products222given by
$\langle\theta,\theta^{\prime}\rangle=\sum_{r}\theta_{r}\theta^{\prime}_{r}$
and
$\langle\alpha,\alpha^{\prime}\rangle=\sum_{r<s}\alpha_{rs}\alpha^{\prime}_{rs}$
for $\theta\in\Omega^{0}$ and $\alpha\in\Omega^{1}$ on $\Omega^{0}(G)$ and
$\Omega^{1}(G)$ is

$(d^{*}\alpha)_{r}=\sum_{s}\alpha_{rs}.$

### 2.3.

Stokes’ theorem $\int_{\gamma}d\theta=\int_{\partial\gamma}\theta$ implies
that the integration pairing passes to a nonsingular dual pairing between the
cohomology $H^{1}(G,\mathbb{R})=\ker(d)$ and the homology
$H_{1}(G,\mathbb{R})=\text{coker}(\partial)$. Consequently, given
$\alpha\in\mathcal{A}(G)$, there exists $\theta\in\Omega^{0}(G,\mathbb{R})$
such that $\alpha=d\theta$ if and only if $\int_{\gamma}\alpha=0$ for every
cycle $\gamma$. ∎

###  2.4. Action of $\mathcal{A}(G)$

The space $\mathcal{A}_{n}(\mathbb{R})$ of real $n\times n$ antisymmetric
matrices acts on the space $\mathcal{H}_{n}$ by

$(\alpha*h)_{rs}=e^{i\alpha_{rs}h_{rs}}$

with $\alpha^{\prime}*\alpha*h=(\alpha^{\prime}+\alpha)*h$. Let
$\mathcal{A}_{n}(2\pi\mathbb{Z})$ be the set of antisymmetric matrices whose
entries are integer multiples of $2\pi$. The action factors through the torus
$\mathcal{A}_{n}(\mathbb{R})/\mathcal{A}_{n}(2\pi\mathbb{Z})$ so that

$\mathbb{T}(G)=\left\\{\alpha\in\mathcal{A}_{n}(\mathbb{R})/\mathcal{A}_{n}(2\pi\mathbb{Z}):\alpha_{rs}\neq
0\implies r\sim s\right\\}$

acts on $\mathcal{H}(G)$. The mapping

$*:\mathbb{T}(G)\times\mathcal{S}(G)\to\mathcal{H}(G)$

is a finite surjective covering. For each $h\in\mathcal{S}(G)$ the orbit

(1) $\mathbb{T}_{h}=\mathbb{T}(G)*h$

is a torus of perturbations333referred to in [5] as the torus of “magnetic
perturbations of $h$” because, for the Schrödinger operator, these
perturbations arise from the introduction of a magnetic field, cf, [3]. of
$h$. The torus $\mathbb{T}_{h}$ is preserved under complex conjugation and the
fixed points are the intersection $\mathbb{T}_{h}\cap\mathcal{S}(G)$, which
consists of the signings of $h$.

###  2.5. Gauge equivalence

If
$\theta=(\theta_{1},\theta_{2},\cdots,\theta_{n})\in\Omega^{0}(G,\mathbb{R})\cong\mathbb{R}^{n}$
and $h\in\mathcal{H}(G)$ then

$d\theta*h=e^{i\theta}he^{-i\theta}$

is conjugate to $h$, where
$e^{i\theta}=\text{diag}(e^{i\theta_{1}},e^{i\theta_{2}},\cdots,e^{i\theta_{n}})$.
Therefore $\lambda_{k}(d\theta*h)=\lambda_{k}(h)$. If
$V_{\lambda}(h)=\ker(h-\lambda I)$ then

(2) $V_{\lambda}(d\theta*h)=e^{i\theta}V_{\lambda}(h).$

We say the elements $h$ and $h^{\prime}=d\theta*h$ are gauge equivalent and
differ by the gauge transformation $d\theta$. Geometrically, equation (2) says
that eigenvectors $\phi,\phi^{\prime}$ of $h$ and $h^{\prime}$ differ by
changing the phases, $\phi^{\prime}_{r}=e^{i\theta_{r}}\phi_{r}$. Since their
eigenvalues $\lambda_{k},\lambda^{\prime}_{k}$ are equal it makes sense to
restrict attention to gauge-equivalence classes of matrices.

We may formally define the gauge group
$\mathcal{G}=(\mathbb{R}/2\pi\mathbb{Z})^{n}$ with action $\theta\diamond
h=d\theta*h$, whose orbits are gauge equivalence classes. The quotient of
$\mathbb{T}_{h}$ under gauge equivalence is an abstract torus
$\mathcal{M}_{h}=\mathbb{T}_{h}\mathbin{/\mkern-6.0mu/}\mathcal{G}$, of
dimension $\beta$, the manifold of magnetic perturbations modulo gauge
transformations. We sometimes write $[h]\in\mathcal{M}_{h}$ for the gauge-
equivalence class of $h$.

Equation (2) reflects an action of the gauge group on vectors
$\phi\in\mathbb{C}^{n}$ with $\theta\diamond\phi=e^{i\theta}\phi$.

##  3\. Disjoint cycles

### 3.1.

We say a graph $G$ has disjoint cycles if distinct simple cycles do not share
a vertex, cf. §1.2. Thus, each edge in $G$ is a bridge unless it is contained
in a simple cycle. Throughout this section we fix a graph $G$ with disjoint
cycles and a matrix $h\in\mathcal{S}(G)$. We also fix
$k\in[n]=\\{1,2,\cdots,n\\}$ and consider the eigenvalue function
$\lambda_{k}$.

### 3.2.

Fix a spanning tree in $G$. Its complement consists of a single edge in each
simple cycle. The elements $\alpha\in\mathbb{T}(G)$ that are supported on
these edges form a torus $\mathbb{T}^{\beta}$ that projects isomorphically to
the quotient torus $\mathcal{M}_{h}$. In other words, every element
$\alpha*h\in\mathbb{T}_{h}$ is gauge equivalent to some $\alpha^{\prime}*h$
where $\alpha^{\prime}$ is supported on these chosen edges. Thus,
$\mathbb{T}^{\beta}$ is a “lift” to $\mathbb{T}(G)$ of the manifold
$\mathcal{M}_{h}$, as in the following diagram. The composition across the top
row is denoted $\Lambda_{k}:\mathbb{T}^{\beta}\to\mathbb{R}$.

(3) $\begin{diagram}$

###  3.3. Combinatorics of $\mathbb{T}^{\beta}$

Choose an ordering of the edges identified in §3.2 (with one edge in each
simple cycle). This gives a particular choice of identification

(4) $\begin{diagram}$

Let $e_{1},e_{2},\cdots,e_{\beta}\in\mathbb{T}^{\beta}$ denote the image in
$\mathbb{R}^{\beta}/(2\pi\mathbb{Z})^{\beta}$ of the standard basis444each
$e_{j}=A[r_{j}s_{j}]=E[r_{j}s_{j}]-E[s_{j}r_{j}]$ is in fact a matrix in
$\mathcal{A}(G)$ defined modulo $2\pi$, and corresponds to one of the
particular edges identified in §3.2.  vectors. Points
$\epsilon=\sum_{i=1}^{\beta}\epsilon_{i}e_{i}\in\mathbb{T}^{\beta}$ with
coordinates $\epsilon_{i}\in\left\\{0,\pi\right\\}$ are called symmetry
points. By abuse of notation we write
$\epsilon\in\left\\{0,\pi\right\\}^{\beta}$. The corresponding matrices
$h_{\epsilon}=\epsilon*h$ are the signings of $h$ modulo gauge equivalence.

There are $2^{\beta}$ symmetry points in $\mathbb{T}^{\beta}$. They form the
vertices of a (hyper-)cube

$\square\subset\mathcal{M}_{h}$

whose $1$-skeleton consists of edges that connect a symmetry point $\epsilon$
to a neighbor $\epsilon+\pi e_{j}\ (\mathop{\rm mod}2\pi)$ (where
$j\in[\beta]$). A choice of eigenvalue $\lambda_{k}$ determines a partial
ordering on the symmetry points,

$\epsilon\succeq\epsilon^{\prime}\ \iff\
\lambda_{k}(\epsilon*h)\geq\lambda_{k}(\epsilon^{\prime}*h).$

For $\epsilon\in\left\\{0,\pi\right\\}^{\beta}\subset\mathbb{T}^{\beta}$ let

(5) $J_{-}(\epsilon)=J_{-}(\epsilon,k,h)=\left\\{j\in[\beta]:\
\lambda_{k}((\epsilon+\pi
e_{j})*h)<\lambda_{k}\left(\epsilon*h\right)\right\\}.$

The set $J_{-}(\epsilon)$ identifies those neighbors $\epsilon+\pi e_{j}$ of
$\epsilon$ in the 1-skeleton for which the eigenvalue
$\lambda_{k}(h_{\epsilon})$ decreases.

### 3.4.

Although the proof of our main result (Theorem 1.3) has many technical steps
the ideas are relatively simple, requiring only the following two propositions
whose proofs appear in §7. Let $G$ be a simple connected graph with disjoint
cycles and suppose $h\in\mathcal{S}(G)$ is generic in the sense of (*satisfies
(NCC). Fix $k\in[n]$ and recall the notation
$\Lambda_{k}(\alpha)=\lambda_{k}(\alpha*h)$ for $\alpha\in\mathbb{T}^{\beta}$.

######  Proposition 3.5.

Each $\epsilon\in\left\\{0,\pi\right\\}^{\beta}$ is a nondegenerate critical
point of the function $\Lambda_{k}:\mathbb{T}^{\beta}\to\mathbb{R}$ and its
Morse index is $\text{ind}(\Lambda_{k})(\epsilon)=|J_{-}(\epsilon)|$. The
Hessian of the function $\Lambda_{k}$ is diagonal with respect to the
decomposition (4).

######  Proposition 3.6.

The mapping $\left\\{0,\pi\right\\}^{\beta}\to\mathcal{P}{[\beta]}$ (the set
of subsets of $[\beta]$), given by $\epsilon\mapsto J_{-}(\epsilon)$ is
bijective. This implies that $\left\\{0,\pi\right\\}^{\beta}$ becomes a
Boolean lattice555The Boolean lattice on a finite set $S$ is the partially
ordered set $\mathcal{P}(S)$ of subsets of $S$ ordered by inclusion. under the
above partial order.

###  3.7. Proof of Theorem 1.3

First we consider the nodal distribution of $\Lambda_{k}(\epsilon)$ as
$\epsilon$ varies in $\\{0,\pi\\}^{\beta}\subset\mathbb{T}^{\beta}$. By [5, 8,
3] the function $\Lambda_{k}$ has a nondegenerate critical point at each
$\epsilon\in\left\\{0,\pi\right\\}^{\beta}$ and its Morse index equals the
nodal surplus $\sigma(h,k)$ at that point. By Proposition 3.5, this means that
the nodal surplus distribution coincides with the distribution of the numbers
$|J_{-}(\epsilon)|$. Proposition 3.6 implies that the distribution of the
numbers $|J_{-}(\epsilon)|$, and hence also the nodal surplus distribution for
$\lambda_{k}$, is binomial as $\epsilon$ varies in
$\left\\{0,\pi\right\\}^{\beta}$.

Next we consider the set of signings of $h$. The set
$\left\\{0,\pi\right\\}^{\beta}*h$ is the quotient of the set of signings of
$h$ by the action of the gauge group, or more accurately, the action by a
certain subgroup of the gauge group. If
$\theta=(\epsilon_{1},\epsilon_{2},\cdots,\epsilon_{n})\in\Omega^{0}(G;\mathbb{R})$
with $\epsilon_{i}\in\\{0,\pi\\}$ and if $h^{\prime}\in\mathcal{A}(G)$ is a
signing of $h$ then $d\theta*h^{\prime}$ is another signing. The set of such
$\theta$ form a group under addition modulo $2\pi$. If $h$ is properly
supported on $G$ then this defines a free action of $(\mathbb{Z}/(2))^{n}$ on
the set of signings (cf. [3, §2.6, §2.7]). Each symmetry point
$\epsilon\in\left\\{0,\pi\right\\}^{\beta}\subset\mathbb{T}^{\beta}$
corresponds to exactly the same number, $2^{n-\beta}$ of signings. Therefore
the binomial distribution on $\left\\{0,\pi\right\\}^{\beta}$ becomes the same
binomial distribution on the set of signings. ∎

##  4\. CriticalityProbability current and criticality

### 4.1.

Throughout this section we fix a simple connected graph $G$ with $n$ vertices
and $h\in\mathcal{S(G)}$ strictly supported on $G$.

######  Definition 4.1.

Given any complex hermitian $h\in\mathcal{H}(G)$ and an eigenvector $\phi$ of
$h$, we define the probability current
${\mathbb{J}}={\mathbb{J}}(h_{\alpha},\phi)\in\mathcal{A}(G)=\Omega^{1}(G,\mathbb{R})$
by

${\color[rgb]{0,0,1}\uwave{{\mathbb{J}}_{rs}=\Im\left(h_{rs}\bar{\phi}_{r}\phi_{s}\right).}}$

We say that the eigenvector $\phi$ satisfies the criticality condition at an
edge $(rs)$ if ${\mathbb{J}}_{rs}=0$.

We remark that the probability current is defined for any eigenvector whether
or not the eigenvalue is simple. The probability current has the following
properties.

######  Proposition 4.2.

Given any complex hermitian $h_{\alpha}\in\mathcal{H}(g)$, let
${\mathbb{J}}={\mathbb{J}}(h_{\alpha},\phi)$ be the probability current of
some normalized eigenvector $\phi$. Then

  1. (1)

${\mathbb{J}}$ is gauge-invariant, namely
${\mathbb{J}}(d\theta*h_{\alpha},e^{i\theta}\phi)={\mathbb{J}}(h_{\alpha},\phi)$.

  2. (2)

${\mathbb{J}}$ is divergence free, meaning that $d^{*}{\mathbb{J}}=0$.

  3. (3)

${\mathbb{J}}_{rs}=0$ for every bridge666A bridge is an edge whose removal
separates the graph $G$ into two pieces, each of which is a union of connected
components $(rs)$.

  4. (4)

${\mathbb{J}}$ is constant along the edges of any simple cycle of $G$ that is
disjoint from all others.

  5. (5)

If $\lambda(h_{\alpha})$, the eigenvalue of $\phi$, is simple, then
${\mathbb{J}}$ is proportional to its derivative,

${\color[rgb]{0,0,1}\uwave{\frac{\partial\lambda(h_{\alpha})}{\partial\alpha_{rs}}=\frac{\partial\Lambda}{\partial\alpha_{rs}}=-2\mathbb{J}_{rs}.}}$

We remark, in particular, if the criticality condition holds on an edge of a
disjoint cycle then it holds on all the edges of that cycle. The proof of
Proposition 4.2 will appear after the following short review on derivatives of
eigenvalues, which will be useful for the proof and in the rest of the paper.
The

###  4.3. Directional derivativeDerivatives of eigenvalues

Let us review the calculation of the directional derivative with respect to
$\alpha_{rs}$ of the eigenvalues of the hermitian matrix $\alpha*h$. Fix
$\alpha\in\mathcal{A}(G)$, set $h_{\alpha}=\alpha*h$, and fix $r<s\in[n]$. A
one parameter family in $\mathcal{A}(G)$ through $\alpha$ in the $(rs)$
direction is

${\color[rgb]{1,0,0}\sout{\alpha(t)_{ij}=\begin{cases}\alpha_{ij}+t&\text{ if
}(ij)=(rs)\\\ \alpha_{ij}-t&\text{ if }(ij)=(sr)\\\ \alpha_{ij}&\text{
otherwise}\end{cases}}}$

or equivalently, $\alpha(t)=\alpha+tA{[rs]}$ where Recall that $A{[rs]}$ is
the antisymmetric matrix with zero entries except for $A{[rs]}_{rs}=1$ and
$A[rs]_{sr}=-1$.

Fix $h\in\mathcal{H}(g)$, $\alpha\in\mathcal{A}(G)$, and consider the one-
parameter family $\alpha(t)=\alpha+tA{[rs]}$ that goes through $\alpha$ in the
$(rs)$ direction. The $t$-dependence of $\alpha(t)*h$ occurs only in the
$(rs)$ and $(sr)$ entries with

$(\alpha(t)*h)_{rs}=e^{it}e^{i\alpha_{rs}}h_{rs}=e^{it}(h_{\alpha})_{rs}.$

If $\lambda_{k}(h_{\alpha})$ is a simple eigenvalue then
$\lambda_{k}(\alpha(t)*h)$ $t\mapsto\lambda_{k}(\alpha(t)*h)$ is an analytic
function of $t$ . Its derivative (evaluated around $t=0$, and its derivative
at $t=0$ ) is the directional derivative of $\lambda_{k}(\alpha*h)$.

If $\lambda_{k}(h_{\alpha})$ has a nontrivial multiplicity then the function
$\lambda_{k}(\alpha(t)*h)$ may fail to be differentiable. The theorem of Kato
([10, Thm. 1.8]) and Rellich ([11, Thm. 1]) implies that it is possible to
find analytic families of eigenvalues $\mu_{k}(t)\in\mathbb{R}$ and
eigenvectors $\phi_{k}$ $\phi_{k}(t)$, for all $t\in\mathbb{R}$, so that
$(\alpha(t)*h)\phi_{k}(t)=\mu_{k}(t)\phi_{k}(t)$. However the curves
$\mu_{k}(t)$ may cross, when there are multiple eigenvalues, so the index $k$
does not necessarily correspond to the order of these eigenvalues. In other
words, as $t$ varies, $\lambda_{k}(\alpha(t)*h)$ jumps between various
analytic branches $\mu_{j}(\alpha(t)*h)$. Let us choose one such analytic
family or “branch”, $(\mu,\phi)$, and drop the subscript $k$, and define

$\Lambda:\mathbb{T}^{\beta}\to\mathbb{R}\ \text{ by }\
\Lambda(\alpha^{\prime})=\mu(\alpha^{\prime}*h).$

Using Leibniz’ dot notation to denote derivative with respect to $t$, and
differentiating $h(t)\phi=\mu(t)\phi(t)$ gives

(6) $(\dot{h}(t)-\dot{\mu}(t))\phi(t)+(h(t)-\mu(t))\dot{\phi}(t)=0$

As in [6, Lemma 2.5] or [3, §5.2], taking the inner product with $\phi$ where
$\|{\phi}\|=1$, using that $h$ is Hermitian, and evaluating at $t=0$ gives the
directional derivative of the eigenvalue $\mu$ along this branch:

(7)
$\displaystyle\begin{split}\frac{\partial\Lambda}{\partial\alpha_{rs}}(\alpha)&=\dot{\mu}=\left.\frac{d}{dt}\mu\left((\alpha+t(A[rs])*h\right)\right|_{t=0}=\langle\phi,\dot{h}\phi\rangle\\\
&=i\left(\bar{\phi}_{r}\phi_{s}(h_{\alpha})_{rs}-\bar{\phi}_{s}\phi_{r}(\bar{h}_{\alpha})_{rs}\right)=-2\Im\left((h_{\alpha})_{rs}\bar{\phi}_{r}\phi_{s}\right)\end{split}$

where $\phi_{r}=\phi(r)$ denotes the value of $\phi$ on the vertex $(r)$.

For applications in equation (14 we again (14), consider the case when
$\frac{\partial\Lambda}{\partial\alpha_{rs}}(\alpha)=0$, in which we can
differentiate (6) once again to obtain, as in [6] Lemma 2.6,

(8)
$\langle\phi,\ddot{h}\phi\rangle=-\Re\left((h_{\alpha})_{rs}\bar{\phi}_{r}\phi_{s}\right){\color[rgb]{0,0,1}\uwave{=-}}\left({\color[rgb]{0,0,1}\uwave{(h_{\alpha})_{rs}}}\bar{\color[rgb]{0,0,1}\uwave{\phi_{r}\phi_{s}}}\right)$

and

(9)
$\frac{\partial^{2}\Lambda}{\partial\alpha_{rs}^{2}}=\ddot{\mu}=\langle\phi,\ddot{h}\phi\rangle+2\Re\left(\langle\phi,\dot{h}\dot{\phi}\rangle\right).$

(See also equation (10): the second mixed partial derivatives of $\Lambda$
vanish(10) where
$\frac{\partial^{2}\Lambda}{\partial\alpha_{r_{1}s_{1}}\partial\alpha_{r_{2}s_{2}}}=0$
when $(r_{1},s_{1})$ and $(r_{2}s_{2})$ belong to disjoint cycles.)

The eigenvector $\phi$ of $h_{\alpha}=\alpha*h$ satisfies the criticality
conditionat an edge $(rs)$ if ${\mathbb{J}}_{rs}=0$ where
${\mathbb{J}}={\mathbb{J}}(h_{\alpha},\phi)\in\Omega^{1}(G,\mathbb{R})$ is the
probability currentgiven by

${\color[rgb]{1,0,0}\sout{{\mathbb{J}}_{pq}=\Im\left(\bar{\phi}_{p}(h_{\alpha})_{pq}\phi_{q}\right).}}$

The probability current is defined for any eigenfunction whether or not the
eigenvalue is simple. Let $\phi$ be an eigenfunction of $h_{\alpha}$. Then

  1. (1)

The probability current ${\mathbb{J}}(h_{\alpha},\phi)$ is gauge-invariant.

  2. (2)

It is divergence free, meaning that $d^{*}{\mathbb{J}}=0$.

  3. (3)

It vanishes on every bridge777A bridge is an edge that separates the graph $G$
into two pieces, each of which is a union of connected components.

  4. (4)

It is constant along the edges of any simple cycle of $G$ that is disjoint
from all others.

  5. (5)

If $\lambda$ is a simple eigenvalue of $h_{\alpha}$ with normalized
eigenfunction $\phi$, the probability current
$\mathbb{J}=\mathbb{J}(h_{\alpha},\phi)$ is essentially the derivative of
$\lambda$, that is, for each edge $(rs)$:

${\color[rgb]{1,0,0}\sout{\frac{\partial\lambda(\alpha*h)}{\partial\alpha_{rs}}=\frac{\partial\Lambda}{\partial\alpha_{rs}}=-2\mathbb{J}_{rs}.}}$

We remark, in particular, if the criticality condition holds on an edge of a
disjoint cycle then it holds on all the edges of that cycle. For the action of
the gauge group, if
$\theta=(\theta_{1},\theta_{2},\cdots,\theta_{n})\in\mathcal{G}$ then

${\color[rgb]{1,0,0}\sout{{\mathbb{J}}(\theta\diamond
h_{\alpha},\theta\diamond\phi)_{pq}={\mathbb{J}}(e^{i\theta}h_{\alpha}e^{-i\theta},e^{i\theta}\phi)={\mathbb{J}}(h_{\alpha},\phi).}}$

###  4.4. Proof of Proposition 4.2

The gauge invariance,
${\mathbb{J}}(e^{i\theta}he^{-i\theta},e^{i\theta}\phi)={\mathbb{J}}(h,\phi)$
is straightforward from definition. The divergence is

$\displaystyle(d^{*}{\mathbb{J}})_{r}$
$\displaystyle=\sum_{s}\Im(\bar{\phi}_{r}(h_{\alpha})_{rs}\phi_{s})=\Im\left(\bar{\phi}_{r}\sum_{s}(h_{\alpha})_{rs}\phi_{s}\right)$
$\displaystyle=\Im(\bar{\phi}_{r}\lambda\phi_{r})=\lambda\Im(|\phi_{r}|^{2})=0.$

If removing an edge $E$ $E=(rs)$ separates the graph into two pieces, say
$G_{A}$ and $G_{B}$. Let $\theta\in\Omega^{0}(G)$ take the value $1$ on
$G_{B}$ and $0$ on $G_{A}$. Then $d\theta$ is supported on $E$ and

${\mathbb{J}}_{rs}=\langle
d\theta,{\mathbb{J}}\rangle=\langle\theta,d^{*}{\mathbb{J}}\rangle=0.$

Similarly, if $E,E^{\prime}$ are two edges in a simple cycle that is disjoint
from all others then removing both separates the graph into two pieces. Taking
$\theta$ as above,

${\mathbb{J}}(E)-{\mathbb{J}}(E^{\prime})=\langle
d\theta,{\mathbb{J}}\rangle=0.$

Part (5) is a restatement of equation (7). ∎

Suppose $(rs)$

######  Lemma 4.5.

(Partial criticality.) Let $h_{\alpha}\in\mathcal{H}(G)$ properly supported,
and let ${\mathbb{J}}$ be the probability current of some eigenvector of a
simple eigenvalue of $h_{\alpha}$. If the is a bridge that splits the graph
$G$ into $G_{A}$ and $G_{B}$. Fix $\alpha\in\mathcal{A}(G)$. Suppose $\lambda$
is a simpleeigenvalue of $h_{\alpha}$ with normalized eigenfunction $\phi$. If
$\alpha|G_{B}=0$, that is, such that $h_{\alpha}|G_{B}$, the restriction of
$h_{\alpha}=\alpha*h$ to the $G_{B}\times G_{B}$ blockis real then the
probability current vanishes also: $\mathbb{J}|G_{B}=0$ so for any edge
$E=(uv)\in G_{B}$ the directional derivative vanishes:

${\color[rgb]{1,0,0}\sout{\frac{\partial\Lambda}{\partial\alpha_{uv}}(\alpha)=0.}}$

, is real, then ${\mathbb{J}}$ vanishes on that block,

${\color[rgb]{0,0,1}\uwave{h_{\alpha}|G_{B}\in\mathcal{S}(G_{B})\Rightarrow\mathbb{J}|G_{B}=0.}}$

###### Proof.

Let $\Lambda(\alpha_{t})=\lambda(\alpha_{t}*h)$ be the analytic family of
eigenvalues along the analytic curve (LABEL:eqn-alpha-curve) in the direction
$E=(uv)$ through $\alpha$. By (7), the directional derivative is
$\frac{\partial\Lambda}{\partial\alpha_{uv}}(\alpha)=-2\Im\left((h_{\alpha})_{uv}\bar{\phi}(u)\phi(v)\right)$.
We will show, if the $G_{B}\times G_{B}$ block of $h$ is real, that the
eigenvectors $\phi=(\phi_{A},\phi_{B})$ of $h_{\alpha}$ can be chosen so that
$\phi_{B}$ is real. Since $(uv)\in G_{B}$,

${\color[rgb]{1,0,0}\sout{\mathbb{J}_{uv}=\Im((h_{\alpha})_{uv}\bar{\phi}(u)\phi(v))=0}}$

and Proposition 4.2(5) gives equation (LABEL:eqn-partial-vanishing).

Define a partial conjugation $\mathcal{C}_{B}:\mathcal{H}(G)\to\mathcal{H}(G)$
that conjugates only the $G_{B}\times G_{B}$ block of the matrix. First we
will show that $h$ and $\mathcal{C}_{B}(h)$ share the same spectrum and
multiplicities.

Suppose the ends of the bridge $(rs)$ have $s\in G_{A}$ denote the bridge with
$s\in G_{A}$ and $r\in G_{B}$. For simplicity $r\in G_{B}$. By changing gauge
and scaling $h_{\alpha}$ if needed, we can assume that
$(h_{\alpha})_{rs}=1$and let . Let $e_{s}$ and $e_{r}$ be the corresponding
standard basis vectors , so that so that in the block decomposition to
$G_{A},G_{B}$ we write $h_{\alpha}=A\oplus B+e_{r}e_{s}^{*}+e_{s}e_{r}^{*}$.
Suppose the simple eigenvalue of interest is $\lambda=0$ (otherwise replace
$h_{\alpha}$ with $h_{\alpha}-\lambda I$), and
$\mathcal{C}_{B}(h_{\alpha})=A\oplus\overline{B}+e_{r}e_{s}^{*}+e_{s}e_{r}^{*}$.
Then, $\phi=(\phi_{A},\phi_{B})$ satisfies $h_{\alpha}\phi=\lambda\phi$ if and
only if

${\color[rgb]{1,0,0}\sout{\begin{cases}A\phi_{A}=\lambda\phi_{A}-\phi(r)e_{s},\
\text{and}\\\ B\phi_{B}=\lambda\phi_{B}-\phi(s)e_{r}\end{cases}.}}$

By the let $\phi=(\phi_{A},\phi_{B})$ denote its normalized eigenvector. We
need to show that if $B$ is real then $\phi_{B}$ is (proportional to) a real
vector, in which case ${\mathbb{J}}|G_{B}=0$. If $\phi_{A}=0$ then
$\phi_{B}\in\ker(B)$ and we are done. So assume $\phi_{A}\neq 0$. By
Proposition 4.2 (3) we know that
$\mathrm{Im}[(h_{\alpha})_{rs}\bar{\phi}_{r}\phi_{s}]=\mathrm{Im}[\bar{\phi}_{r}\phi_{s}]=0$,
so we can write $\phi(r)=R_{r}e^{i\theta}$ and $\phi(s)=R_{s}e^{i\theta}$ with
realscalars $\theta,R_{r},R_{s}\in\mathbb{R}$. (If $\phi(r)=\phi(s)=0$ set
$\theta=0$.) Then $e^{i2\theta}\overline{\phi}(r)=\phi(r)$ and
$e^{i2\theta}\overline{\phi}(s)=\phi(s)$. Let
$\phi^{\prime}=(\phi^{\prime}_{A},\phi^{\prime}_{B}):=(\phi_{A},e^{i2\theta}\overline{\phi}_{B})$,
so that $\phi(s)=\phi^{\prime}(s)$, $\phi(r)=\phi^{\prime}(r)$. In particular,

$\displaystyle{\color[rgb]{1,0,0}\sout{A\phi_{A}=\lambda\phi_{A}-\phi(r)e_{s}\
\iff}}$ $\displaystyle{\color[rgb]{1,0,0}\sout{\
A\phi^{\prime}_{A}=\lambda\phi^{\prime}_{A}-\phi^{\prime}(r)e_{s},\
\text{and}}}$
$\displaystyle{\color[rgb]{1,0,0}\sout{B\phi_{B}=\lambda\phi_{B}-\phi(s)e_{r}\
\iff}}$
$\displaystyle{\color[rgb]{1,0,0}\sout{\overline{B}\overline{\phi}_{B}=\lambda\overline{\phi}_{B}-\overline{\phi}(s)e_{r}}}$
$\displaystyle{\color[rgb]{1,0,0}\sout{\ \iff}}$
$\displaystyle{\color[rgb]{1,0,0}\sout{\overline{B}\phi^{\prime}_{B}=\lambda\phi^{\prime}_{B}-e^{i2\theta}\overline{\phi}(s)e_{r}=\lambda\phi^{\prime}_{B}-\phi^{\prime}(s)e_{r}.}}$

That is , by scaling $\phi$ is an eigenvector of $h_{\alpha}=A\oplus
B+e_{r}e_{s}^{*}+e_{s}e_{r}^{*}$ if and only if $\phi^{\prime}$ is an
eigenvector of $\mathcal{C}_{B}(h_{\alpha})$ with the same eigenvalue. Now
suppose the block $B$ is real, so that
$h_{\alpha}=\mathcal{C}_{B}(h_{\alpha})$, if needed we can assume that
$\phi(r)$ and $\phi(s)$ are real. We will now show that
$\phi^{\prime}=(\phi^{\prime}_{A},\phi^{\prime}_{B}):=(\phi_{A},\overline{\phi}_{B})$
is also in $\ker(h_{\alpha})$, which means that $\phi^{\prime}\propto\phi$
since $\lambda$ is simple, and so one of the following eigenvectors

${\color[rgb]{1,0,0}\sout{\frac{1}{2}(\phi_{j}+\phi_{j}^{\prime})=\left(\phi_{j,A},\Re(\phi_{j,B})\right)\
\text{ and }\
\frac{-i}{2}(\phi_{j}-\phi_{j}^{\prime})=(0_{A},\Im(\phi_{j,B}))}}$

$\phi^{\prime}=\phi$ since the kernel is one-dimensional and $\phi_{A}\neq 0$.
This is true because

${\color[rgb]{0,0,1}\uwave{h_{\alpha}\phi=0\Rightarrow
A\phi_{A}+\phi(r)e_{s}=0\ \text{ and }\ B\phi_{B}+\phi(s)e_{r}=0,}}$

is real and non-zero on $G_{B}$and
$\phi(r)=\phi^{\prime}(r),\phi(s)=\phi^{\prime}(s)$, so

$\displaystyle{\color[rgb]{0,0,1}\uwave{\left(A\oplus
B+e_{r}e_{s}^{*}+e_{s}e_{r}^{*}\right)\phi^{\prime}=}}$
$\displaystyle{\color[rgb]{0,0,1}\uwave{(A\phi_{A}+\phi(r)e_{s},B\bar{\phi}_{B}+\phi(s)e_{r})}}$
$\displaystyle{\color[rgb]{0,0,1}\uwave{=}}$
$\displaystyle{\color[rgb]{0,0,1}\uwave{(0,B\bar{\phi}_{B}+\phi(s)e_{r}),}}$

and since $B$ and $\phi(s)$ are real, then
$B\bar{\phi}_{B}+\phi(s)e_{r}=\overline{(B\phi_{B}+\phi(s)e_{r})}=0$.∎

Suppose We now return to the special case of $G$ is a connected graph with
that has disjoint cycles and $n$ vertices. Let $h\in\mathcal{S}(G)$ be
properly supported and generic in the sense of (*). Fix $k$ $(1\leq k\leq n)$
and let consider the Hessians of each
$\Lambda_{k}:\mathbb{T}^{\beta}\to\mathbb{R}$, with
$\Lambda_{k}(\alpha)=\lambda_{k}(\alpha*h)$. Then, $\Lambda_{k}$ has a
nondegenerate critical point at each , at the different signings
$\epsilon\in\\{0,\pi\\}^{\beta}\subset\mathbb{T}^{\beta}$and its Hessian is
diagonal with respect to the decomposition (4), in the basis described in §3.2
(with one edge in each simple cycle).

######  Corollary 4.6.

Suppose $G$ has disjoint cycles and $h\in\mathcal{S}(G)$ satisfies (NCC), then
the Hessian of $\Lambda_{k}$ is diagonal at any
$\epsilon\in\\{0,\pi\\}^{\beta}\subset\mathbb{T}^{\beta}$ for any $1\leq k\leq
n$.

###### Proof.

Each symmetry point $\epsilon\in\left\\{0,\pi\right\\}^{\beta}$ is a
nondegenerate critical point of $\Lambda_{k}$ by [5, 8, 3]. We will show that
its Hessian is diagonal by verifying that the second mixed partial derivatives
vanish. Recall that Fix $k$ and $\epsilon$. We work in the basis of
$T_{\epsilon}\mathbb{T}^{\beta}\cong\mathbb{R}^{\beta}$ given by the prefixed
choice of a single edge $(r_{j},s_{j})\in\gamma_{j}$ has been chosen for each
cycle . To ease notation it suffices to show per cycle of $G$ in §3.2, say
$(r_{j},s_{j})\in\gamma_{j}$. We will show that

(10)
$\frac{\partial^{2}\Lambda_{k}}{\partial\alpha_{r_{1}s_{1}}\partial\alpha_{r_{2}s_{2}}}(\epsilon)=0.$

All other off-diagonal terms would vanish for the same reason. Since the
cycles are “disjoint ” disjoint there exists a bridge $(rs)$ that separates
the graph into two parts, $G_{A},G_{B}$ with $\gamma_{1}\subset G_{A}$ and
$\gamma_{2}\subset G_{B}$. For $t\in[0,1]$ let
$\alpha(t)=\alpha+tA[r_{1},s_{1}]$ Let $\alpha(t)=\epsilon+tA[r_{1},s_{1}]$
and let $h_{t}=\alpha(t)*h$. The matrix $h_{t}$ is real except for the
$(r_{1},s_{1})$ and $(s_{1},r_{1})$ entries so we may apply Proposition
LABEL:prop-conjugation and conclude that Lemma 4.5 and part (5) of Proposition
4.2 to conclude that

${\color[rgb]{1,0,0}\sout{\frac{\partial\Lambda}{\partial\alpha_{r_{2},s_{2}}}}}{\color[rgb]{0,0,1}\uwave{\frac{\partial\Lambda_{k}}{\partial\alpha_{r_{2},s_{2}}}}}(\alpha(t))=0$

for all $t\in[0,1]$$t$ around $0$. Differentiating with respect to $t$, at
$t=0$, gives equation (10).∎

##  5\. Montonicity

### 5.1.

Throughout this section we fix a simple connected graph $G$ with $n$ vertices
and $h\in\mathcal{S(G)}$ strictly supported on $G$.

######  Lemma 5.1.

$($Montonicity$)$Suppose  Suppose $G$ has a cycle $\gamma$ is a cycle ,
disjoint from all others in $G$. Let $\alpha\in\mathcal{A}(G)$ and let
$h\in\mathcal{S}(G)$ that satisfies (NCC). Consider any one-parameter family
$h_{t}=\alpha_{t}*h$ with $\alpha_{t}$ supported on $\gamma$ with
$\int_{\gamma}\alpha=1$. Fix $h\in\mathcal{S}(G)$, real and symmetricand
$\int_{\gamma}\alpha_{t}=t$ for all $t\in[0,\pi]$. Then, for every $k$ ($1\leq
k\leq n)$ the one parameter family $t\mapsto\lambda_{k}((t\alpha)*h)$
$t\mapsto\lambda_{k}(h_{t})$ is strictly monotone in
$t\in(0,\pi)$$t\in[0,\pi]$ for all $k\in[n]$.

We remark that, up to gauge equivalence, we may suppose that $\alpha$ is
supported on a single edge of $\gamma$. This means the family
$h_{t}=(t\alpha*h)$ $h_{t}$ traverses a single segment in the 1-skeleton of
the of the hypercube $\square\subset\mathcal{M}_{h}$ from §3.3. The
monotonicity lemma only applies to these special paths. The rest of §5 is
devoted to the proof of this monotonicity lemmaLemma 5.1, which appears
finally in §5.5.

######  Lemma 5.2 (Flat band criteria).

Suppose that $G$ has a simple cycle $\gamma$ that is disjoint from all other
cycles of $G$. Let $h_{t}=\alpha_{t}*h$ be a others, let $h\in\mathcal{S}(G)$
and consider any one-parameter family , where $\alpha_{t}\in\mathcal{A}(G)$
satisfy $\alpha_{t}=\alpha_{0}$ outside of $h_{t}=\alpha_{t}*h$ with
$\alpha_{t}$ supported on $\gamma$ and $\int_{\gamma}\alpha_{t}=t$ for all
$t\in\mathbb{R}$. If there exists $t_{0}\neq 0\ (\mathop{\rm mod}\pi)$ such
that $h_{t_{0}}$ has an eigenvector $\phi$, with eigenvalue
$\lambda\in\mathbb{R}$ (possibly multiple eigenvalue), satisfying the
criticality condition (4.1) on one (and hence every) edge
$\int_{\gamma}\alpha_{t}=t$ for all $t\in[0,\pi]$. If for some
$t_{0}\in(0,\pi)$ there is some normalized eigenvector of $h_{t_{0}}$ with
probability current that vanishes on some edge in $\gamma$, then . Then, the
(possibly multiple) eigenvalue $\lambda$ is an eigenvalue of of that
eigenvector is a common eigenvalue of all $h_{t}$ for all $t$. with
$t\in[0,\pi]$.

###### Proof.

Without loss of generality assume $t_{0}=1$ and to ease notation let
$\alpha=\alpha_{1}$. To avoid triple subscripts write $\alpha(rs)$ for
$\alpha_{rs}$. Let $(rs)$ be an edge in We number the vertices of $\gamma$ .
There is a gauge equivalent $\alpha^{\prime}=\alpha+d\theta$ so that
$\alpha^{\prime}_{pq}=0$ for every other edge $(pq)\in\gamma$, $(pq)\neq(rs)$,
because $\gamma$ is a simple cycle. If $\phi(r)=\phi(s)=0$ then
$(h_{\alpha^{\prime}}-\lambda)\phi=0$ implies that
$(h_{\alpha^{\prime}_{t}}-\lambda)\phi=0$ for all $t$, and the result follows.
Thus from $1$ to $m=|\gamma|$ cyclically. The statement and the support of the
eigenfunction of interest, say $\phi$, are both gauge invariant, so we may
assume that all matrices $\alpha_{t}$ are supported on a single edge
$(m,1)\in\gamma$ which we will choose according to the support of $\phi$.
Without loss of generality, we may assume ,

  1. (A)

for every edge $(rs)$ in $\gamma$, $\phi(r)$ and $\phi(s)$ are not both zero.

Next we claim

  1. ()

there exists a vertex $r\in\gamma$ of degree $\deg(r)\geq 3$ such that
$\phi(r)=0$.

To prove this claim, up to change of gauge we may assume that $\phi$ is real,
cf. equation (2). In this case , the criticality condition is
$\phi(r)\phi(s)h_{rs}\sin(\alpha(rs))=0$ for any $(rs)\in\gamma$, that
$\lambda=0$, so

    1. (B)

If $(rs)\in\gamma$ and $\alpha(rs)\notin\\{0,\pi\\}$ then $\phi(r)\phi(s)=0$.

Now suppose $r$ is a vertex $h_{t_{0}}\phi=0$ and we want to construct a
family of non-zero vectors $\phi_{t}$ such that $h_{t}\phi_{t}\equiv 0$. If
there is an edge $(rs)\in\gamma$ such that $\phi(r)=0$ and $\phi(s)=0$, then
we may let $\alpha_{t}$ be supported on that edge, in which case the equation
$h_{t}\phi=0$ is independent of $t$, and we are done. From here on assume this
is not the case, i.e. $\phi$ doesn’t vanish on at least one vertex of any edge
in $\gamma$of degree 2 with $\phi(r)=0$. Let $s<r<t$ be the two vertices
attached to $r$. Then $\phi(s)\neq 0$ . Since the probability current
${\mathbb{J}}(h_{t_{0}},\phi)$ vanishes on some edge in $\gamma$, then it
vanishes on all edges in $\gamma$ by part (4) of Proposition 4.2, and since
$\alpha_{t_{0}}$ is supported on $(m,1)$ then
$e^{it_{0}}\phi(m)\bar{\phi}(1)\in\mathbb{R}$ and $\phi(t)\neq 0$ by (A) so
the eigenvalue equation reads

${\color[rgb]{1,0,0}\sout{\phi(s)h_{sr}e^{i\alpha(sr)}+0+\phi(t)h_{rt}e^{i\alpha(rt)}=0}}$

which implies

${\color[rgb]{1,0,0}\sout{\alpha(sr)+\alpha(rt)=0\ (\mathop{\rm mod}\pi)}}$

whenever $\deg(r)=2$ and $\phi(r)=0$. Adding over all vertices $r$ of degree
2, such that $\phi(r)=0$ gives

${\color[rgb]{1,0,0}\sout{\sum_{\phi(r)=0}\alpha(sr)+\alpha(rt)=0}}$

where, as before, $s<r<t$ denote the neighbors of $r$. The terms in this sum
are disjoint by (A). If all vertices $r$ with $\phi(r)=0$ have degree 2 then
every edge $(pq)$ with $\alpha(pq)\neq 0\ (\mathop{\rm mod}\pi)$ occurs in the
sum, by (B). So the sum (LABEL:eqn-sum) actually computes
$\int_{\gamma}\alpha$, which contradicts the assumption that
$\int_{\gamma}\alpha\neq 0\ (\mathop{\rm mod}\pi)$. This proves (${\dagger}$).

Therefore , without $\phi(j)\bar{\phi}(j+1)\in\mathbb{R}$ for all $1\leq j\leq
m-1$. It follows that $e^{it_{0}}\Pi_{j=1}^{m}|\phi(j)|^{2}\in\mathbb{R}$, and
since $e^{it_{0}}\notin\mathbb{R}$, then $\phi$ must vanish at some vertex.
Let $I\subset\gamma$ denote the vertices of degree two on which $\phi(j)=0$.
If $1\in I$ then
$0=(h_{t_{0}}\phi))_{1}=h_{m,1}e^{it_{0}}\phi(m)+h_{1,2}\phi(2)$ so
$e^{it_{0}}\phi(m)\bar{\phi}(2)\in\mathbb{R}$. Similarly, for any other $j\in
I$, $0=(h_{t_{0}}\phi))_{j}=h_{j-1,j}\phi(j-1)+h_{j,j+1}\phi(j+1)$ which means
that $\phi(j-1)\bar{\phi}(j+1)\in\mathbb{R}$. Therefore
$e^{it_{0}}\Pi_{j\in\gamma\setminus I}^{m}|\phi(j)|^{2}\in\mathbb{R}$ and so
must vanish. We conclude that there is a vertex of degree $\geq 3$ on which
$\phi$ vanishes. Without loss of generality , we may suppose that we have
vertices $1<2<3$ in say its vertex $1$, so that
$0=(h_{t_{0}}\phi)_{1}=h_{m,1}e^{it_{0}}\phi(m)+h_{1,2}\phi(2)+F(\phi)$ where
the “out of $\gamma$with $\phi(2)=0,\deg(2)\geq 3,$ and
$\alpha(12)+\alpha(23)\neq 0\ (\mathop{\rm mod}\pi)$. In particular,

${\color[rgb]{1,0,0}\sout{\phi(1)h_{12}e^{i\alpha(12)}+\phi(3)h_{23}e^{i\alpha(23)}\notin\mathbb{R}.}}$

Let $H$ ” contributions are given by $F(\phi):=\sum_{j\notin\lambda;j\sim
1}h_{j1}\phi(j)$, and the previous argument guarantees that $F(\phi)\neq 0$.
and note that $c_{t_{0}}=1$.

Let $A$ denote the union of connected components of $G\setminus\gamma$ that
are connected to vertex $2$ $1$ in $G$. We will show there exists
$c=c(t)\in\mathbb{C}$ so that the vector $\phi_{c}$ defined by , let
$B=G\setminus A$, and write $\phi=(\phi_{A},\phi_{B})$. Define for any $t$

${\color[rgb]{0,0,1}\uwave{c_{t}:=-\frac{\phi(m)h_{m1}e^{it}+\phi(2)h_{12}}{F(\phi)}\
\text{ and }\
\phi_{t}=}}({\color[rgb]{0,0,1}\uwave{c_{t}}}\phi{\color[rgb]{1,0,0}\sout{{}_{c}}}{\color[rgb]{0,0,1}\uwave{{}_{A},\phi_{B}}}){\color[rgb]{1,0,0}\sout{{}_{r}=}}{\color[rgb]{0,0,1}\uwave{,}}$

and note that $F(\phi)$ is independent of $\phi_{B}$ and is an eigenvector of
$\alpha_{t}*h$ with fixed eigenvalue $\lambda$. Up to gauge equivalence, we
may assume that $\alpha_{t}=\alpha$ on all edges except for (12) and that
$\alpha_{t}(12)=t$. By our assumption on $G$, the only vertex in $G\setminus
H$ with a neighbor in $H$ is the vertex $2$ on which $\phi(2)=0$. Therefore
$\left((h_{\alpha_{t}}-\lambda)\phi_{c}\right)(r)=0$ for all $r\neq 2$. To
understand the situation at vertex $2$ let linear in $\phi_{A}$, so
$F(\phi_{t})=c_{t}F(\phi)$. Then, for any $t\in[0-,\pi]$ we have
$h_{t}\phi_{t}=0$ since

${\color[rgb]{1,0,0}\sout{F_{2}}}({\color[rgb]{1,0,0}\sout{\alpha,}}{\color[rgb]{0,0,1}\uwave{h_{t}}}\phi{\color[rgb]{0,0,1}\uwave{{}_{t}}}){\color[rgb]{0,0,1}\uwave{{}_{1}}}={\color[rgb]{1,0,0}\sout{\sum_{r\in
H,r\sim
2}}}h{\color[rgb]{1,0,0}\sout{{}_{2r}}}{\color[rgb]{0,0,1}\uwave{{}_{m,1}}}e{\color[rgb]{1,0,0}\sout{{}^{i\alpha({2r})}}}{\color[rgb]{0,0,1}\uwave{{}^{it}}}\phi({\color[rgb]{1,0,0}\sout{r}}{\color[rgb]{0,0,1}\uwave{m}}){\color[rgb]{1,0,0}\sout{.}}{\color[rgb]{1,0,0}\sout{Then$F_{2}(\alpha_{t},\phi_{c})=cF_{2}(\alpha,\phi)$andatvertex2wehave}}{\color[rgb]{1,0,0}\sout{(}}{\color[rgb]{0,0,1}\uwave{+}}h{\color[rgb]{1,0,0}\sout{{}_{\alpha}-\lambda)\phi}}{\color[rgb]{0,0,1}\uwave{{}_{1,2}\phi(2)+F}}({\color[rgb]{1,0,0}\sout{2}}{\color[rgb]{0,0,1}\uwave{\phi_{t}}})={\color[rgb]{1,0,0}\sout{\phi(1)}}h{\color[rgb]{1,0,0}\sout{{}_{12}}}{\color[rgb]{0,0,1}\uwave{{}_{m,1}}}e{\color[rgb]{1,0,0}\sout{{}^{i\alpha(12)}}}{\color[rgb]{0,0,1}\uwave{{}^{it}\phi(m)}}+{\color[rgb]{1,0,0}\sout{\phi(3)}}h{\color[rgb]{1,0,0}\sout{{}_{23}e^{i\alpha(23)}}}{\color[rgb]{0,0,1}\uwave{{}_{1,2}\phi(2)}}+{\color[rgb]{0,0,1}\uwave{c_{t}}}F{\color[rgb]{1,0,0}\sout{{}_{2}}}({\color[rgb]{1,0,0}\sout{\alpha}}{\color[rgb]{0,0,1}\uwave{\phi)=0}},$

and $r\neq 1$ we have

${\color[rgb]{0,0,1}\uwave{(h_{t}}}\phi{\color[rgb]{0,0,1}\uwave{{}_{t}}}){\color[rgb]{0,0,1}\uwave{{}_{r}}}={\color[rgb]{1,0,0}\sout{0.}}\begin{cases}c_{t}(h_{t_{0}}\phi)_{r}=0&\text{if}\
r\in A\\\ (h_{t_{0}}\phi)_{r}=0&\text{if}\ r\in B,\ r\neq 1\\\
\end{cases}{\color[rgb]{0,0,1}\uwave{.}}$

Therefore,

${\color[rgb]{1,0,0}\sout{-F_{2}(\alpha,\phi)=\phi(1)h_{12}e^{i\alpha(12)}+\phi(3)h_{23}e^{i\alpha(23)}\neq
0}}$

since it is not real. The eigenvalue equation at vertex 2 becomes

$\displaystyle{\color[rgb]{1,0,0}\sout{\left((h_{\alpha_{t}}-\lambda)\phi_{c}\right)(2)=}}$
$\displaystyle{\color[rgb]{1,0,0}\sout{\phi(1)h_{12}e^{it}+\phi(3)h_{23}e^{i\alpha(23)}+F_{2}(\alpha_{t},\phi_{c})}}$
$\displaystyle{\color[rgb]{1,0,0}\sout{=}}$
$\displaystyle{\color[rgb]{1,0,0}\sout{\phi(1)h_{12}e^{it}+\phi(3)h_{23}e^{i\alpha(23)}+cF_{2}(\alpha,\phi).}}$

We conclude that $\lambda$ is an eigenvalue of $h_{\alpha_{t}}$ with
$(h_{\alpha_{t}}-\lambda)\phi_{c}=0$ by choosing

${\color[rgb]{1,0,0}\sout{c=-\frac{\phi(1)h_{12}e^{it}+\phi(3)h_{23}e^{i\alpha(23)}}{F_{2}(\alpha,\phi)}=\frac{\phi(1)h_{12}e^{it}+\phi(3)h_{23}e^{i\alpha(23)}}{\phi(1)h_{12}e^{i\alpha(12)}+\phi(3)h_{23}e^{i\alpha(23)}}.}}\qed{\color[rgb]{1,0,0}\sout{}}$

### 5.3.

Suppose $\gamma$ is a cycle disjoint from all others in $G$ and suppose
$\alpha\in\mathcal{A}(G)$ is supported on a single edge of $\gamma$, say
$\alpha=A[12]$ in the notation of §4.3. Abbreviate $h_{t}=(t\alpha)*h$ so that
$(h_{t})_{ij}=h_{ij}$ for all $ij$ except for $(h_{t})_{12}=h_{12}e^{it}$ and
$(h_{t})_{21}=h_{12}e^{-it}$.

######  Lemma 5.4.

For any $t\in(0,\pi)$ and for any normalized eigenfunction In the setting of
Lemma 5.1, if $(rs)$ is an edge in $\gamma$ and $\phi$ of $h_{t}$ the
probability current satisfies:

${\color[rgb]{1,0,0}\sout{\mathbb{J}(h_{t},\phi)\neq 0.}}$

If $\phi,\phi^{\prime}$ is a normalized eigenvector of $h_{t}$, for some
$t\in(0,\pi)$, then ${\mathbb{J}}={\mathbb{J}}(h_{t},\phi)$ has
${\mathbb{J}}_{rs}\neq 0$.

In particular, if $\phi$ and $\phi^{\prime}$ are eigenvectors of $h_{t}$ for
some $t\in(0,\pi)$ then $\mathbb{J}(h_{t},\phi)$ and
$\mathbb{J}(h_{t},\phi^{\prime})$ the same eigenvalue of $h_{t}$, then
${\mathbb{J}}(h_{t},\phi)_{rs}$ and ${\mathbb{J}}(h_{t},\phi^{\prime})_{rs}$
share the same sign.

###### Proof.

Since $h$ satisfies (NCC) then each of the eigenvalues has
$\Lambda_{k}(\alpha)=\lambda_{k}(\alpha*h)$ has a non-degenerate critical
point at $\alpha=0$, namely at $h=h_{0}$, whose Hessian is diagonal by
Corollary 4.6. In particular, for any $k\in[n]$,
$\Lambda_{k}(\alpha_{t})=\lambda_{k}(h_{t})$ is not constant around $t=0$.
This means that ${\mathbb{J}}_{rs}\neq 0$ for any normalized eigenvector of
any $h_{t}$ with $t\in(0,\pi)$, otherwise we would get a “flat band”, namely a
constant eigenvalue $\lambda_{k}(h_{t})\equiv\lambda$ for all $t$ around $t=0$
by Lemma 5.2. This concludes the first part.

Now let $V=\ker(h_{t}-\lambda_{k}(h_{t]}))$ be some eigenspace of some $h_{t}$
with $t\in(0,\pi)$, and assume $\dim(V)\geq 2$. Then the map
$\phi\mapsto{\mathbb{J}}(h_{t},\phi)$ is a continuous map from
$V\setminus\\{0\\}$ (which is connected) to $\mathbb{R}\setminus\\{0\\}$ so
its image must lie either in $\mathbb{R}_{>0}$ or in $\mathbb{R}_{<}$.
$V\setminus\\{0\\}$. ∎

###  5.5. Proof of Lemma 5.1

The statement is gauge invariant, so we may fix the gauge such that $\alpha$
is supported on a single edge, say, $(12)$. By Kato [10, Thm 1.8] or Rellich
[11, Thm. 1], since this is a one-parameter analytic family of hermitian
matrices, the ordered eigenvalues $(\lambda_{1}\leq\cdots\leq\lambda_{n})$ and
eigenvectors $(\phi_{1},\cdots,\phi_{n})$ of $h$ extend analytically to
eigenvalues and normalized eigenvectors $(\mu_{k}(t),\phi_{k}(t))_{k=1}^{n}$
of $h_{t}$, although apriori their order may not be preserved. The derivative

(11)
$\dot{\mu}_{k}(t)=\frac{d}{dt}\mu_{k}(t)=\langle\phi_{k}(t),\dot{h}_{t}\phi_{k}(t)\rangle=-2{\color[rgb]{1,0,0}\sout{\mathbb{J}}}{\color[rgb]{0,0,1}\uwave{{\mathbb{J}}}}(h_{t},\phi_{k}(t))$

was calculated in (7). If (LABEL:eqn-nonzero) were to fail for some
$\phi=\phi_{k}$ and $t_{0}\in(0,\pi)$ then $(h_{t_{0}},\phi_{k}(t_{0}))$
satisfies the criticality condition on the edge $(12)$ and therefore also
along the whole cycle $\gamma$, by Proposition 4.2. This implies (Proposition
LABEL:prop:_cycle_criticality) that the corresponding eigenvalue $\lambda$ is
constant in $t$, where $h_{t_{0}}\phi_{k}(t_{0})=\lambda\phi_{k}(t_{0})$.
Since $h$ is generic in the sense of (*) and $\lambda_{k}=\mu_{k}$ when $t=0$,
this means that $\lambda=\lambda_{k}(t)=\mu_{k}(t)$ is constant, which
contradicts the fact (Proposition 3.6) that
$\Lambda_{k}:\mathbb{T}^{\beta}\to\mathbb{R}$ has a nondegenerate critical
point at $h$. This proves equation (LABEL:eqn-nonzero).

For the second statement in Since ${\mathbb{J}}(h_{t},\phi_{k}(t))\neq 0$ for
all $k$ and all $t\in(0,\pi)$ by Lemma 5.4, suppose $t\in(0,\pi)$ and $h_{t}$
has a multiple eigenvalue. Since $\mathbb{J}(h_{t},\phi)\neq 0$ for any
nonzero eigenvector $\phi$ in the eigenspace $V$, it cannot change sign on any
path between two vectors in $V\setminus\\{0\\}$. then each $\mu_{k}(t)$ is
strictly monotone in $t\in[0,\pi]$.

###  5.6. Proof of Lemma LABEL:lem:_monotonicity

The statement is gauge invariant, so we may fix the gauge such that $\alpha$
is supported on a single edge, say, $(12)$. So $\alpha=A[12]$ in the notation
of §4.3. As in the preceding paragraph we continue to abbreviate
$h_{t}=(t\alpha)*h$ so that $(h_{t})_{ij}=h_{ij}$ for all $ij$ except for
$(h_{t})_{12}=h_{12}e^{it}$ and $(h_{t})_{21}=h_{12}e^{-it}$.

If all eigenvalues are simple then equation (LABEL:eqn-nonzero) implies they
are strictly monotone as $t$ varies in $[0,\pi]$. If $t_{0}\in(0,\pi)$ and
$h_{t_{0}}$ has a multiple eigenvalue then two (or more) analytic branches of
the eigenvalue surface $\det(h_{t}-\mu I)=0$ meet at $h_{t_{0}}$, say,
$\mu_{j}(t_{0})=\mu_{j^{\prime}}(t_{0})$. For $t<t_{0}$ we may have
$\lambda_{k}(h_{t})=\mu_{j}(t)$ and for $t>t_{0}$ we may have
$\lambda_{k}(h_{t})=\mu_{j^{\prime}}(t).$ In order to guarantee that
$\lambda_{k}(h_{t})$ ismonotone in $t$ near $t=t_{0}$ it suffices to know that
the derivatives $\dot{\mu}_{j}(t_{0})$ and $\dot{\mu}_{j^{\prime}}(t)$ are
nonzero and To conclude that $t\mapsto\lambda_{k}(h_{t})$ it is enough to show
that at multiplicity, if exists, the unordered eigenvalues that meet are
monotone in the same way. That is, if $\mu_{k}(t)=\mu_{k^{\prime}}(t)$ then
their derivatives $-2{\mathbb{J}}(h_{t},\phi_{k}(t))$ and
$-2{\mathbb{J}}(h_{t},\phi_{k}^{\prime}(t))$ have the same sign, which is
Lemma 5.4 abovesigns. The second part of Lemma 5.4 ensures this is the case. ∎

###  5.6. Remark

Equations (11) and (LABEL:eqn-nonzero) Lemma 5.4 and equation (11) mean that
the restriction of the Hermitian form $\dot{h}_{t}$ to the eigenspace of
$h_{t}$ is sign-definite, which is exactly the BZ condition of [7] for a point
of multiplicity to be topologically regular (the BZ condition), see Appendix
B. )

##  6\. Genericity

######  Lemma 6.1.

Let $G=G([n],E)$ be a finite simple connected graph. The set of matrices

$\mathcal{O}=\left\\{h\in\mathcal{S}(G):\ h{\color[rgb]{1,0,0}\sout{\text{
satisfies (*) }}}{\color[rgb]{0,0,1}\uwave{\text{ satisfies (NCC)
}}}\right\\}$

is open and dense in $\mathcal{S}(G)$. Its complement is contained in a closed
semi-algebraic777A semi-algebraic subset of a real vector space is a finite
Boolean combination of sets defined by polynomial equalities $f(x)=0$ and
inequalities $f(x)<0$. subset of $\mathcal{S}(G)$ of codimension $\geq 1$.

###### Proof.

When eigenvalues are simple, the eigenvalues and eigenvectors vary
continuously with the matrix, so the set of matrices satisfying (*NCC) is
open. If a matrix $h^{\prime}\in\mathcal{S}(G)$ fails to satisfy (*NCC) then
there is a signing $\epsilon\in\\{0,\pi\\}^{E}$ for which
$h=\epsilon*h^{\prime}$ lies in at least one of the following sets:

    1. (i)

The set of matrices in $\mathcal{S}(G)$ that are not strictly supported on
$G$, that is, $h_{ij}=0$ for some $(ij)\in E$.

    2. (iii)

The set of matrices in $\mathcal{S}(G)$ that have a multiple eigenvalue:
$\mathrm{discriminant}(h)=0$, or

    3. (iii)

The set of matrices in $\mathcal{S}(G)$ that have a simple eigenvalue with an
eigenvector that vanishes at some vertex.

The sets (i) and (ii) are zero sets of polynomials that are not the zero
polynomial888To see that $\mathrm{discriminant}(h)\neq 0$ for some
$h\in\mathcal{S}(G)$ take $h=\mathop{\rm diag}(1,2,\ldots,n)$.  on
$\mathcal{S}(G)$, so these are algebraic subsets of $\mathcal{S}(G)$ with
positive codimension in $\mathcal{S}(G)$. Since the class of semi-algebraic
subsets is preserved by any change of signing, it suffices to show that the
set (iii) is semi-algebraic with positive codimension in $\mathcal{S}(G)$.

Let us consider the set of $h\in\mathcal{S}(G)$ which admit an eigenvector
$\phi=(0,\phi^{\prime})\in\mathbb{R}^{n}$ that vanishes on the first vertex.
We may write $h$ in block form

$h=\left(\begin{matrix}a&b^{t}\\\ b&d\end{matrix}\right)$

with $a=h_{11}\in A=\mathbb{R}$, with $b\in B=\mathbb{R}^{n-1}$ and
$d\in\mathcal{S}(G^{\prime})$ where $G^{\prime}$ is the graph obtained from
$G$ by removing vertex no. 1. Then $(h-\lambda.I)\phi=0$ is equivalent to

$(d-\lambda.I)\phi^{\prime}=0\ \text{ and }b^{t}.\phi^{\prime}=0.$

There is a diagram of algebraic sets Here,

$\displaystyle\widetilde{\mathcal{H}}$
$\displaystyle=\left\\{(d,\lambda,[\phi^{\prime}],b)\in\mathcal{S}(G^{\prime})\times\mathbb{R}\times\mathbb{P}(\mathbb{R}^{n-1})\times
B:\ (d-\lambda.I)\phi^{\prime}=0\text{ and }b^{t}.\phi^{\prime}=0\right\\}$
$\displaystyle\mathcal{H}$
$\displaystyle=\left\\{(d,\lambda,[\phi^{\prime}])\in\mathcal{S}(G^{\prime})\times\mathbb{R}\times\mathbb{P}(\mathbb{R}^{n-1}):\
(d-\lambda.I)\phi^{\prime}=0\right\\}$

and we have written $[\phi^{\prime}]\in\mathbb{P}(\mathbb{R}^{n-1})$ for the
line defined by $\phi^{\prime}\in\mathbb{R}^{n-1}$. We claim that

$\dim(\widetilde{\mathcal{H}}\times A)=\frac{n(n+1)}{2}-1.$

This holds because:

     * •

$\dim(\mathcal{H})=\frac{(n-1)n}{2}$ since
$\mathcal{H}\to\mathcal{S}(G^{\prime})$ is generically $(n-1)$ to one. (A
generic element $d\in\mathcal{S}(G^{\prime})$ has distinct eigenvalues
$\lambda$, each with a unique projective eigenvector $[\phi^{\prime}]$).

     * •

$\dim(\widetilde{\mathcal{H}})=\frac{(n-1)n}{2}+n-2=\frac{n(n+1)}{2}-2$ since
$\widetilde{\mathcal{H}}\to\mathcal{H}$ is a vector bundle whose fiber over
$(d,\lambda,[\phi^{\prime}])$ is the $n-2$ dimensional vector space
$V_{[\phi^{\prime}]}=\left\\{b\in B:\ b^{t}.\phi^{\prime}=0\right\\}$ (which
depends only on the line $[\phi^{\prime}]$).

The mapping $\widetilde{H}\times A\to\mathcal{S}(G^{\prime})$ is

$(d,\lambda,[\phi^{\prime}],b,a)\to\left(\begin{matrix}a&b^{t}\\\
b&d\end{matrix}\right).$

Its image has dimension $\leq\frac{n(n+1)}{2}-1$ and is exactly the set of
$h\in\mathcal{S}(G)$ which have an eigenvector $\phi=(0,\phi^{\prime})$ whose
first coordinate vanishes. By the Tarski-Seidenberg theorem, it is semi-
algebraic.

Applying this argument to each coordinate gives $n$ such semi-algebraic sets,
whose union is therefore also semi-algebraic of codimension $\geq 1$. ∎

### 6.2.

Let $G$ be a finite graph. Let $\mathcal{B}$ denote the set of matrices
$h\in\mathcal{S}(G)$ that satisfy

     * (✠)

any two gauge-inequivalent signings $\epsilon*h,\epsilon^{\prime}*h$ have
distinct eigenvalues.

######  Lemma 6.3.

The set $\mathcal{B}$ is open and dense in $\mathcal{S}(G)$ and its complement
is contained in an algebraic subset of codimension $\geq 1$.

###### Proof.

We may assume that $G$ is connected. If $G$ is a tree and $h\in\mathcal{S}(G)$
then every signing of $h$ is gauge equivalence to $h$ so we may assume
$\beta(G)\geq 1$. First consider the case that $\beta(G)=1$ so that $G$
contains a unique cycle. Fix an edge $(rs)$ in this cycle. For any
$h\in\mathcal{S}(G)$ there is only one gauge-equivalence class of signings
$\epsilon*h$ of $h$ and it corresponds to changing the sign of $h_{rs}$ (and
of $h_{sr}$).

Let $Q_{\epsilon}(h)$ denote the discriminant of the $2n\times 2n$ matrix
$(h)\oplus(\epsilon*h)$. The set $Q_{\epsilon}^{-1}(0)$ is an algebraic subset
of $\mathcal{S}(G)$ which contains the complement of $\mathcal{B}$. If
$Q_{\epsilon}^{-1}(0)$ contains an open subset of $\mathcal{S}(G)$ then it is
all of $\mathcal{S}(G)$; otherwise it has codimension $\geq 1$. We will assume
that $Q_{\epsilon}(h)=0$ for all $h\in\mathcal{S}(G)$ and arrive at a
contradiction.

In this one dimensional case the hypercube of §3.3 is just an interval whose
endpoints are $h$ and $\epsilon*h$. Let $V={\rm diag}(1,2,\ldots,n)$. Choose
let Let $\xi\in\mathcal{S}(G)$ (strictly supported on $G$) sufficiently small
such that $h:=V+\xi\in\mathcal{O}$ and $\epsilon*h\in\mathcal{O}$ (such $\xi$
exists by Lemma 6.1). The eigenvalues of $h$ are distinct; the eigenvalues of
$\epsilon*h$ are distinct. Therefore, if $Q_{\epsilon}(h)=0$ then $h$ and
$\epsilon*h$ share an eigenvalue, say,
$\lambda_{k}(h)=\lambda_{k^{\prime}}(\epsilon*h)$ . If $\xi$ is sufficiently
small, the eigenvalues of $h$ and of $\epsilon*h$ are small perturbations of
the eigenvalues of $V$, which are distinct integers, hence $k=k^{\prime}$. But
this contradicts the montonicity Lemma LABEL:lem:_monotonicity5.1.

We conclude that for any graph $G$ with $\beta(G)=1$ the function
$Q_{\epsilon}$ vanishes identically on $\mathcal{S}(G)$. Now consider the case
of a general graph $\beta(G)\geq 1$. For a general signings
$\epsilon,\epsilon^{\prime}\in\\{0,\pi\\}^{\beta}$, set

$Q_{\epsilon,\epsilon^{\prime}}(h)={\rm
discr}\left((\epsilon*h)\oplus(\epsilon^{\prime}*h)\right).$

The complement of $\mathcal{B}$ is contained in the algebraic set

$Z:=\bigcup_{\begin{smallmatrix}\epsilon,\epsilon^{\prime}\in\\{0,\pi\\}^{\beta}\\\
\epsilon\neq\epsilon^{\prime}\end{smallmatrix}}Q_{\epsilon,\epsilon^{\prime}}^{-1}(0)=\left(\prod_{\begin{smallmatrix}\epsilon,\epsilon^{\prime}\in\\{0,\pi\\}^{\beta}\\\
\epsilon\neq\epsilon^{\prime}\end{smallmatrix}}Q_{\epsilon,\epsilon^{\prime}}\right)^{-1}(0).$

The set $Z$ is a finite union of sets of the form $Q_{\epsilon}^{-1}(0)$. To
see that each of these sets has codimension $\geq 1$ suppose otherwise. Then
there exists a signing $\epsilon$ so that that $Q_{\epsilon}(h)=0$ for all
$h\in\mathcal{S}(G)$.

Choose a spanning tree in $G$. Label the edges $e_{1},e_{2},\cdots,e_{\beta}$
in the complement and express $\epsilon=\sum\epsilon_{i}e_{i}$ as in §3.2 and
§3.3. Arrange the labeling so that $\epsilon_{1}\neq 0$. The graph
$G^{\prime}$ obtained from $G$ by removing the edges
$e_{2},e_{3},\cdots,e_{\beta}$ has $\beta(G^{\prime})=1$. The signing
$\epsilon$ of $G$ becomes a signing $\eta=\epsilon_{1}$ on $G^{\prime}$, that
is, a change of sign on the remaining edge $e_{1}$. Moreover, any
$h^{\prime}\in\mathcal{S}(G^{\prime})$ can be obtained as a limit of
$h\in\mathcal{S}(G)$ by allowing $h_{rs}\to 0$ where $(rs)$ varies over the
edges $e_{2},e_{3},\cdots,e_{\beta}$. Since $Q_{\epsilon}(h)$ is a continuous
function of $h$, it vanishes on this limiting value, $h^{\prime}$. This proves
that $Q_{\eta}(h^{\prime})=0$ for all $h^{\prime}\in\mathcal{S}(G^{\prime})$
which contradicts the conclusion from the first paragraph. ∎

##  7\. Proofs of Propositions 3.5 and 3.6

###  7.1. Proof of Proposition 3.5

Recall from §3.7 that $G$ is a simple connected graph with disjoint cycles,
$h\in\mathcal{S}(G)$ is generic in the sense of (*NCC), and
$\Lambda_{k}:\mathbb{T}^{\beta}\to\mathbb{R}$ is
$\Lambda_{k}(\alpha)=\lambda_{k}(\alpha*h)$.

It was shown in [5, 8, 3] that each
$\epsilon\in\\{0,\pi\\}^{\beta}\subset\mathbb{T}^{\beta}$ is a nondegenerate
critical point of $\Lambda_{k}$ and its Morse index equals the nodal surplus.
In Corollary 4.6 it is shown that the Hessian of $\Lambda_{k}$ is diagonal
with respect to the decomposition (4). Therefore the Morse index at
$\epsilon\in\\{0,\pi\\}{{}^{\beta}}$ is the number of segments in the
1-skeleton of the Boolean lattice that start at $\alpha$ and descend. By the
montonicity Lemma LABEL:lem:_monotonicity5.1, this is the same as the number
of segments whose endpoints have a lower eigenvalue, which is
$|J_{-}(\alpha)|$. ∎

### 7.2.

A main tool that we will use in proving Proposition 3.6 is the local-global
theorem of [6], which can be stated in a simplified manner as follows:

######  Theorem 7.3.

[6, Theorem 3.10] Suppose $G$ is a simple, connected graph and
$h\in\mathcal{S}(G)$ has a simple eigenvalue $\lambda_{k}(h)$ with a nowhere-
vanishing eigenvector. Let $J\subset[\beta]$, let
$\mathbb{T}_{J}\subset\mathbb{T}^{\beta}$ be the subtorus spanned by
$\\{e_{j}\\}_{j\in J}$, and consider the restriction of $\Lambda_{k}$ to the
subtorus $\mathbb{T}_{J}$ (with $\Lambda_{k}(\alpha)=\lambda_{k}(\alpha*h)$ as
before). Then, $\alpha=0$ is a local minimum (resp. maximum) of $\Lambda_{k}$
on $\mathbb{T}_{J}$ if and only if it is a global minimum (resp. maximum) on
$\mathbb{T}_{J}$.

The statements in [6] involve a different but equivalent graph model, and
apply in a situation of greater generality, where the eigenvector is permitted
to vanish at various vertices. We therefore provide the proof for Theorem 7.3,
adapted to our situation, in the Appendix. Theorem 7.3 together with the
monotonicity lemma gives the following:

######  Corollary 7.4.

Fix $h\in\mathcal{S}(G)$. Fix $\epsilon\in\left\\{0,\pi\right\\}^{\beta}$ and
write $h_{\epsilon}=\epsilon*h$. Let $\mathbb{T}_{-}(\epsilon)$ denote the
sub-torus of $\mathbb{T}^{\beta}$ that is spanned by those basis elements
$e_{j}$ for $j\in J_{-}(\epsilon)$ and similarly for
$\mathbb{T}_{+}(\epsilon)$. Then

$\displaystyle\lambda_{k}(\alpha*h_{\epsilon})$
$\displaystyle\leq\lambda_{k}(h_{\epsilon})\text{ for any
}\alpha\in\mathbb{T}_{-}(\epsilon)$
$\displaystyle\lambda_{k}(\alpha*h_{\epsilon})$
$\displaystyle\geq\lambda_{k}(h_{\epsilon})\text{ for any
}\alpha\in\mathbb{T}_{+}(\epsilon).\qed$

###  7.5. Proof of Proposition 3.6

Suppose $G$ is simple, connected, and has disjoint cycles, and suppose that
$h$ is generic in the sense of (*NCC). Let
$\epsilon,\epsilon^{\prime}\in\left\\{0,\pi\right\\}^{\beta}$. We need to show
that

(12) $J_{+}(\epsilon)=J_{+}(\epsilon^{\prime})\iff\epsilon=\epsilon^{\prime}.$

Using §6 we first reduce to the case that $h$ is generic in the sense of (*)
and also satisfies the condition () which we repeat here:

    1. ()

For each $k\in[\beta]$ the eigenvalue $\lambda_{k}$ takes distinct values on
distinct gauge-equivalence classes of signings of $h$.

The definition of $J_{\pm}(\epsilon)$ implicitly requires a choice of
$k\in[\beta]$ $k\in[n]$ and $h\in\mathcal{S}(G)$ so to be explicit we
temporarily denote it $J_{\pm}(\epsilon,k,h)$. For fixed $\epsilon,k$ this set
is constant (in $h$) on connected components of the open set $\mathcal{O}$ of
$h\in\mathcal{S}(G)$ which satisfy condition (*NCC), because the eigenvalues
$\lambda_{k}(h),\lambda_{k}(\epsilon*h)$ vary continuously with $h$. Suppose
$h\in\mathcal{O}$ does not necessarily satisfy ($\maltese$). The set of
$h^{\prime}\in\mathcal{S}(G)$ which satisfy (As a result, it is enough to
prove the statement for $h\in\mathcal{B}\cap\mathcal{O}$ as this is set is
dense in $\mathcal{O}$ by Lemma 6.3. Recall that
$h\in\mathcal{B}\cap\mathcal{O}$ if and only if it satisfies (NCC) and the
condition (✠) and also satisfy (*) is open and dense in $\mathcal{S}(G)$ by
Lemma 6.1 and Lemma 6.3. For such an element $h^{\prime}$ sufficiently close
to ) which we repeat here:

    1. (✠)

For each $k\in[n]$ the eigenvalue $\lambda_{k}$ takes distinct values on
distinct gauge-equivalence classes of signings of $h$, we then have

${\color[rgb]{1,0,0}\sout{J_{\pm}(\epsilon,k,h)=J_{\pm}(\epsilon,k,h^{\prime})\text{
and }J_{\pm}(\epsilon^{\prime},k,h)=J_{\pm}(\epsilon^{\prime},k,h^{\prime})}}$

so proving (12) for $h^{\prime}$ implies the same thing for $h$.

Therefore we may

From here on we assume that $h$ satisfies (*NCC) and (✠). Given
$\epsilon,\epsilon^{\prime}\in\left\\{0,\pi\right\\}^{\beta}$ suppose
$J_{+}(\epsilon)=J_{+}(\epsilon^{\prime})$. Set $h_{\epsilon}=\epsilon*h$ and
similarly for $h_{\epsilon^{\prime}}$. Using addition modulo $2\pi$ we may
express $\epsilon^{\prime}=\epsilon+\sum_{j=1}^{\beta}a_{j}e_{j}$ with
$a_{j}\in\left\\{0,\pi\right\\}$. Let

${\color[rgb]{1,0,0}\sout{\epsilon^{\prime\prime}=\epsilon+\sum_{j\in
J_{+}(\epsilon)}a_{j}e_{j}}}$

Assume for the sake of contradiction that $\epsilon\neq\epsilon^{\prime}$ so
$\Lambda_{k}(\epsilon)\neq\Lambda_{k}(\epsilon^{\prime})$. Assume that
$\Lambda_{k}(\epsilon)<\Lambda_{k}(\epsilon^{\prime})$ and let us show that
there is $\epsilon^{\prime\prime}$ such that
$\Lambda_{k}(\epsilon)>\Lambda_{k}(\epsilon^{\prime\prime})>\Lambda_{k}(\epsilon^{\prime})$
which provides the needed contradiction. Since
$J_{+}(\epsilon)=J_{+}(\epsilon^{\prime})$ then the intersection
$\mathbb{T}_{+}(\epsilon^{\prime})\cap\mathbb{T}_{-}(\epsilon)$ contains a
signing, call it $\epsilon^{\prime\prime}$. Then, Corollary 7.4 implies
$\lambda_{k}(\epsilon^{\prime\prime}*h)\geq\lambda_{k}(h_{\epsilon})$ because
the above sum is in
$\mathbb{T}_{+}(\epsilon)$$\Lambda_{k}(\epsilon^{\prime\prime})>\Lambda_{k}(\epsilon^{\prime})$
because $\epsilon^{\prime\prime}\in\mathbb{T}_{+}(\epsilon^{\prime})$.
However,

${\color[rgb]{1,0,0}\sout{\epsilon^{\prime\prime}=\epsilon^{\prime}+\sum_{j\in
J_{-}(\epsilon)}a_{j}e_{j}=\epsilon^{\prime}+\sum_{j\in
J_{-}(\epsilon^{\prime})}a_{j}e_{j}}}$

because $J_{-}(\epsilon)=J_{-}(\epsilon^{\prime})$.Lemma 7.4 implies
$\lambda_{k}(\epsilon^{\prime}*h)\geq\lambda_{k}(\epsilon^{\prime\prime}*h)$.
Consequently $\lambda_{k}(h_{\epsilon^{\prime}})\geq\lambda_{k}(h_{\epsilon})$
and the reverse inequality is proven similarly. Thus
$\lambda_{k}(h_{\epsilon})=\lambda_{k}(h_{\epsilon^{\prime}})$ which implies
$\epsilon=\epsilon^{\prime}$ because of condition (): $\lambda_{k}$ takes
distinct values on distinct signings of $h$. This completes the proof of
Proposition 3.6. $\Lambda_{k}(\epsilon^{\prime\prime})<\Lambda_{k}(\epsilon)$
because $\epsilon^{\prime\prime}\in\mathbb{T}_{-}(\epsilon)$.∎

##  Appendix A Proof of Theorem 7.3

### A.1.

We follow the proof in [6] but reorder the steps. Theorem 7.3 begins with a
real symmetric matrix $h\in\mathcal{S}(G)$. Recall that the choice of edge
$(r_{j},s_{j})\in\gamma_{j}$ determines a basis $e_{1},e_{2},\cdots,e_{\beta}$
of $\mathbb{T}^{\beta}=\mathbb{R}^{\beta}/(2\pi i\mathbb{Z})^{\beta}$. The
subset $J\subset[\beta]$ determines the subtorus
$\mathbb{T}_{J}\subset\mathbb{T}^{\beta}$ which is spanned by the coordinates
$e_{j}$ for $j\in J$. We therefore have an analytic family of magnetic
perturbations, $h_{\alpha}=\alpha*h$ for $\alpha\in\mathbb{T}_{J}$, and an
eigenvalue function $\Lambda_{k}:\mathbb{T}_{J}\to\mathbb{R}$ defined by
$\Lambda_{k}(\alpha):=\lambda_{k}(h_{\alpha})$. Since $\lambda=\lambda_{k}(h)$
is a simple eigenvalue, the function $\Lambda_{k}$ is analytic near $\alpha=0$
and is piecewise analytic on all of $\mathbb{T}_{J}$. We may choose the
corresponding eigenvector $\phi$ of $h$ to be real. By assumption, it is
nowhere vanishing.

The point $\alpha=0$ is a critical point of $\Lambda_{k}$. Assume it is a
local minimum. Theorem 7.3 states that it is also a global minimum. (The case
of a maximum can be proven analogously.) So we need to show

(13) $\lambda\leq\lambda_{k}(h_{\alpha})\ \text{ for all}\
\alpha\in\mathbb{T}_{J}.$

### A.2.

The proof in [6] involves several auxiliary matrices. Holding $\phi$ constant,
the function $\langle\phi,h_{\alpha}\phi\rangle:\mathbb{T}_{J}\to\mathbb{R}$
has a critical point at $\alpha=0$ (cf. equation (7)) and we set

$\Omega=\left.\frac{1}{2}\mathop{\rm{Hess}}\left(\langle\phi,h_{\alpha}\phi\rangle\right)\right|_{\alpha=0}.$

The matrix $\Omega$ is a real diagonal $|J|\times|J|$ matrix. It is diagonal
since each entry of $h_{\alpha}$ depends on at most one $\alpha_{j}$
coordinate, so
$\frac{\partial^{2}h_{\alpha}}{\partial\alpha_{i}\partial\alpha_{j}}=0$ for
$i\neq j$. It is real and invertible since its diagonal entries are

(14) $\Omega_{jj}=-h_{r_{j}s_{j}}\phi(r_{j})\phi(s_{j})\neq 0$

as calculated in (8). (Recall that both $h$ and $\phi$ are real, and $\phi$ is
nowhere-vanishing.)

For each $j\in J$ let $R_{j}(t)$ be the hermitian $n\times n$ matrix supported
on the block

$\left[r_{j}r_{j},r_{j}s_{j};s_{j}r_{j},s_{j}s_{j}\right]$

on which it is given by

(15) $R_{j}(t)\quad=\quad
h_{r_{j}s_{j}}\begin{pmatrix}-\frac{\phi(s_{j})}{\phi(r_{j})}&e^{it}\\\
e^{-it}&-\frac{\phi(r_{j})}{\phi(s_{j})}\end{pmatrix}.$

To ease notation let us assume that $J=\\{1,2,\cdots,|J|\\}$. Writing
$\alpha=(\alpha_{1},\alpha_{2},\cdots,\alpha_{J})\in\mathbb{T}_{J}$, the sum

$\sum_{j\in J}R_{j}(\alpha_{j})$

is a family of Hermitian $n\times n$ matrices depending on
$\alpha\in\mathbb{T}_{J}$.

Define the real symmetric $n\times n$ (constant) matrix $S$ by

(16) $S=h-\sum_{j\in J}R_{j}(0).$

This collection of matrices satisfies the following properties:

    1. (a)

For any $\alpha=(\alpha_{1},\alpha_{2},\cdots,\alpha_{|J|})\in\mathbb{T}_{J}$,

$h_{\alpha}=\alpha*h=S+\sum_{j\in J}R_{j}(\alpha_{j}).$

    2. (b)

For any $j\neq j^{\prime}$, $R_{j}(t)$ and $R_{j^{\prime}}(t^{\prime})$
commute for all $t,t^{\prime}$.

    3. (c)

$R_{j}(0)\phi=0$ for every $j\in J$, and hence $S\phi=\lambda\phi$.

    4. (d)

$\det(R_{j}(t))=0$ so $R_{j}(t)$ has rank one

    5. (e)

The semi-definite sign of $R_{j}(t)$ is independent of $t$ since ${\rm
trace}(R_{j}(t))=2\Omega_{jj}$.

(see equation (14)). Let

$m=\left|\\{j\in J\ :\
-h_{r_{i}s_{i}}\phi(r_{i})\phi(s_{i})<0\\}\right|=\mathrm{ind}(\Omega)$

be the number of negative semi-definite $R_{j}$’s. Then the sum of these
commuting rank-one matrices has $m$ negative eigenvalues and $n-|J|>0$ zero
eigenvalues (recalling that $|J|\leq\beta<n$ by the assumption of disjoint
cycles), so

$\lambda_{m+1}\left(\sum_{j\in J}R_{j}(\alpha_{j})\right)=0\ \text{ for all }\
\alpha\in\mathbb{T}_{J}.$

The Weyl inequalities for $h_{\alpha}=S+\sum_{i=1}^{|J|}R_{j}(\alpha_{j})$ may
be expressed as follows, Only the first inequality is required for the case of
a local minimum. Taking $q=m+1$ gives

(17) $\lambda_{k-m}(S)\leq\lambda_{k}(h_{\alpha})\ \text{ for all }\
\alpha\in\mathbb{T}_{J}.$

By (13) the proof of Theorem 7.3 now comes down to the following statement:

######  Lemma A.3.

If $\alpha=0$ is a local minimum of $\Lambda_{k}(\alpha)$ then
$\lambda_{k-m}(S)=\lambda_{k}(h)=\lambda$.

The proof involves the next few paragraphs.

###  A.4.

Holding $\phi$ constant gives a mapping
$ih_{\alpha}\phi:\mathbb{T}_{J}\to\mathbb{C}^{n}$. Define $B$ to be its
derivative $B=\left.iD(h_{\alpha}\phi)\right|_{\alpha=0}$. It is a real
$n\times|J|$ matrix with

$B_{vj}=\left.\frac{\partial}{\partial\alpha_{j}}\left(h_{\alpha}\phi\right)_{v}\right|_{\alpha=0}=\begin{cases}-h_{r_{j}s_{j}}\phi(r_{j})&\text{
if }v=s_{j}\\\ h_{s_{j}r_{j}}\phi({s_{j}})&\text{ if }v=r_{j}\\\ 0&\text{
otherwise}\end{cases}$

A direct but messy calculation involving double subscripts as in [6, Lemma
2.7] gives

(18) $\sum_{j\in J}R_{j}(0)=B\Omega^{-1}B^{T},\ \text{ and therefore }\
S=h-B\Omega^{-1}B^{T}.$

### A.5.

A primary insight in [6] is the identification of the generalized Schur
complements in the real symmetric $(n+|J|)\times(n+|J|)$ matrix

(19) $M=\left(\begin{matrix}h-\lambda&B\\\ B^{T}&\Omega\end{matrix}\right).$

These complements are defined to be

$\displaystyle M/(h-\lambda)=\Omega-B^{T}(h-\lambda)^{+}B$ $\displaystyle
M/\Omega=(h-\lambda)-B\Omega^{-1}B^{T}=S-\lambda.$

where “$+$” denotes the Moore-Penrose pseudo-inverse.999The Moore-Penrose
pseudo-inverse of a real symmetric matrix $A$ is zero on
$(\rm{Im}(A))^{\perp}$ and is the inverse of the isomorphism
$(\ker(A))^{\perp}\to{\rm{Im}}(A)$.

######  Proposition A.6.

[6, Lemma 2.3] The Schur complement to $h-\lambda$ may be identified,

$M/(h-\lambda)=\frac{1}{2}\mathop{\rm{Hess}}(\Lambda_{k}(0)).$

The proof in [6] requires [10] (Remark II.2.2 p. 81) but it is actually
elementary and we provide it here for completeness. The Lemma is equivalent to
the statement that

$\frac{1}{2}\langle\eta,\mathop{\rm{Hess}}(\Lambda_{k}(0))\eta\rangle=\langle\eta,\Omega\eta\rangle-\langle
B\eta,(h-\lambda)^{+}B\eta\rangle\ \text{ for all }\eta\in
T_{0}\mathbb{T}^{J}=\mathbb{R}^{J}.$

To calculate $\langle\eta,\mathop{\rm{Hess}}(\Lambda_{k}(0)\eta\rangle$,
choose an analytic one parameter family $\alpha_{t}$ with
$\eta=\dot{\alpha}(0)$ and write $h_{t}=\alpha_{t}*h$ with simple eigenvalue
$\Lambda_{k}(\alpha_{t})$ and normalized eigenvector $\phi_{t}$ (so that
$\phi=\phi_{0}$). From (6) and (9) the second derivative is

$\langle\eta,\mathop{\rm{Hess}}(\Lambda_{k}(0)\eta\rangle=\left.\frac{d^{2}}{dt^{2}}\Lambda_{k}(\alpha_{t})\right|_{t=0}=\left.\frac{d^{2}}{dt^{2}}\left(\langle\phi_{t},h_{t}\phi_{t}\rangle\right)\right|_{t=0}=\left.\langle\phi,\ddot{h}\phi\rangle+2\Re[\langle\phi,\dot{h}\dot{\phi}\rangle]\right|_{t=0},$

where $\dot{h}=\frac{d}{dt}h_{t}|_{t=0},\
\dot{\phi}=\frac{d}{dt}\phi_{t}|_{t=0}$, and $\ddot{h}=\ddot{h}_{t}|_{t=0}$
(This is the formula from [10] that is referenced in [6].) The first term
agrees with the first term in $2\langle\eta,(M/h-\lambda)\eta\rangle$:

$\frac{1}{2}\langle\phi,\ddot{h}\phi\rangle=\frac{1}{2}\frac{d^{2}}{dt^{2}}\left.\langle\phi,h_{t}\phi\rangle\right|_{t=0}=\langle\eta,\Omega\eta\rangle.$

The $t$-derivative of $ih_{t}\phi$ (keeping $\phi$ fixed) is

$B\eta=iD_{\eta}(h_{\alpha}\phi)=i\dot{h}\phi$

So we need to compare

$-\langle\eta,B^{*}(h-\lambda)^{+}B\eta\rangle=-\langle\dot{h}\phi,(h-\lambda)^{+}\dot{h}\phi\rangle$

with
$\langle\phi,\dot{h}\dot{\phi}\rangle=\langle\dot{h}\phi,\dot{\phi}\rangle$.
From (6),

$\dot{\phi}+(h-\lambda)^{+}\dot{h}\phi=c\phi$

for some constant $c$, because $\phi$ spans the (one dimensional) kernel of
$h-\lambda$. Taking the inner product with $\dot{h}\phi$ and using (7) with
$\dot{\lambda}=0$ gives

$\langle\dot{h}\phi,\dot{\phi}\rangle+\langle\dot{h}\phi,(h-\lambda)^{+}\dot{h}\phi\rangle=0$

as claimed. ∎

###  A.7. Proof of Lemma A.3

The Hainsworth theorem for the matrix $M$ in (19) gives,

$\mathrm{ind}(M)=\mathrm{ind}(M/(h-\lambda))+\mathrm{ind}(h-\lambda)=\mathrm{ind}(M/\Omega)+\mathrm{ind}(\Omega),$

which yields

$\mathrm{ind}(S-\lambda)=\mathrm{ind}(M/(h-\lambda))+k-1-m.$

Since $\alpha=0$ is a local minimum of $\Lambda_{k}$, Proposition A.6 gives
$\mathrm{ind}\left(M/(h-\lambda)\right)=0$. Property (c) of the matrices
$R_{j}(t)$ implies $\lambda$ is an eigenvalue of $S$. Therefore
$\lambda_{k-m}(S-\lambda)=0$.∎

##  Appendix B The BZ condition

The argument in Lemma 5.4 concerning eigenvalues with nontrivial multiplicity
is essentially the same as that of Theorem 1.5 in [7], which we state here for
completeness because it is an important observation about singular critical
points appearsthat may appear. We are interested in the Morse theory of the
composition $\Lambda_{k}:\mathbb{T}^{\beta}\to\mathbb{R}$,

$\begin{CD}\mathbb{T}^{\beta}<EMAIL_ADDRESS>
Fix $\alpha\in\mathbb{T}^{\beta}$ and suppose that $\lambda_{k}(\alpha*h)$ is
an eigenvalue of multiplicity $m\leq\beta$. Let $V$ denote the $m$-dimensional
eigenspace. Consider the set of all Hermitian forms on $V$ that are given by

(20) $\langle\phi,\frac{d}{dt}[(\alpha+tv)*h]\nu\rangle\text{ for }\phi,\nu\in
V$

as $v$ varies within $T_{\alpha}\mathbb{T}^{\beta}$. According to Theorem 1.5
in [7], if there exists $v\in T_{\alpha}\mathbb{T}^{\beta}$ such that the form
(20) is positive definite (which we refer to as the BZ condition), then the
point $\alpha\in\mathbb{T}^{\beta}$ is topologically regular, meaning that for
sufficiently small $\delta>0$ the set
$\mathbb{T}^{\beta}_{\leq\lambda-\delta}$ is a strong deformation retract of
$\mathbb{T}^{\beta}_{\leq\lambda+\delta}$. (Here, $\mathbb{T}^{\beta}_{\leq
t}=\left\\{\alpha^{\prime}\in\mathbb{T}^{\beta}:\
\Lambda_{k}(\alpha^{\prime})\leq t\right\\}$ and
$\lambda=\Lambda_{k}(\alpha)$.)

## References

     * [1] L. Alon, R. Band, G. Berkolaiko, Nodal Statistics on Quantum Graphs, Comm. Math. Phys., 362 (2018), 909-948.
     * [2] Alon, L., Band, R. & Berkolaiko, G. Universality of nodal count distribution in large metric graphs. Experimental Mathematics. pp. 1-35 (2022)
     * [3] L. Alon, M. Goresky, Morse theory for discrete magnetic operators and nodal count distributiion for graphs, in press, J. Spectral Theory.
     * [4] Band, R. The nodal count 0, 1, 2, 3,… implies the graph is a tree. Philosophical Transactions Of The Royal Society A: Mathematical, Physical And Engineering Sciences. 372, 20120504 (2014)
     * [5] G. Berkolaiko, Nodal count of graph eigenvectors via magnetic perturbation. Analysis and PDE 6 (5) (2013).
     * [6] G. Berkolaiko, Y. Canzani, G. Cox, J. L. Marzuola, A local test for global extrema in the dispersion relation of a periodic graph. Pure Appl. Anal. 4 (2) 257 - 286, 2022. https://doi.org/10.2140/paa.2022.4.257
     * [7] G. Berkolaiko and I. Zelenko, Morse inequalities for ordered eigenvalues of generic families of self-adjoint matrices. arXiv:2304.04331 [math.SP]
     * [8] Y. Colin de Verdière, Magnetic interpretation of the nodal defect on graphs, Analysis & PDE 6 (2013), 1235-1242.
     * [9] Fiedler, M. Eigenvectors of acyclic matrices. Czechoslovak Mathematical Journal. 25, 607-618 (1975)
     * [10] T. Kato, Perturbation Theory for Linear Operators, Grundlehren 132 (1980), Springer Verlag, Berlin.
     * [11] F. Rellich, Perturbation Theory of Eigenvalue Problems, Gordon and Breach, N.Y., 1969.