# Average Nodal Count and the Nodal Count Condition for Graphs

Lior Alon  Department of Mathematics, Massachusetts Institute of Technology,
Cambridge, MA, 02139 USA<EMAIL_ADDRESS>and  John Urschel<EMAIL_ADDRESS>
###### Abstract.

The nodal edge count of an eigenvector of the Laplacian of a graph is the
number of edges on which it changes sign. This quantity extends to any real
symmetric $n\times n$ matrix supported on a graph $G$ with $n$ vertices. The
average nodal count, averaged over all eigenvectors of a given matrix, is
known to be bounded between $\frac{n-1}{2}$ and $\frac{n-1}{2}+\beta(G)$,
where $\beta(G)$ is the first Betti number of $G$ (a topological quantity),
and it was believed that generically the average should be around
$\frac{n-1}{2}+\beta(G)/2$. We prove that this is not the case: the average is
bounded between $\frac{n-1}{2}+\beta(G)/n$ and
$\frac{n-1}{2}+\beta(G)-\beta(G)/n$, and we provide graphs and matrices that
attain the upper and lower bounds for any possible choice of $n$ and $\beta$.

A natural condition on a matrix for defining the nodal count is that it has
simple eigenvalues and non-vanishing eigenvectors. For any connected graph
$G$, a generic real symmetric matrix supported on $G$ satisfies this nodal
count condition. However, the situation for constant diagonal matrices is far
more subtle. We completely characterize the graphs $G$ for which this
condition is generically true, and show that if this is not the case, then any
real symmetric matrix supported on $G$ with constant diagonal has a multiple
eigenvalue or an eigenvector that vanishes somewhere. Finally, we discuss what
can be said when this nodal count condition fails, and provide examples.

###### Key words and phrases:

nodal count, spectral graph theory.

###### 2020 Mathematics Subject Classification:

Primary 05C50, 15A42, 15B35.

##  1\. Introduction and Main Results

Let $G$ be a simple connected graph with $n$ vertices, $[n]=\\{1,\ldots,n\\}$,
and $|E(G)|$ edges, where $E(G)$ is the edge set of $G$. The first Betti
number $\beta(G)=|E(G)|-(n-1)$ of $G$ is a topological quantity measuring the
maximum number of independent cycles in $G$, or, equivalently, the number of
additional edges $G$ possesses over an $n$-vertex tree. We say that an
$n\times n$ real symmetric matrix $A$ is _supported on $G$_ if $A_{ij}=0$
whenever $i\neq j$ and $(ij)\not\in E(G)$ (there are no restrictions on the
diagonal of $A$), and is _strictly supported on $G$_ if, in addition,
$A_{ij}\neq 0$ for any edge $(ij)\in E(G)$. Let $\mathcal{S}(G)$ be the vector
space of real-symmetric matrices supported on $G$, and let
$\mathcal{S}_{0}(G)$ denote the matrices in $\mathcal{S}(G)$ with zeros on all
diagonal entries. For example, the adjacency matrix of $G$ is in
$\mathcal{S}_{0}(G)$, and the graph Laplacian on $G$ is in $\mathcal{S}(G)$
but not in $\mathcal{S}_{0}(G)$ (unless $G$ is regular, in which case a scalar
shift of the Laplacian is in $\mathcal{S}_{0}(G)$). The eigenvalues of a
matrix $A\in\mathcal{S}(G)$ are real and indexed in non-decreasing order
$\lambda_{1}(A)\leq\lambda_{2}(A)\leq\ldots\leq\lambda_{n}(A)$. When
$\lambda_{k}(A)$ is simple, we let $\bm{\varphi}_{k}\in\mathbb{R}^{n}$ be its
normalized eigenvector, and we say that $\bm{\varphi}_{k}$ is _nowhere-
vanishing_ (or _non-vanishing_) if $\bm{\varphi}_{k}(i)\neq 0$ for all
$i\in[n]$. To define the _nodal edge count_ of $A\in\mathcal{S}(G)$, we
require that:

######  Nodal Count Condition 1.1.

$A$ is strictly supported on $G$ and all its eigenvalues are simple with
nowhere-vanishing eigenvectors.

######  Remark 1.2 (NCC).

As a convention, we use the phrase “$A$ satisfies Nodal Count Condition 1.1”
in statements of theorems/propositions/lemmas, and use the abbreviation “$A$
satisfies (NCC)” in the remainder of the text.

If $A$ satisfies (NCC), then the nodal count sequence
$\nu(A,\bm{\varphi}_{k})$ for $k\in[n]$ is defined by

$\nu(A,\bm{\varphi}_{k})=\left|\\{i<j:A_{ij}\bm{\varphi}_{k}(i)\bm{\varphi}_{k}(j)>0\\}\right|.$

If $A_{ij}<0$ for edges $(ij)\in E(G)$, as in the case of the graph Laplacian,
the nodal count is the number of edges on which $\bm{\varphi}_{k}$ changes
sign. The study of the nodal count for matrices on graphs began with the work
of Fiedler [12], who, motivated by Sturm’s oscillation theorem, showed that if
$G$ is a tree, then $\nu(A,\bm{\varphi}_{k})=k-1$. Three decades later,
Berkolaiko provided bounds [6]

$k-1\leq\nu(A,\bm{\varphi}_{k})\leq k-1+\beta(G),$

that are tight in general. Band produced an inverse result, showing that if
$\nu(A,\bm{\varphi}_{k})=k-1$ for all $k$, then $G$ must be a tree [5]. He did
so by proving that when $\beta(G)>0$,

$\sum_{k=1}^{n}\left[\nu(A,\bm{\varphi}_{k})-(k-1)\right]>0.$

Since then, the question of how the _nodal surplus_
$\nu(A,\bm{\varphi}_{k})-(k-1)$ is distributed as $k$ varies over $[n]$ was
asked in the context of quantum graphs [1], where it was shown that the
average nodal surplus is $\beta(G)/2$. For quantum graphs, numerical
experiments suggest that for sufficiently large $\beta(G)$ the nodal surplus
is approximately distributed like a Gaussian centered around $\beta(G)/2$ with
variance of order $\beta(G)$ [2]. For matrices supported on graphs, [3] showed
that if $A\in\mathcal{S}_{0}(G)$ is fixed and the signs of its entries are
changed at random, then the average nodal surplus is $\beta(G)/2$. These
results led to a common belief that, in general, the average of
$\nu(A,\bm{\varphi}_{k})-(k-1)$ for a fixed $A\in\mathcal{S}(G)$ should be
$\beta(G)/2$ or close to it.

We show that this is not the case. Our main result is

######  Theorem 1.3.

Let $G$ be a simple, connected graph $G$ on $n$ vertices, and let
$A\in\mathcal{S}(G)$ satisfy Nodal Count Condition 1.1. Then the average nodal
surplus is bounded by

$\frac{\beta(G)}{n}\leq\frac{1}{n}\sum_{k=1}^{n}\left[\nu(A,\bm{\varphi}_{k})-(k-1)\right]\leq\beta(G)-\frac{\beta(G)}{n}.$

Equivalently, the average nodal count is bounded by

$\frac{n-1}{2}+\frac{\beta(G)}{n}\leq\frac{1}{n}\sum_{k=1}^{n}\nu(A,\bm{\varphi}_{k})\leq\frac{n-1}{2}+\beta(G)-\frac{\beta(G)}{n}.$

Moreover, these bounds are tight. For any choice of $n\in\mathbb{N}$ and
$0\leq\beta\leq{n-1\choose 2}$, we construct a graph $G$ (see Figure 1) on $n$
vertices with $\beta(G)=\beta$ and a matrix $A\in\mathcal{S}(G)$ satisfying
Nodal Count Condition 1.1 whose average nodal surplus attains the lower bound
$\frac{\beta(G)}{n}$ (and, therefore, the average nodal surplus of $-A$
attains the upper bound).

######  Remark 1.4 (lower and upper bounds are equivalent due to symmetry).

If $\bm{\varphi}$ is the $k^{th}$ eigenvector of $A$, then it is also the
$(n-k)^{th}$ eigenvector of $-A$, and
$\nu(-A,\bm{\varphi})=|E(G)|-\nu(A,\bm{\varphi})$, where $|E(G)|=\beta(G)+n-1$
is the number of edges. As a result,

$\frac{1}{n}\sum_{k=1}^{n}\nu(A,\bm{\varphi}_{k})=\frac{n-1}{2}+c\quad\Rightarrow\quad\frac{1}{n}\sum_{k=1}^{n}\nu(-A,\bm{\varphi}_{k})=\frac{n-1}{2}+\beta(G)-c,$

hence the lower bound and the upper bound are equivalent.

Figure 1. An example of the extremizer graph $G=G_{n,\beta}$ obtained by
attaching an $m$-clique to an $(n-m)$-vertex path, and removing $\ell$ edges
from one of the clique vertices, while keeping the degree of the clique vertex
connected to the path equal to $m$. The parameters $m$ and $\ell$ are taken
such that ${m-2\choose 2}<\beta\leq{m-1\choose 2}$ and $\ell={m-1\choose
2}-\beta$.

We prove Theorem 1.3 in Subsection 3.1 (lower and upper bounds) and Subsection
3.2 (tight constructions). Theorem 1.3 shows that the average nodal surplus
can be quite far from $\beta(G)/2$ for certain graphs $G$ (see Figure 1) and
matrices $A\in\mathcal{S}(G)$. For zero-diagonal matrices, the same bounds
obviously hold, and we can make some statements regarding their tightness. For
instance, in Proposition 3.2, we prove that, for all $n\in\mathbb{N}$, there
exists an $A\in S_{0}(K_{n})$ that achieves the lower bound of Theorem 1.3,
where $K_{n}$ is the clique on $n$ vertices. In Proposition 3.9, we construct
sparse zero-diagonal matrices that achieve the lower bound of Theorem 1.3 for
nodal surplus up to a multiplicative factor of two. However, in Proposition
3.11, we show that if $G$ is bipartite and $A\in\mathcal{S}_{0}(G)$ satisfies
(NCC), then its average nodal surplus is exactly $\beta(G)/2$. The caveat of
this result is that, while it is known that a generic matrix in
$\mathcal{S}(G)$ satisfies (NCC) (see [4, Lemma 6.1], for example), this is
not always the case for matrices in $\mathcal{S}_{0}(G)$. Nevertheless, our
second main result provides an explicit criterion for a graph $G$ so that a
generic matrix in $\mathcal{S}_{0}(G)$ satisfies (NCC); if this criterion
fails, then all matrices in $\mathcal{S}_{0}(G)$ fail to satisfy (NCC).

(a) Sub-Determinantal (b) Determinantal

Figure 2. Examples of sub-determinantal and determinantal graphs. For each
determinantal graph, we provide a vertex-disjoint union of cycles and edges
covering all vertices in bold.

######  Definition 1.5.

We say that a graph $G$ is _sub-determinantal_ if $\det(A)=0$ for all
$A\in\mathcal{S}_{0}(G)$, and otherwise we say that $G$ is _determinantal_.
Equivalently, $G$ is _determinantal_ if and only if it contains a vertex-
disjoint union of edges and cycles that covers all vertices. For bipartite
$G$, it is enough to ask if $G$ has a perfect matching.

See Figure 2 for examples of determinantal and sub-determinantal graphs. The
terminology “sub”-determinantal suggests that if we start with $n$ vertices,
and iteratively add edges one at a time, then there will be some step $j$ such
that the graphs are sub-determinantal until the $j$-th step and are
determinantal for all subsequent steps.

######  Theorem 1.6.

Let $G$ be a simple, connected graph. The Nodal Count Condition 1.1 is generic
in $\mathcal{S}(G)$. That is, there is an open, dense, and semi-algebraic
subset of $\mathcal{S}(G)$ of matrices satisfying the condition.

For $\mathcal{S}_{0}(G)$, either $G$ is determinental, in which case the Nodal
Count Condition 1.1 is generic in $\mathcal{S}_{0}(G)$ in a similar sense, or
$G$ is sub-determinantal, in which case all matrices in $\mathcal{S}_{0}(G)$
fail to satisfy the condition.

In particular, if $G$ is sub-determinantal and $A\in\mathcal{S}_{0}(G)$, then

  1. (1)

either $\lambda=0$ is a multiple eigenvalue, or

  2. (2)

the eigenvector $\bm{\varphi}$ of $\lambda=0$ satisfies
$\bm{\varphi}(i)\bm{\varphi}(j)=0$ for every edge $(ij)$.

The result for $\mathcal{S}_{0}(G)$ is new, and is proved in Section 4 (see
Theorem 4.1). The first part of the theorem, that (NCC) is generic in
$\mathcal{S}(G)$, is known (see for example [4, Lemma 6.1]) and is only
presented for comparison.

### Discussion: When the Nodal Count Condition fails

Finally, in Section 5 we provide an analysis of the situations that can occur
when (NCC) fails, either by having eigenvectors that vanish somewhere, or
having multiple eigenvalues, or both (i.e., eigenvalue multiplicity and no
non-vanishing orthogonal basis for the corresponding eigenspace). The theory
of nodal domains on graphs is particularly focused on this setting, as when
(NCC) holds, Courant’s proof technique directly translates to tight results
for generalized graph Laplacians. Work for nodal domains includes upper bounds
for weak and strong nodal domains due to Davies, Gladwell, Leydold, and
Stadler [10, 11], lower bounds under (NCC) due to Berkolaiko [6], strengthened
lower bounds when (NCC) fails due to Xu and S.T. Yau [24], and nodal
decomposition results due to the second author [20].

Below we provide some results for each of these three cases for nodal count;
Figure 3 summarizes our discussion into a diagram.

Figure 3. A schematic diagram of what can be said when Nodal Count Condition
1.1 fails.

  1. (1)

vanishing eigenvectors: Given an eigenvector $\bm{\varphi}$ with
$\bm{\varphi}(i)=0$ for some $i$, the notion of nodal count for $\bm{\varphi}$
becomes ambiguous. We provide a construction (Example 5.2) where the total
nodal count, measured either with respect to edges with
$A_{ij}\bm{\varphi}_{k}(i)\bm{\varphi}_{k}(j)>0$ (e.g., a strong nodal edge
count) or $A_{ij}\bm{\varphi}_{k}(i)\bm{\varphi}_{k}(j)\geq 0$ (e.g., a weak
nodal edge count) both fail to satisfy the bounds of Theorem 1.3. However, in
Proposition 5.3 we show that there always exists a signing of the vanishing
entries of eigenvectors, so that the resulting augmented vectors have a total
nodal count satisfying the bounds of Theorem 1.3.

  2. (2)

eigenvalue multiplicity: When a matrix has a repeated eigenvalue, there is no
longer a notion of a fixed eigenbasis. A naive approach would be to simply
choose a nowhere-vanishing eigenbasis and hope that a small enough
perturbation would resolve eigenvalue multiplicity without changing the sign
structure, leading back to the Theorem 1.3 bounds. We provide an example where
this type of approach fails (Example 5.4). In particular, we produce an
example where the sign structure of the eigenbasis of the perturbed matrix
does not match the sign structure of any eigenbasis of the original matrix. On
the other hand, suppose that $A\in\mathcal{S}(G)$ has $r$ distinct eigenvalues
of multiplicities $(m_{i})_{i=1}^{r}$. Proposition 5.7 shows that if
$\sum_{i=1}^{r}{m-1\choose 2}\geq\beta(G)$, then any nowhere-vanishing
eigenbasis of $A$ satisfies the bounds of Theorem 1.3, and Proposition 5.8
shows that for the case $\sum_{i=1}^{r}{m-1\choose 2}<\beta(G)$, if $A$
satisfies a certain transversality condition, then any nowhere-vanishing
eigenbasis of $A$ satisfies the bounds of Theorem 1.3.

  3. (3)

eigenvalue multiplicity & vanishing eigenvectors: When all the eigenvectors of
a repeated eigenvalue vanish at a vertex, the behavior of eigenvectors becomes
rather complex. The adjacency matrix $A$ of $G$, a star graph on $n$ vertices
(Example 5.9), is a standard example illustrating the difficulties in this
case. For this graph, the relative size of the subset of eigenbases of $A$
that can be perturbed to an eigenbasis of a nearby matrix
$A^{\prime}\in\mathcal{S}(G)$ satisfying (NCC) is exponentially small in $n$.

##  2\. Preliminary Results: perturbations, transversality, matrix inversion,
and the nodal-magnetic relation

###  2.1. Additive perturbation and signs of eigenvectors

Here we collect some useful tools from perturbation theory. We mainly concern
ourselves with the simple setting $A_{\epsilon}=A+\epsilon B$, however, we
sometimes require the more general setting of a one-parameter real analytic
family $A_{\epsilon}$ of real symmetric matrices. We start with a celebrated
result proven by Kato [16, Thm 1.8] and by Rellich [19, Thm. 1], see also [23]
for a short proof.

######  Lemma 2.1.

[16, 19] A one-parameter family of real symmetric matrices $A_{\epsilon}$ that
depends analytically on $\epsilon$ admits an orthonormal basis of eigenvectors
that depends analytically on $\epsilon$.

The following lemma is immediate.

######  Lemma 2.2.

Let $A_{\epsilon}$ be a one-parameter real analytic family of $n\times n$ real
symmetric matrices, let
$\bm{\varphi}_{1,\epsilon},\bm{\varphi}_{2,\epsilon},\ldots,\bm{\varphi}_{n,\epsilon}$
be a real analytic orthonormal eigenbasis, with (not necessarily ordered) real
eigenvalues $\lambda_{k,\epsilon}=\langle
A_{\epsilon}\bm{\varphi}_{k,\epsilon},\bm{\varphi}_{k,\epsilon}\rangle$. The
power series expansions $A_{\epsilon}=A^{(0)}+\epsilon
A^{(1)}+O(\epsilon^{2}),\
\lambda_{k,\epsilon}=\lambda_{k}^{(0)}+\epsilon\lambda_{k}^{(1)}+O(\epsilon^{2})$,
and
$\bm{\varphi}_{k,\epsilon}=\sum_{j=0}^{\infty}\epsilon^{j}\bm{\varphi}_{k}^{(j)}$,
satisfy

  1. (1)

we have $\lambda_{k}^{(1)}=\langle
A^{(1)}\bm{\varphi}_{k}^{(0)},\bm{\varphi}_{k}^{(0)}\rangle$, and $\langle
A^{(1)}\bm{\varphi}_{k}^{(0)},\bm{\varphi}_{k^{\prime}}^{(0)}\rangle=0$
whenever $\lambda_{k}^{(0)}=\lambda_{k^{\prime}}^{(0)}$ with $k^{\prime}\neq
k$. In particular, the restriction of $A^{(1)}$ to the eigenspace
$\ker(A^{(0)}-\lambda_{k}^{(0)})$ is diagonal in the basis of
$\bm{\varphi}_{k^{\prime}}^{(0)}$ with
$\lambda_{k^{\prime}}^{(0)}=\lambda_{k}^{(0)}$.

  2. (2)

There is a discrete (locally finite) set $\mathcal{B}\subset\mathbb{R}$ such
that for all $\epsilon\in\mathbb{R}\setminus\mathcal{B}$ the support of
$\bm{\varphi}_{k,\epsilon}$ is independent of $\epsilon$ and given by

$\mathrm{supp}(\bm{\varphi}_{k,\epsilon})=\bigcup_{j=0}^{\infty}\mathrm{supp}(\bm{\varphi}_{k}^{(j)}).$

  3. (3)

Let $b>0$ such that $(0,b)\cap\mathcal{B}=\emptyset$, let
$i\in\bigcup_{j=0}^{\infty}\mathrm{supp}(\bm{\varphi}_{k}^{(j)})$ and let
$j_{i}$ be the minimal $j$ for which $\varphi_{k}^{(j)}(i)\neq 0$, then for
all $\epsilon\in(0,b)$,

$\mathrm{sign}(\bm{\varphi}_{k,\epsilon}(i))=\mathrm{sign}(\bm{\varphi}_{k}^{(j_{i})}(i)).$
(2.1)

###### Proof.

Part (1) is given by the first-order term in the expansion of
$\langle(A_{\epsilon}-\lambda_{k,\epsilon})\bm{\varphi}_{k,\epsilon},\bm{\varphi}_{k^{\prime},\epsilon}\rangle\equiv
0$. Part (2) is due to the fact that for each $i\in[n]$, either
$\bm{\varphi}_{k}^{(j)}(i)=0$ for all $j$, or the real analytic function
$\epsilon\mapsto\bm{\varphi}_{k,\epsilon}(i)=\sum_{j=0}^{\infty}\epsilon^{j}\bm{\varphi}_{k}^{(j)}(i)$
has a discrete set of zeros. For part (3) notice that
$\bm{\varphi}_{k,\epsilon}(i)\neq 0$ for all $\epsilon\in(0,b)$, since
$(0,b)\cap\mathcal{B}=\emptyset$, so
$\mathrm{sign}(\bm{\varphi}_{k,\epsilon}(i))$ is constant in that interval.
For small enough $\epsilon>0$ we have
$\bm{\varphi}_{k,\epsilon}=\epsilon^{j_{i}}(\bm{\varphi}_{k}^{(j_{i})}(i)+O(\epsilon))$
which determine the sign. ∎

Now consider the simple case of $A_{\epsilon}=A+\epsilon B$.

######  Lemma 2.3.

Let $A_{\epsilon}=A+\epsilon B$ with $A$ and $B$ real symmetric $n\times n$
matrices, then

  1. (1)

If $A$ has simple eigenvalues, then $A_{\epsilon}$ has simple eigenvalues for
all $\epsilon\in(-T,T)$ with

$T=\frac{\min_{k}|\lambda_{k+1}(A)-\lambda_{k}(A)|}{\max_{k}|\lambda_{k}(B)|}.$

  2. (2)

Let
$\bm{\varphi}_{\epsilon}=\sum_{j=0}^{\infty}\epsilon^{j}\bm{\varphi}^{(j)}$ be
an eigenvector of $A_{\epsilon}$ with a simple eigenvalue for all $\epsilon$
in some interval $(a,b)$. Then in this interval, we have a recursive formula

$\bm{\varphi}^{(j)}=-(A-\lambda^{(0)}I)^{+}B\bm{\varphi}^{(j-1)}+\sum_{m=1}^{j}\lambda^{(m)}(A-\lambda^{(0)}I)^{+}\bm{\varphi}^{(j-m)},$
(2.2)

where $(A-\lambda^{(0)}I)^{+}$ denotes the pseudo-inverse111The pseudo-inverse
$M^{+}$ of a real symmetric matrix $M$ is a real symmetric matrix with the
same kernel of $M$, such that $M^{+}M=MM^{+}$ acts as the identity on the
orthogonal complement of the kernel. of $A-\lambda^{(0)}I$. This formula
becomes simpler, if we assume that $\lambda^{(0)}=0$ and $\langle
B\bm{\varphi}^{(0)},\bm{\varphi}^{(0)}\rangle=0$, in which case
$\bm{\varphi}^{(1)}=-A^{+}B\bm{\varphi}^{(0)}$ and, for all $j>1$,

$\bm{\varphi}^{(j)}=-A^{+}B\bm{\varphi}^{(j-1)}+\sum_{m=2}^{j}\lambda^{(m)}A^{+}\bm{\varphi}^{(j-m)}.$
(2.3)

  3. (3)

Let $\bm{\varphi}_{1,\epsilon},\ldots,\bm{\varphi}_{n,\epsilon}$ be the
orthonormal eigenvectors of $A_{\epsilon}$ as in the previous lemma, and
suppose that $\lambda_{k,0}=\lambda$ is a multiple eigenvalue of $A$ and that
$\lambda_{k,\epsilon}$ is simple for all $\epsilon\in(0,b)$ for some $b>0$.
Then, $\lambda_{k}^{(1)}\neq\lambda_{k^{\prime}}^{(1)}$ for any
$k^{\prime}\neq k$ with $\lambda_{k^{\prime}}^{(0)}=\lambda$, and the
following holds for all $\epsilon\in(0,b)$,

$\bm{\varphi}_{k}^{(1)}=-(A-\lambda)^{+}B\bm{\varphi}_{k}^{(0)}+\sum_{\lambda_{k^{\prime}}^{(0)}=\lambda,\
k^{\prime}\neq
k}\frac{\langle(A-\lambda)^{+}B\bm{\varphi}_{k^{\prime}}^{(0)},B\bm{\varphi}_{k}^{(0)}\rangle}{\lambda_{k}^{(1)}-\lambda_{k^{\prime}}^{(1)}}\bm{\varphi}_{k^{\prime}}^{(0)}.$
(2.4)

###### Proof.

For part (1) see [15, Cor. 4.3.15] for the value of $T$ that ensures simple
eigenvalues when $\epsilon\in(-T,T)$. For part (2), the eigenvalue-eigenvector
equation $(A+\epsilon B-\lambda_{\epsilon}I)\bm{\varphi}_{\epsilon}=0$
decomposes according to powers of $\epsilon$, with the below equation
representing $\epsilon^{j}$, as follows:

$(A-\lambda^{(0)}I)\bm{\varphi}^{(j)}=-B\bm{\varphi}^{(j-1)}+\sum_{i=1}^{j}\lambda^{(i)}\bm{\varphi}^{(j-i)}.$

the normalization condition
$\langle\varphi_{\epsilon},\varphi_{\epsilon}\rangle\equiv 1$ decomposes
according to powers of $\epsilon$ gives that
$\langle\varphi^{(0)},\varphi^{(j)}\rangle=0$ for all $j>0$, and using the
assumption that $\lambda^{(0)}$ is simple we get that $\varphi^{(j)}$ is in
the range of $(A-\lambda^{(0)}I)^{+}$. Equation (2.2) is obtained by
multiplying both sides by $(A-\lambda^{(0)}I)^{+}$.

For Equation (2.3), note that the inner product of the $j=1$ equation with
$\bm{\varphi}^{(0)}$ gives
$\lambda^{(1)}=\langle\bm{\varphi}^{(0)},B\bm{\varphi}^{(0)}\rangle$, so the
$j=1$ equation gives $A\bm{\varphi}^{(1)}=-B\bm{\varphi}^{(0)}$, and so
Equation (2.3) follows.

Finally, for part (3), let us write
$\bm{\varphi}_{k}^{(1)}=w+\sum_{\lambda_{k^{\prime}}^{(0)}=\lambda,\
k^{\prime}\neq k}c_{k,k^{\prime}}\bm{\varphi}_{k^{\prime}}^{(0)}$, for some
scalars $c_{k,k^{\prime}}$ and a vector $w\perp\ker(A-\lambda I)$, using that
$\langle\bm{\varphi}_{k}^{(1)},\bm{\varphi}_{k}^{(0)}\rangle=0$. The $j=1$
term of the eigenvalue-eigenvector equation gives

$\displaystyle(A-\lambda I)w$ $\displaystyle=(A-\lambda
I)\bm{\varphi}_{k}^{(1)}=-B\bm{\varphi}_{k}^{0}+\lambda^{(1)}\bm{\varphi}^{0},\
\text{so}$ $\displaystyle w$ $\displaystyle=-(A-\lambda
I)^{+}B\bm{\varphi}_{k}^{0}.$

To find $c_{k,k^{\prime}}$ we take the inner product of
$\bm{\varphi}_{k^{\prime}}^{(0)}$ and the second-term of the eigenvalue-
eigenvector equation

$(A-\lambda_{k}^{(0)}I)\bm{\varphi}_{k}^{(2)}=-B\bm{\varphi}_{k}^{1}+\lambda_{k}^{(1)}\bm{\varphi}_{k}^{1}+\lambda_{k}^{(2)}\bm{\varphi}_{k}^{0},$

where the right-hand-side is equal to
$-Bw+c_{k,k^{\prime}}(\lambda_{k}^{(1)}-B)\bm{\varphi}_{k^{\prime}}^{(0)}$
plus a vector orthogonal to $\bm{\varphi}_{k^{\prime}}^{(0)}$, so

$c_{k,k^{\prime}}=\frac{\langle-
Bw,\bm{\varphi}_{k^{\prime}}^{(0)}\rangle}{\langle(\lambda_{k}^{(1)}-B)\bm{\varphi}_{k^{\prime}}^{(0)},\bm{\varphi}_{k^{\prime}}^{(0)}\rangle}=\frac{\langle-
Bw,\bm{\varphi}_{k^{\prime}}^{(0)}\rangle}{\lambda_{k}^{(1)}-\lambda_{k^{\prime}}^{(1)}}.$

∎

###  2.2. Transversality

When a matrix $A\in\mathcal{S}(G)$ has eigenvalue multiplicity, there is no
longer a unique choice of eigenbasis, and different choices can lead to
different nodal counts. One naive approach to bound nodal counts in this
situation would be to slightly change the eigenvalues to resolve multiplicity,
and then slightly change the eigenvectors to ensure the resulting matrix
$A^{\prime}$ is in $\mathcal{S}(G)$, all while maintaining the sign structure
of the matrix and eigenbasis. The orbit of a matrix $A\in\mathcal{S}(G)$ under
the action of the orthogonal group $O(n)$, which we denote by
$O(n).A:=\\{oAo^{T}:o\in O(n)\\}$, is the set of matrices (not necessarily in
$\mathcal{S}(G)$) with the same spectrum. A sufficient condition for this
naive approach to work is that the intersection of $O(n).A$ and
$\mathcal{S}(G)$ at $A$ is transversal (see Figure 4). Namely, this
transversality is a sufficient condition so that for any choice of nowhere-
vanishing eigenbasis of $A$ there is a nearby matrix
$A^{\prime}\in\mathcal{S}(G)$ satisfying (NCC) whose eigenbasis has the same
sign structure and, therefore, the same nodal count. We state the following
result for a general vector space $W$, which will be applied to either
$W=\mathcal{S}(G)$ or $W=\mathcal{S}_{0}(G)$.

Figure 4. A heuristic diagram to illustrate transversality of $O(n)$ orbits
with respect to a vector space $W\subset\mathcal{S}(n)$. The coordinate
system, $D$ against $V$ (in the spectral decomposition $A=VDV^{T}$), means
that vertical lines are $O(n)$ orbits and horizontal lines contain all
matrices with the same eigenbasis.

######  Lemma 2.4 (Transversality).

Let $\mathcal{S}(n)$ and $\mathcal{A}(n)$ be the set of real symmetric and
real anti-symmetric matrices, respectively, $A\in\mathcal{S}(n)$, and
$O(n).A=\\{oAo^{T}:o\in O(n)\\}$.

  1. (1)

The tangent space at $A$ is $T_{A}(O(n).A)=\\{AX-XA:X\in\mathcal{A}(n)\\}$. If
$A$ has $r$ distinct eigenvalues of multiplicities $m_{1},\ldots,m_{r}$,
$\sum_{i=1}^{r}m_{i}=n$, then

$\dim(\\{AX-XA:X\in\mathcal{A}(n)\\})={n\choose 2}-\sum_{i=1}^{r}{m_{i}\choose
2}.$

  2. (2)

Let $W\subset\mathcal{S}(n)$ be a vector subspace containing $A$. We say that
$A$ satisfies the _transversality condition_ if the intersection of $O(n).A$
and $W$ at $A$ is transversal, namely if

$\\{AX-XA:X\in\mathcal{A}(n)\\}+W=\mathcal{S}(n).$ (2.5)

If $A$ satisfies the _transversality condition_ , then, for any choice of non-
vanishing eigenbasis of $A$, say
$\bm{\varphi}_{1},\bm{\varphi}_{2},\ldots,\bm{\varphi}_{n}$ with
$\bm{\varphi}_{k}(i)\neq 0$ for all $i,k\in[n]$, there is an arbitrarily close
matrix $A^{\prime}\in W$ that satisfies Nodal Count Condition 1.1 with an
eigenbasis $\bm{\psi}_{1},\bm{\psi}_{2},\ldots,\bm{\psi}_{n}$, such that

$\displaystyle\mathrm{sign}(\bm{\varphi}_{k}(i))=\mathrm{sign}(\bm{\psi}_{k}(i))\
$ $\displaystyle\ \text{for all $i,k\in[n]$},$
$\displaystyle\mathrm{sign}(A^{\prime}_{ij})=\mathrm{sign}(A_{ij})\ $
$\displaystyle\ \text{for all }(ij)\ \text{with}\ A_{ij}\neq 0.$

###### Proof.

The tangent space of $O(n)$ at the identity is the Lie algebra
$\mathcal{A}(n)$, so the tangent space $T_{A}(O(n).A)$ consists of all
matrices of the form $\frac{d}{dt}(e^{tX}Ae^{-tX})|_{t=0}=XA-AX$ for all
$X\in\mathcal{A}(n)$. Let $O_{A}\subset O(n)$ be the subgroup of $o$ for which
$oAo^{T}=A$, and consider its vector space of generators
$\mathcal{A}_{A}\subset\mathcal{A}(n)$, namely, $X\in\mathcal{A}(n)$ such that
$e^{tX}\in O_{A}$ for all $t\in\mathbb{R}$. Then
$\dim(\mathcal{A}_{A})=\dim(O_{A})$ and $\mathcal{A}_{A}$ is exactly the
kernel of the linear map $X\mapsto XA-AX$, so
$\dim(T_{A}(O(n).A))=\dim(\mathcal{A}(n))-\dim(O_{A})$. To calculate the
dimension of $O_{A}$, notice that $o\in O_{A}$, i.e., it is an orthogonal
matrix that commutes with $A$, if and only if it is block diagonal with
respect to the eigenspaces of $A$ and acts as an orthogonal map on each
eigenspace. That is $O_{A}\cong\oplus_{i=1}^{r}O(m_{i})$ and therefore
$\dim(O_{A})=\sum_{i=1}^{r}{m_{i}\choose 2}$. This proves part (1).

For part (2), by definition, $O(n).A$ intersect $W$ transversely at $A$ (in
the ambient space $\mathcal{S}(n)$) if and only if the tangent spaces $T_{A}W$
and $T_{A}(O(n).A)$ add up to $T_{A}\mathcal{S}(n)$. Using that $T_{A}W=W$ and
$T_{A}\mathcal{S}(n)=\mathcal{S}(n)$, the transversality condition becomes

$\\{AX-AX:X\in\mathcal{A}(n)\\}+W=\mathcal{S}(n).$

If the intersection is transversal, then for any $\epsilon>0$ there is a
$\delta>0$, such that for any $\tilde{A}\in\mathcal{S}(n)$ with
$\|A-\tilde{A}\|<\delta$ there is $o\in O(n)$ with $\|o-I\|<\epsilon$ for
which $o\tilde{A}o^{T}\in W$. Choosing an eigenbasis gives a spectral
decomposition $A=VDV^{T}$ with $D$ diagonal of eigenvalues and
$V_{ik}=\bm{\varphi}_{k}(i)$. Let $D^{\prime}$ be any diagonal matrix, with
distinct diagonal entries, such that $\|D-D^{\prime}\|<\delta$. Then
$\tilde{A}=VD^{\prime}V^{T}$ has simple spectrum and
$\|A-\tilde{A}\|=\|D-D^{\prime}\|<\delta$. Letting $V^{\prime}=oV$ gives

$A^{\prime}=o\tilde{A}o^{T}=V^{\prime}D^{\prime}(V^{\prime})^{T}\in W,$

so that we can set $\bm{\psi}_{k}(i)=V^{\prime}_{ik}$. By taking $\epsilon$
and $\delta$ arbitrarily small we can make $\|A^{\prime}-A\|$ and
$\|V^{\prime}-V\|$ arbitrarily small, which means that
$|A^{\prime}_{ij}-A_{ij}|$ and $|V^{\prime}_{ij}-V_{ij}|$ are arbitrarily
small for all $ij$, and so they have the same sign structure. ∎

###  2.3. Sparsity of the matrix inverse

Here we provide two results regarding the sparsity structure of the inverse of
a matrix $A\in\mathcal{S}(G)$. First, we consider the sparsity structure of
the inverse of any invertible $A\in\mathcal{S}_{0}(P_{2n})$ strictly supported
on $P_{2n}$, the path graph on $2n$ vertices. The following is a
straightforward consequence of the recurrence formula for the entries of the
inverse of a symmetric tridiagonal matrix (see [22] for details).

######  Proposition 2.5 (corollary of [22, Theorem 1]).

If $A\in\mathcal{S}_{0}(P_{2n})$ is strictly supported on $P_{2n}$ and
$\det(A)\neq 0$, then $A_{ij}^{-1}\neq 0$, $i\geq j$, if and only if $i$ is
even and $j$ is odd.

In Subsection 3.4 we prove that such a matrix $A\in\mathcal{S}_{0}(P_{2n})$
always exists. Next, consider an irreducible symmetric non-negative matrix
$A$. We note that $(A-\mu I)^{-1}$ is an entry-wise non-zero matrix for all
but finitely many choices of $\mu\in\mathbb{R}$:

######  Proposition 2.6.

For any connected graph $G$ and non-negative matrix $A\in\mathcal{S}(G)$
strictly supported on $G$, there exists a finite set
$\Lambda\subset\mathbb{R}$ such that $(A-\lambda I)^{-1}_{ij}\neq 0$ for all
$i,j\in[n]$ and $\lambda\not\in\Lambda$.

###### Proof.

Suppose $\lambda$ is not an eigenvalue of $A$. The $i,j$ entry of $(A-\lambda
I)^{-1}$ is equal to zero if and only if $\mathrm{adj}(A-\lambda I)_{ij}=0$.
Considering the degree $\leq n-1$ polynomial
$p(\lambda)=\mathrm{adj}(A-\lambda I)_{ij}$, we note that either
$p(\lambda)=0$ for all $\lambda\in\mathbb{R}$, or equals zero for at most
$n-1$ values of $\lambda$. Taking $\lambda>\rho(A)$, $\lambda I-A$ is an
irreducible M-matrix, and so its inverse $(\lambda I-A)^{-1}$ is a positive
matrix [15, 8.3.P15]. Therefore, $p(\lambda)>0$ for $\lambda$ sufficiently
large, implying that $p(\lambda)=0$ for at most $n-1$ values of $\lambda$.
Taking $\Lambda$ be the union of the eigenvalues of $A$ and the zeros of
$\mathrm{adj}(A-\lambda I)_{ij}$ for all entries $i,j\in[n]$ completes the
proof. ∎

###  2.4. Nodal-Magnetic relation

To bound the average nodal count beyond the sum of known bounds for individual
eigenvectors $0\leq\nu(A,\bm{\varphi}_{k})-(k-1)\leq\beta(G)$, we exploit the
topological characterization of the nodal surplus
$\nu(A,\bm{\varphi}_{k})-(k-1)$ introduced by Berkolaiko [7] and further
developed by Colin de Verdiere [8]. We present this characterization in a
short and simplified manner, without introducing magnetic fields and the gauge
group. We recommend [3] for a thorough introduction. The simplified setup is
as follows. Let $G$ be a simple connected graph, fix an arbitrary spanning
tree of $G$, and let $((r_{\ell},s_{\ell}))_{\ell=1}^{\beta(G)}\subset E(G)$
be the $\beta(G)$ edges of $G$ that are not contained in the chosen spanning
tree. Given $A\in\mathcal{S}(G)$ and
$\theta=(\theta_{1},\ldots,\theta_{\beta})\in\mathbb{T}^{\beta}$, let
$A_{\theta}$ be the Hermitian matrix supported on $G$ with

$(A_{\theta})_{r_{\ell},s_{\ell}}=e^{i\theta_{\ell}}A_{r_{\ell},s_{\ell}}\qquad\text{and}\qquad(A_{\theta})_{s_{\ell},r_{\ell}}=e^{-i\theta_{\ell}}A_{s_{\ell},r_{\ell}}\qquad\text{for
all }\ell=1,\ldots,\beta(G),$

and $(A_{\theta})_{ij}=A_{ij}$ otherwise.

######  Theorem 2.7 ([7, 8] Topological characterization of the nodal
surplus).

Let $A\in\mathcal{S}(G)$ satisfy Nodal Count Condition 1.1, and consider the
functions $\lambda_{k}:\mathbb{T}^{\beta}\to\mathbb{R}$ with
$\lambda_{k}(\theta)$ denoting the $k^{th}$ eigenvalue of $A_{\theta}$. Then
$\lambda_{k}(\theta)$ is smooth around $\theta=0$, with a critical point at
$\theta=0$ which is non-degenerate and has Morse index equal to
$\nu(A,\bm{\varphi}_{k})-(k-1)$. Equivalently, $\mathrm{Hess}\lambda_{k}(0)$,
the Hessian of $\lambda_{k}$ at $\theta=0$, is an invertible
$\beta(G)\times\beta(G)$ real symmetric matrix with exactly
$\nu(A,\bm{\varphi}_{k})-(k-1)$ negative eigenvalues.

This theorem, in full generality, considers (Gauge) equivalence classes of
matrices. The choice of spanning tree amounts to choosing a representative
$A_{\theta}$ from each equivalence class, which is why the above theorem is
independent of the choice of spanning tree. See [3, Subsection 2.5] for
details.

##  3\. Tight Bounds for Average Nodal Count

In this section, we provide a proof of Theorem 1.3, our main result. We do so
in two parts. First, in Subsection 3.1, we prove the bounds of Theorem 1.3
using Berkolaiko’s theorem and a clever linear algebraic argument. Then, in
Subsection 3.2, we illustrate the tightness of these bounds through
mathematical constructions for all choices of $n$ and $\beta$.

###  3.1. Proof of Theorem 1.3: Bounding nodal count

Using the nodal-magnetic relation introduced in Subsection 2.4, we prove the
bounds of Theorem 1.3.

###### Proof of Theorem 1.3: Part 1.

Following Remark 1.4, we only prove the lower bound, which can be written as

$\beta(G)\leq\sum_{k=1}^{n}[\nu(A,\bm{\varphi}_{k})-(k-1)].$

Let $H_{k}=\mathrm{Hess}\lambda_{k}(0)$, as described in Theorem 2.7, so that
$\det(H_{k})\neq 0$ and $H_{k}$ has exactly $\nu(A,\bm{\varphi}_{k})-(k-1)$
negative eigenvalues, denoted by
$\mathrm{ind}(H_{k})=\nu(\bm{\varphi}_{k})-(k-1)$. We aim to show that

$\beta(G)\leq\sum_{k=1}^{n}\mathrm{ind}(H_{k}).$

Suppose, for the sake of contradiction, that
$\sum_{k=1}^{n}\mathrm{ind}(H_{k})=m<\beta$. Let
$V_{k}\subset\mathbb{R}^{\beta}$ be the $\mathrm{ind}(H_{k})$ dimensional
vector space on which $H_{k}$ is negative-definite. Since $H_{k}$ is
invertible, it is positive-definite on $V_{k}^{\perp}$, namely $\langle
H_{k}u,u\rangle>0$ for all non-zero $u\in V_{k}^{\perp}$. The vector space
$V=V_{1}+V_{2}+\ldots+V_{n}$ has dimension at most $m<\beta$, so
$\bigcap_{k=1}^{n}V_{k}^{\perp}$ has positive dimension, and hence contains at
least one non-zero vector $u$. For this vector, $\langle H_{k}u,u\rangle>0$
for all $k\in[n]$, which means that
$\langle\left(\sum_{k=1}^{n}H_{k}\right)u,u\rangle>0$. However, by
construction, $\mathrm{trace}(A_{\theta})$ is independent of
$\theta\in\mathbb{T}^{\beta}$, so its Hessian is the zero matrix,
$\sum_{k=1}^{n}H_{k}=\sum_{k=1}^{n}\mathrm{Hess}\lambda_{k}(0)=\mathrm{Hess}\left(\mathrm{trace}(A_{\theta})\right)=0$,
and therefore $\langle\left(\sum_{k=1}^{n}H_{k}\right)u,u\rangle=0$, providing
the needed contradiction. ∎

###  3.2. Proof of Theorem 1.3: Construction of extremizers $G_{n,\beta}$

######  Definition 3.1.

Given $n\in\mathbb{N}$ and $0<\beta\leq{n-1\choose 2}$, let
$G_{n,\beta}=([n],E)$, where

$E=\\{(1,i)\,|\,\ell+1<i\leq m\\}\cup\\{(i,j)\,|\,1<i<j\leq
m\\}\cup\\{(i,i+1)\,|\,m\leq i<n\\},$

and $m$ and $\ell$ are such that ${m-2\choose 2}<\beta\leq{m-1\choose 2}$ and
$\ell={m-1\choose 2}-\beta$ (notice that $\ell\leq m-2$). This graph is a
clique, with some edges removed, attached to a path (see Figure 1).

Here, and in what follows, we use the standard convention that ${n\choose
k}=0$ for all $n<k$. We note that $G_{n,\beta}$ only exists for $n>2$, as the
unique connected graphs on one and two vertices are both trees. In this
subsection, we construct a matrix $A\in\mathcal{S}(G_{n,\beta})$, for every
choice of $n\in\mathbb{N}$ and $0\leq\beta\leq{n-1\choose 2}$, that satisfies
(NCC) and has $\sum_{k=1}^{n}\nu(A,\bm{\varphi}_{k})={n\choose 2}+\beta$. This
construction illustrates the tightness of Theorem 1.3, thus completing its
proof, as the case $\beta(G)=0$ is simply Fiedler’s matrix tree theorem [12].
We first treat the regime ${n-2\choose 2}<\beta\leq{n-1\choose 2}$ (i.e.,
$m=n$).

######  Proposition 3.2.

Given $n\in\mathbb{N}$, $n>2$, and ${n-2\choose 2}<\beta\leq{n-1\choose 2}$,
the matrix $A\in\mathcal{S}(G_{n,\beta})$, defined below, has the following
properties:

  1. (1)

it has a choice of nowhere-vanishing eigenbasis
$\bm{\varphi}_{1},\ldots,\bm{\varphi}_{n}$ with total nodal count

$\sum_{k=1}^{n}\nu(A,\bm{\varphi}_{k})={n\choose 2}+\beta,$

  2. (2)

it satisfies the transversality condition of Lemma 2.4 with respect to
$W=\mathcal{S}(G_{n,\beta})$.

Therefore, there exists an $A^{\prime}\in\mathcal{S}(G_{n,\beta})$ arbitrarily
close $A$ that satisfies Nodal Count Condition 1.1 and has the same total
nodal count ${n\choose 2}+\beta$. The matrix $A$ is given by

$A=\blockarray{cccc}{\scriptstyle 1}&{\scriptstyle\ell}{\scriptstyle
n-\ell-1}\\\ \block{[ccc]c}(n-1)^{3}-\ell{n-1\choose 2}0-(n-1){n-1\choose
2}\mathbf{1}^{T}{\scriptstyle 1}\\\ 0(n-1){n\choose
2}I-(n-\ell-1)\mathbf{1}\mathbf{1}^{T}-\big{[}{n\choose
2}-\ell\big{]}\mathbf{1}\mathbf{1}^{T}{\scriptstyle\ell}\\\ -(n-1){n-1\choose
2}\mathbf{1}-\big{[}{n\choose 2}-\ell\big{]}\mathbf{1}\mathbf{1}^{T}{n\choose
2}^{2}I-\big{[}(n-1)^{2}-\ell\big{]}\mathbf{1}\mathbf{1}^{T}{\scriptstyle
n-\ell-1}\\\ $

where $\ell={n-1\choose 2}-\beta$, $I$ denotes the identity matrix, $0$
denotes the all-zeros vector, and $\mathbf{1}$ denotes the all-ones vector,
with the dimension of each clear from context. If $\ell=0$, then $A$ consists
only of the first and third rows and columns of the above block matrix.

###### Proof.

By inspection, $A$ admits the orthonormal eigendecomposition

$\displaystyle\lambda_{1}$ $\displaystyle=\ell{n\choose 2},$
$\displaystyle\bm{\varphi}_{1}$
$\displaystyle=\frac{1}{n}\begin{bmatrix}n-2\\\
2\mathbf{1}_{n-1}\end{bmatrix},$ $\displaystyle\lambda_{k}$
$\displaystyle=\begin{cases}(n-1){n\choose 2}&1<k\leq\ell+1\\\ {n\choose
2}^{2}&\ell+1<k\leq n\end{cases},$ $\displaystyle\bm{\varphi}_{k}$
$\displaystyle={n\choose 2}^{-1}\begin{bmatrix}n-1\\\
\mathbf{1}_{n-1}-{n\choose 2}\bm{e}_{k-1}\end{bmatrix},$

where $\bm{e}_{k}$ denotes the $k^{th}$ standard basis vector. The total nodal
count of the eigenbasis $\\{\bm{\varphi}_{1},\ldots,\bm{\varphi}_{n}\\}$ is

$\displaystyle\nu(A,\bm{\varphi}_{1})+\sum_{k=2}^{\ell+1}\nu(A,\bm{\varphi}_{k})+\sum_{k=\ell+2}^{n}\nu(A,\bm{\varphi}_{k})$
$\displaystyle=0+\ell(n-2)+(n-\ell-1)(n-1)$ $\displaystyle=(n-1)^{2}-\ell$
$\displaystyle={n\choose 2}+\beta(G).$

This proves property (1). To show property (2), note that the set of non-edges
of $G$ consists of all $(1j)$ with $j\in J=\\{2,\ldots,\ell+1\\}$.
Transversality condition (2.5) for $W=\mathcal{S}(G_{n,\beta})$ holds if, for
any matrix $C\in\mathcal{S}(n)$, there is a matrix $X\in\mathcal{A}(n)$ such
that $(XA-AX)_{1j}=C_{1j}$ for all $j\in J$. If $\ell=0$, then $J=\emptyset$
and we are done. Now, suppose $J$ is non-empty and consider
$X\in\mathcal{A}(n)$ with entries $X_{ij}=0$, $i<j$, for
$(i,j)\not\in\\{1\\}\times J$. In this case, for $i\in J$, we have

$\displaystyle(XA-AX)_{1i}$ $\displaystyle=X_{1i}(A_{ii}-A_{11})+\sum_{k\in
J,k\neq i}X_{1k}A_{ki}$ $\displaystyle=-(n-\ell-1)\bigg{[}{n-1\choose
2}X_{1i}+\sum_{k\in J}X_{1k}\bigg{]},$

implying that $(XA-AX)_{1i}$, $i\in J$, are linearly independent (linear)
functions in $(X_{1k})_{k\in J}$, so for any choice of $(C_{1,j})_{j\in J}$
there is an $X$ as above for which $(XA-AX)_{1i}=C_{1i}$ for all $i\in J$.
Therefore, the transversality condition holds, and by Lemma 2.4 there is
$A^{\prime}\in\mathcal{S}(G_{n,\beta})$ satisfying (NCC) with the same nodal
count as $A$. ∎

This treats the regime ${n-2\choose 2}<\beta\leq{n-1\choose 2}$. To produce
constructions $A\in\mathcal{S}(G_{n,\beta})$ for $0<\beta\leq{n-2\choose 2}$,
we prove an interpolation lemma that analyzes the effect on nodal count of
adding an edge of small weight between two graphs, one of which contains a
vertex of full degree.

######  Lemma 3.3.

Let $G_{1},G_{2}$ be two connected graphs with $n_{1}$ and $n_{2}$ vertices
respectively, and suppose that vertex $n_{1}$ of $G_{1}$ is connected to all
other vertices of $G_{1}$. Let $G$ be the graph on $n=n_{1}+n_{2}$ vertices
obtained by taking $G_{1}$ and $G_{2}$ and adding an edge between vertex
$n_{1}$ of $G_{1}$ and vertex $1$ of $G_{2}$, so that
$\beta(G)=\beta(G_{1})+\beta(G_{2})$. Given any two matrices
$A_{1}\in\mathcal{S}(G_{1})$ and $A_{2}\in\mathcal{S}(G_{2})$ that satisfy
Nodal Count Condition 1.1, have only non-positive entries, and have total
nodal count $\nu_{1}$ and $\nu_{2}$ respectively, there is a sufficiently
large spectral shift $s\gg 1$ such that, for all sufficiently small
$\epsilon>0$, the matrix

$A_{\epsilon}=\blockarray{ccc}{\scriptstyle n_{1}}&{\scriptstyle n_{2}}\\\
\block{[cc]c}A_{1}-sI-\epsilon\,\bm{e}_{n_{1}}\bm{e}_{1}^{T}{\scriptstyle
n_{1}}\\\ -\epsilon\,\bm{e}_{1}\bm{e}_{n_{1}}^{T}A_{2}{\scriptstyle n_{2}}\\\
\in\mathcal{S}(G)$

satisfies Nodal Count Condition 1.1 and has total nodal count equal to
$\nu_{1}+\nu_{2}+n_{1}n_{2}$.

###### Proof.

Let $A=(A_{1}-sI)\oplus A_{2}$ for a fixed sufficiently large $s$, (to be
determined later), and let
$B=-\bm{e}_{n_{1}}\bm{e}_{n_{1}+1}^{T}-\bm{e}_{n_{1}+1}\bm{e}_{n_{1}}^{T}$ so
that $A_{\epsilon}=A+\epsilon B$ as in the setting of Lemma 2.3. Note that by
taking $s$ sufficiently large, the spectra of $A_{1}-sI$ and $A_{2}$ are
disjoint, so $A$ has a simple spectrum. Lemma 2.2 provides a small interval
$(0,b)$ so that, for all $\epsilon\in(0,b)$, the eigenvalues of $A_{\epsilon}$
are simple and the support and signs of the eigenvectors are independent of
$\epsilon$. For $\epsilon\in(0,b)$, an eigenpair of $A_{\epsilon}$ has the
form $\lambda_{\epsilon}=\lambda^{(0)}+\epsilon\lambda^{(1)}+O(\epsilon^{2})$
and
$\bm{\varphi}_{\epsilon}=\bm{\varphi}^{(0)}+\epsilon\bm{\varphi}^{(1)}+O(\epsilon^{2})$.
We break our analysis into two cases, depending on whether $\lambda^{(0)}$ is
an eigenvalue of $A_{1}-sI$ or $A_{2}$.

First, we consider the case when $\lambda^{(0)}$ is an eigenvalue of
$A_{1}-sI$ with non-vanishing eigenvector $\bm{u}\in\mathbb{R}^{n_{1}}$, so
that $\bm{\varphi}^{(0)}=(\bm{u},0)^{T}$. Then, Lemma 2.3 and the block
structure of $A$ and $B$ implies that $\lambda^{(1)}=\langle
B\bm{\varphi}^{(0)},\bm{\varphi}^{(0)}\rangle=0$ and

$\bm{\varphi}^{(1)}=-(A-\lambda^{(0)}I)^{+}B\bm{\varphi}^{(0)}=\begin{bmatrix}0\\\
\bm{u}(n_{1})(A_{2}-\lambda^{(0)}I)^{-1}\bm{e}_{1}\end{bmatrix}.$

By making the shift $s$ sufficiently large, we ensure that $\lambda^{(0)}<0$
and $|\lambda^{(0)}|$ is strictly larger than the spectral radius of $A_{2}$,
so $A_{2}-\lambda^{(0)}I$ is an $M$-matrix. Because $A_{2}$ is irreducible
($G_{2}$ is connected), $(A_{2}-\lambda^{(0)}I)^{-1}$ is an entrywise positive
matrix and so $(A_{2}-\lambda^{(0)}I)^{-1}\bm{e}_{1}$ is a non-vanishing
positive vector [15, 8.3.P15]. We conclude, using Lemma 2.2, that
$\bm{\varphi}_{\epsilon}$ is non-vanishing, with constant sign on the vertices
$n_{1}\leq j\leq n_{1}+n_{2}$ and with the same sign pattern as $\bm{u}$ on
the vertices $1\leq j\leq n_{1}$. The nodal count is therefore

$\nu(A_{\epsilon},\bm{\varphi}_{\epsilon})=\nu(A_{1},\bm{u}).$

Next, we consider the case when $\lambda^{(0)}$ is an eigenvalue of $A_{2}$
with non-vanishing eigenvector $\bm{u}\in\mathbb{R}^{n_{2}}$, so that now
$\bm{\varphi}^{(0)}=(0,\bm{u})^{T}$. The same argument implies that

$\bm{\varphi}^{(1)}=\begin{bmatrix}\bm{w}\\\
0\end{bmatrix}\quad\text{with}\quad\bm{w}=\bm{u}(1)\left[(A_{1}-sI)-\lambda^{(0)}I\right]^{-1}\bm{e}_{n_{1}}.$

For notational convenience, let $\delta=(s+\lambda^{(0)})^{-1}$. Let $s$ be
sufficiently large so that $\delta>0$ and the spectral radius of $\delta
A_{1}$ is less than one. By expanding the inverse as a power series

$(I-\delta A_{1})^{-1}=\sum_{m=0}^{\infty}\delta^{m}A_{1}^{m}=I+\delta
A_{1}+O(\delta^{2}),$

we have

$\bm{w}=-\delta\bm{u}(1)(I-\delta
A_{1})^{-1}\bm{e}_{n_{1}}=-\delta\bm{u}(1)\left[\bm{e}_{n_{1}}+\delta
A_{1}\bm{e}_{n_{1}}+O(\delta^{2})\right].$

Because vertex $n_{1}$ of $G_{1}$ is connected to all other vertices of
$G_{1}$, $(A_{1})_{j,n_{1}}<0$ for all $j<n_{1}$. This means that, for
$\delta>0$ sufficiently small, $\bm{w}$ is non-vanishing with
$\mathrm{sign}(\bm{w}(n_{1}))=-\mathrm{sign}(\bm{u}(1))$ and
$\mathrm{sign}(\bm{w}(j))=\mathrm{sign}(\bm{u}(1))=-\mathrm{sign}(\bm{w}(n_{1}))$
for all $j<n_{1}$. Since the sign structure of $\bm{\varphi}_{\epsilon}$ is
equal to the sign structure of $\bm{w}$ on $G_{1}$ and $\bm{u}$ on $G_{2}$,
then its nodal count is that of $\bm{u}$ plus a sign change on the edge
$(n_{1},n_{1}+1)$ and sign changes on the $n_{1}-1$ edges $(j,n_{1})$,
$j<n_{1}$. Namely,

$\nu(A_{\epsilon},\bm{\varphi}_{\epsilon})=\nu(A_{2},\bm{u})+n_{1}.$

Summing the nodal count in each of the above two cases, we conclude that the
total nodal count of $A_{\epsilon}$ is $\nu_{1}+\nu_{2}+n_{1}n_{2}$. ∎

We are now prepared to complete the proof of Theorem 1.3. In particular, we
are prepared to prove that, for any $n\in\mathbb{N}$, $n>2$, and
$0<\beta\leq{n-1\choose 2}$, there is a matrix $A\in\mathcal{S}(G_{n,\beta})$
that satisfies (NCC) and has total nodal count ${n\choose 2}+\beta$ (recall,
the case $\beta=0$ is Fielder’s matrix tree theorem [12]).

###### Proof of Theorem 1.3: Part 2.

Let $m$ such that ${m-2\choose 2}<\beta\leq{m-1\choose 2}$, so that
$G_{n,\beta}$ is obtained by connecting the graph $G_{m,\beta}$ and an
$(n-m)$-vertex path graph. Proposition 3.2 produces a matrix
$A_{1}\in\mathcal{S}(G_{m,\beta})$ that satisfies (NCC), has non-positive off-
diagonal entries (and can be shifted to obtain negative diagonal entries), and
has total nodal count $\nu_{1}={m\choose 2}+\beta$. For the path graph $G_{2}$
on $n-m$ vertices, let $A_{2}\in\mathcal{S}(G_{2})$ be any non-positive matrix
with simple spectrum (such a matrix exists by genericity). By Fiedler’s matrix
tree theorem [12], $A_{2}$ must satisfy (NCC) and its total nodal count must
equal $\nu_{2}={n-m\choose 2}$. We may now apply Lemma 3.3 to
$G_{1}:=G_{m,\beta}$ and $G_{2}$ to obtain the matrix
$A_{\epsilon}\in\mathcal{S}(G_{n,\beta})$ which satisfies (NCC) and whose
total nodal count is

$\nu_{1}+\nu_{2}+m(n-m)={m\choose 2}+\beta+{n-m\choose 2}+m(n-m)={n\choose
2}+\beta.$

∎

###  3.3. Nodal count for $\mathcal{S}_{0}(G)$

In the case of $\mathcal{S}_{0}(G)$, we note that the bounds of Theorem 1.3
can still be tight. Here, we consider dense constructions in
$\mathcal{S}_{0}(K_{n})$ that achieve the bounds of Theorem 1.3. We consider
sparse zero-diagonal constructions, as well as alternate constructions for
$\mathcal{S}(G)$ for the regime $0<\beta\leq n-2$, in the following
subsection.

######  Proposition 3.4.

Let $n\in\mathbb{N}$, $n>2$, and $K_{n}$ be the complete graph on $n$
vertices. For $\epsilon>0$ sufficiently small, the matrix
$A^{\prime}=A_{\epsilon}-I\in\mathcal{S}_{0}(K_{n})$, with $A_{\epsilon}$
defined below, has the following properties:

  1. (1)

it has a choice of nowhere-vanishing eigenbasis
$\bm{\varphi}_{1},\ldots,\bm{\varphi}_{n}$ with total nodal count

$\sum_{k=1}^{n}\nu(A,\bm{\varphi}_{k})={n\choose 2}+\beta(K_{n}),$

  2. (2)

it satisfies the transversality condition of Lemma 2.4 with respect to
$W=\mathcal{S}_{0}(K_{n})$.

Therefore, there exists an $A^{\prime\prime}\in\mathcal{S}_{0}(K_{n})$
arbitrarily close to $A^{\prime}$ that satisfies Nodal Count Condition 1.1 and
has the same total nodal count ${n\choose 2}+\beta(K_{n})$. The matrix
$A_{\epsilon}$ is given by

$A_{\epsilon}=-\;\blockarray{cccc}{\scriptstyle 1}&{\scriptstyle
1}{\scriptstyle n-2}\\\
\block{[ccc]c}\epsilon^{2}1-\epsilon^{2}a\,\epsilon\,\bm{1}^{T}{\scriptstyle
1}\\\ 1-\epsilon^{2}\epsilon^{2}b\,\epsilon\,\bm{1}^{T}{\scriptstyle 1}\\\
a\,\epsilon\,\bm{1}b\,\epsilon\,\bm{1}\epsilon^{2}\bm{1}\bm{1}^{T}{\scriptstyle
n-2}\\\ $

where $a=(1+\frac{9\epsilon^{2}}{4+\epsilon^{2}})\frac{1}{2\sqrt{2}}$,
$b=(1-\frac{9\epsilon^{2}}{8+2\epsilon^{2}})\sqrt{2}$, and
$\mathbf{1}\in\mathbb{R}^{n-2}$ denotes the all-ones vector.

###### Proof.

Notice that $A_{\epsilon}=A^{\prime}+I$, so $A_{\epsilon}$ and $A^{\prime}$
share the same eigenvectors and same nodal count,
$\sum_{k=1}^{n}\nu(A_{\epsilon},\bm{\varphi}_{k})=\sum_{k=1}^{n}\nu(A^{\prime},\bm{\varphi}_{k})$.
The matrix $A_{\epsilon}$ is rank two, with the vector

$\bm{x}=\begin{bmatrix}(8-\epsilon^{2})(n-2)\epsilon\\\
(2-\epsilon^{2})(n-2)\epsilon\\\
-\sqrt{2}(4+\epsilon^{2})\,\bm{1}_{n-2}\end{bmatrix}$

in its nullspace, as well as any vector $(0,0,\bm{y}^{T})^{T}$ with
$\bm{y}^{T}\bm{1}=0$. For $\epsilon$ sufficiently small, the two eigenvectors
not in the nullspace are of the form
$\bm{\varphi}_{1}=\frac{1}{\sqrt{2}}(1,1,\bm{0}_{n-2})^{T}+O(\epsilon)$ and
$\bm{\varphi}_{n}=\frac{1}{\sqrt{2}}(1,-1,\bm{0}_{n-2}^{T})+O(\epsilon)$ by
2.1. By orthogonality to the nullspace, both are constant on the indices
$\\{3,\ldots,n\\}$. For $\epsilon$ sufficiently small,

$\mathrm{null}\left(\begin{bmatrix}\lambda+\epsilon^{2}&1-\epsilon^{2}\\\
1-\epsilon^{2}&\lambda+\epsilon^{2}\\\
a\,\epsilon&b\,\epsilon\end{bmatrix}\right)=0\qquad\text{for all
}\lambda\in\mathbb{R},$

implying that both $\bm{\varphi}_{1}$ and $\bm{\varphi}_{n}$ are also non-
vanishing on the indices $\\{3,\ldots,n\\}$. Therefore, for $\epsilon$
sufficiently small, $\bm{\varphi}_{1}$ and $\bm{\varphi}_{n}$ are non-
vanishing and have nodal counts $\nu(A_{\epsilon},\bm{\varphi}_{1})=0$ (by
Perron-Frobenius) and $\nu(A_{\epsilon},\bm{\varphi}_{n})=n-1$.

Now, consider the non-vanishing orthonormal basis

$\bm{\varphi_{k}}=\bm{x}+\frac{\|\bm{x}\|}{\sqrt{n-2}}\begin{bmatrix}0\\\ 0\\\
\bm{1}-(n-2)\bm{e}_{k-1}\end{bmatrix},\qquad k=2,\ldots,n-1,$

for the nullspace of $A_{\epsilon}$. For $k\in\\{2,\ldots,n-1\\}$, we have
$\bm{\varphi}_{k}(1)>0$, $\bm{\varphi}_{k}(2)>0$, $\bm{\varphi}_{k}(k+1)<0$,
and

$\bm{\varphi}_{k}(\ell)=-\sqrt{2}(4+\epsilon^{2})+\sqrt{2\,(4+\epsilon^{2})^{2}+(n-2)[(8-\epsilon^{2})^{2}+(2-\epsilon^{2})^{2}]}>0$

for all $\ell\neq 1,2,k+1$. Therefore,
$\nu(A_{\epsilon},\bm{\varphi}_{k})=n-1$ for all $k=2,\ldots n-1$, and so

$\sum_{k=1}^{n}\nu(A,\bm{\varphi}_{k})=(n-1)^{2}={n\choose 2}+{n-1\choose
2}={n\choose 2}+\beta(K_{n})$

for this eigenbasis of $A_{\epsilon}$. This proves property (1).

Next, we consider property (2). Because $G=K_{n}$ is the complete graph, the
orthogonal complement of $\mathcal{S}_{0}(K_{n})$ is the space of diagonal
matrices with trace zero. Transversality condition 2.5 holds if, for any
$\bm{v}\in\mathbb{R}^{n}$ with $\langle\bm{v},\textbf{1}\rangle=0$, there
exists an $X\in\mathcal{A}(n)$ such that
$(A^{\prime}X-XA^{\prime})_{jj}=\bm{v}(j)$ for all $j$. We calculate

$\frac{1}{2}(A^{\prime}X-XA^{\prime})_{jj}=(A^{\prime}X)_{jj}=\begin{cases}(\epsilon^{2}-1)X_{12}-a\,\epsilon\sum_{i=3}^{n}X_{1i}\
&\ \text{for }j=1\\\ (\epsilon^{2}-1)X_{21}-b\,\epsilon\sum_{i=3}^{n}X_{2i}\
&\ \text{for }j=2\\\ -a\,\epsilon X_{j1}-b\,\epsilon
X_{j2}-\epsilon^{2}\sum_{i=3}^{n}X_{ji}\ &\ \text{for }j>2\end{cases}.$

Let $X^{(i,j)}\in\mathcal{A}(n)$, $i<j$, be the anti-symmetric matrix with
$X^{(i,j)}_{ij}=-X_{ji}^{(i,j)}=1$ and equal to zero elsewhere. We note that,
for $j>2$,

$(A^{\prime}X^{(1,j)})_{ii}=\begin{cases}-a\,\epsilon\ &\ \text{for }i=1\\\
\phantom{-}a\,\epsilon\ &\ \text{for }i=j\\\ \phantom{-}0\ &\
\text{otherwise}\end{cases}\qquad\text{and}\qquad(A^{\prime}X^{(2,j)})_{ii}=\begin{cases}-b\,\epsilon\
&\ \text{for }i=2\\\ \phantom{-}b\,\epsilon\ &\ \text{for }i=j\\\
\phantom{-}0\ &\ \text{otherwise}\end{cases}.$

Any $\bm{v}\in\mathbb{R}^{n}$ with $\langle\bm{v},\textbf{1}\rangle=0$ is in
the span of the vectors
$\\{\bm{e}_{1}-\bm{e}_{j}\\}_{j=3}^{n}\cup\\{\bm{e}_{2}-\bm{e}_{j}\\}_{j=3}^{n}$,
completing the proof. ∎

Finally, we complement the above dense constructions with sparse ones, using
perturbations of tridiagonal matrices. In particular, we show that, even
though trees produce matrices with strongly controlled nodal edge count, we
can still produce perturbations that lead to fairly extreme behavior of the
nodal surplus. We do so by first producing an alternate tight construction for
Theorem 1.3 in the regime $0<\beta\leq n-2$, and then adjusting this
construction to obtain a constant diagonal construction with nodal surplus
$2\beta$ for a similar regime.

###  3.4. Path-based constructions for small $\beta$

In this subsection, we provide another class of extremizers based on a
different approach. We construct a tridiagonal matrix (a matrix supported on
the path graph $P_{n}$) whose eigenvectors have a special sign structure:
$\bm{\varphi}_{k}(i)\bm{\varphi}_{k}(i+2)$ is negative if and only if $i=k$.
The extremizer graphs $H_{n,\beta}$ are obtained by adding $\beta$ edges of
the form $(i,i+2)$. We also provide examples of zero-diagonal matrices for
which the bounds of Theorem 1.3 are nearly tight. We do so by constructing
zero-diagonal matrices on $P_{2n}$ that satisfy (NCC) and have a similar
eigenvector structure. The existence of matrices on $P_{2n}$ that satisfy
(NCC) is also a key ingredient in the proof of Theorem 1.6 in Section 4 (see
Remark 3.10 and the proof of Lemma 4.3 for details).

######  Definition 3.5.

Given $n\in\mathbb{N}$ and $0\leq\beta\leq n-2$, let $H_{n,\beta}=([n],E)$,
where

$\displaystyle E$ $\displaystyle=\\{(i,i+1)\,|\,1\leq
i<n\\}\cup\\{(i,i+2)\,|\,1\leq i\leq\beta\\}.$

This graph is a path with $\beta$ additional edges added, all between vertices
at path distance two (see Figure 5(a)).

(a) Extremizer $H_{n,\beta}$ with $n=8$ and $\beta=3$.

(b) Extremizer $H_{2n,\beta}^{(0)}$ with $n=8$ and $\beta=3$.

Figure 5. Example of extremizers from path constructions.

######  Definition 3.6.

Given $n\in\mathbb{N}$ and $0\leq\beta\leq 2(n-2)$, let
$H^{(0)}_{2n,\beta}=([2n],E_{0})$, where

$\displaystyle E_{0}$ $\displaystyle=\\{(i,i+1)\,|\,1\leq
i<2n\\}\cup\\{(i,i+4)\,|\,1\leq i\leq\beta\\}.$

This graph is a path with $\beta$ additional edges added, all between vertices
at path distance four (see Figure 5(b)).

In this subsection and the next, it is useful to count the number of sign
changes $A_{ij}\bm{\varphi}_{k}(i)\bm{\varphi}_{k}(j)>0$ per edge (over all
eigenvectors) rather than per eigenvector (over all edges). We introduce the
following notation.

######  Definition 3.7.

Let $(ij)$ be an edge of a graph $G$ and $A\in\mathcal{S}(G)$ with simple
eigenvalues and eigenbasis
$\bm{\varphi}_{1},\bm{\varphi}_{2},\ldots,\bm{\varphi}_{n}$. The contribution
of $(ij)$ to the total nodal count is denoted by

$\nu(A,(ij)):=\left|\\{k\in[n]:A_{ij}\bm{\varphi}_{k}(i)\bm{\varphi}_{k}(j)>0\\}\right|.$
(3.1)

######  Proposition 3.8.

Given $n\in\mathbb{N}$, $0\leq\beta\leq n-2$, $\epsilon>0$ sufficiently small,
and $\delta>0$ sufficiently small relative to $\epsilon$, let

$M=D(\bm{u})-\epsilon A-\delta B\in\mathcal{S}(H_{n,\beta}),$

where $\bm{u}=(1,2,\dots,n)^{T}$, $D(\bm{u})$ is the diagonal matrix with
$\bm{u}$ on the diagonal, $A$ is the adjacency matrix of the path $P_{n}$ on
$n$ vertices, and $B$ is the adjacency matrix of $H_{n,\beta}$. The matrix $M$
satisfies Nodal Count Condition 1.1, has eigenvectors
$\bm{\varphi}_{1},\ldots,\bm{\varphi}_{n}$ with sign structure

$\mathrm{sign}\big{(}\bm{\varphi}_{k}(\ell)\big{)}=\begin{cases}(-1)^{k-\ell}&\text{
for }\ell<k\\\ \,+1&\text{ for }\ell\geq k\end{cases},$

and therefore has total nodal count

${n\choose 2}+\beta.$

###### Proof.

We consider $M=M_{\epsilon}-\delta B$ as a $\delta>0$ perturbation of the
matrix $M_{\epsilon}:=D(\bm{u})-\epsilon A$ which is strictly supported on the
path $P_{n}$. We first show that, for sufficiently small $\epsilon$, the
matrix $M_{\epsilon}$ has simple eigenvalues and non-vanishing eigenvectors
$\bm{\psi}_{1},\ldots,\bm{\psi}_{n}$ with sign structure

$\mathrm{sign}\big{(}\bm{\psi}_{k}(\ell)\big{)}=\begin{cases}(-1)^{k-\ell}&\text{
for }\ell<k\\\ \,+1&\text{ for }\ell\geq k\end{cases}.$

The matrix $M_{\epsilon}$ is an $O(\epsilon)$ perturbation of $D(\bm{u})$,
which has distinct diagonal entries, and so $M_{\epsilon}$ has simple
eigenvalues for all $\epsilon\in(-T,T)$ for some $T>0$ (specified in Lemma
2.3). Let $\lambda_{\epsilon}=\sum_{i=0}^{\infty}\epsilon^{i}\lambda^{(i)}$ be
the $k^{th}$ smallest eigenvalue of $M_{\epsilon}$ and
$\bm{\psi}_{k}=\bm{\psi}_{\epsilon}=\sum_{i=0}^{\infty}\epsilon^{i}\bm{\psi}^{(i)}$
be the corresponding eigenvector, with $\lambda^{(0)}=k$ and
$\bm{\psi}^{(0)}=\bm{e}_{k}$. By Lemma 2.2, it suffices to analyze the value
of $\bm{\psi}^{(j)}(\ell)$ for the first $j$ for which
$\bm{\psi}^{(j)}(\ell)\neq 0$. Since $(D(\bm{u})-kI)^{+}$ is diagonal with
$(D(\bm{u})-kI)^{+}_{\ell\ell}=\frac{1}{\ell-k}$ for $\ell\neq k$, Equation
(2.2) implies that

$\bm{\psi}^{(j)}(\ell)=\frac{1}{\ell-k}\left[(A\bm{\psi}^{(j-1)})(\ell)+\sum_{i=1}^{j}\lambda^{(i)}\bm{\psi}^{(j-i)}(\ell)\right]\qquad\text{for
all }\ell\neq k.$

We claim that the support of $\bm{\psi}^{(j)}$ is contained in the interval
$[k-j,k+j]$. We proceed by induction on $j$. When $j=0$ we have
$\bm{\psi}^{(0)}=\bm{e}_{k}$. Now suppose the desired claim holds for
$\bm{\psi}^{(0)},\ldots,\bm{\psi}^{(j-1)}$. Then, for
$\ell\notin[k-j+1,k+j-1]$, the sum on the right-hand side of the above formula
vanishes, giving

$\displaystyle\bm{\psi}^{(j)}(\ell)=\frac{1}{\ell-k}\bm{\psi}^{(j-1)}(\ell+1)\
$ $\displaystyle\quad\text{for}\ 1\leq\ell\leq k-j,$
$\displaystyle\bm{\psi}^{(j)}(\ell)=\frac{1}{\ell-k}\bm{\psi}^{(j-1)}(\ell-1)\
$ $\displaystyle\quad\text{for}\ k+j\leq\ell\leq n,$

and so $\bm{\psi}^{(j)}$ is supported inside $[k-j,k+j]$. In addition, if
$k-j\in[n]$, then

$\mathrm{sign}\big{(}\bm{\psi}^{(j)}(k-j)\big{)}=-\mathrm{sign}\big{(}\bm{\psi}^{(j-1)}(k-(j-1))\big{)}=\ldots=(-1)^{j}\mathrm{sign}\big{(}\bm{\psi}^{(0)}(k)\big{)}=(-1)^{j},$

and, similarly, if $k+j\in[n]$, then

$\mathrm{sign}\big{(}\bm{\psi}^{(j)}(k+j)\big{)}=\mathrm{sign}\big{(}\bm{\psi}^{(j-1)}(k+(j-1))\big{)}=\ldots=\mathrm{sign}\big{(}\bm{\psi}^{(0)}(k)\big{)}=1.$

Therefore, $M_{\epsilon}$ has simple spectrum and non-vanishing eigenvectors
with the desired sign structure.

We now consider $M=M_{\epsilon}-\delta B$ as a $\delta$ perturbation of
$M_{\epsilon}$. For sufficiently small $\delta$ (with respect to the
eigenvalues of $M_{\epsilon}$ and $B$), $M$ has simple eigenvalues by Lemma
2.3, and non-vanishing eigenvectors $\bm{\varphi}_{1},\ldots,\bm{\varphi}_{n}$
with
$\mathrm{sign}(\bm{\varphi}_{k}(\ell))=\mathrm{sign}(\bm{\psi}_{k}(\ell))$ for
all $k,\ell\in[n]$ by Lemma 2.2. Because $M$ and $M_{\epsilon}$ have the same
sign pattern on $P_{n}$, the difference in the nodal count is only due to the
contribution of the $\beta$ additional $(i,i+2)$ edges. The sign structure of
the eigenvectors $\bm{\varphi}_{k}$ are such that
$\bm{\varphi}_{k}(i)\bm{\varphi}_{k}(i+2)<0$ if and only if $k=i+1$, implying
that $\nu(M,(i,i+2))=1$ (see Equation (3.1) for definition) for all
$(i,i+2)\in E(H_{n,\beta})$. Therefore,

$\displaystyle\sum_{k=1}^{n}\nu(M,\bm{\varphi}_{k})=$
$\displaystyle\sum_{k=1}^{n}\nu(M_{\epsilon},\bm{\psi}_{k})+\sum_{i=1}^{\beta}\nu(M,(i,i+2))$
$\displaystyle=$ $\displaystyle{n\choose 2}+\beta,$

where we have used the fact that, by Fiedler’s matrix tree theorem [12] (or
inspection), $\sum_{k=1}^{n}\nu(M_{\epsilon},\bm{\psi}_{k})={n\choose 2}$. ∎

Next, we build zero-diagonal matrices using a similar construction involving
the path graph $P_{2n}$ on $2n$ vertices. The matrices constructed are nearly
extremizers, with total nodal count equal to ${2n\choose 2}+2\beta$ (rather
than the lower bound ${2n\choose 2}+\beta$ of Theorem 1.3).

######  Proposition 3.9.

Given $n\in\mathbb{N}$, $0\leq\beta\leq 2(n-2)$, $\epsilon>0$ sufficiently
small, and $\delta>0$ sufficiently small relative to $\epsilon$, let

$M=D(\bm{u})\otimes\begin{bmatrix}0&1\\\ 1&0\end{bmatrix}-\epsilon A-\delta
B\in\mathcal{S}(H^{(0)}_{2n,\beta}),$

where $\bm{u}=-(n,n-1,\dots,1)^{T}$, $D(\bm{u})$ is the diagonal matrix with
$\bm{u}$ on the diagonal, $A$ is the adjacency matrix of the path $P_{2n}$ on
$2n$ vertices, and $B$ is the adjacency matrix of $H^{(0)}_{2n,\beta}$. Let
$\bm{\xi}_{k}\in\\{\pm 1\\}^{n}$, $k\in[n]$, be defined by

$\bm{\xi}_{k}(i)=\begin{cases}(-1)^{k-\ell}&\text{ for }\ell<k\\\ \,+1&\text{
for }\ell\geq k\end{cases}.$

The matrix $M$ satisfies Nodal Count Condition 1.1, has eigenvectors
$\bm{\varphi}_{1},\ldots,\bm{\varphi}_{2n}$ with sign structure

$\mathrm{sign}(\bm{\varphi}_{k})=\bm{\xi}_{k}\otimes\begin{bmatrix}1\\\
1\end{bmatrix}\qquad\text{and}\qquad\mathrm{sign}(\bm{\varphi}_{2n-k+1})=\bm{\xi}_{k}\otimes\begin{bmatrix}\phantom{-}1\\\
-1\end{bmatrix}$

for all $k\in[n]$, and therefore has total nodal count

${2n\choose 2}+2\beta.$

###### Proof.

The proof is nearly identical to that of Proposition 3.8: we first prove that
$M_{\epsilon}:=D(\bm{u})\otimes\begin{bmatrix}0&1\\\ 1&0\end{bmatrix}-\epsilon
A$ has simple eigenvalues and non-vanishing eigenvectors with the desired
$\bm{\xi}_{k}$ sign structure, and then show that $M=M_{\epsilon}-\delta B$
also has simple eigenvalues and non-vanishing eigenvectors with the same sign
structure. The only difference in the two proofs lies in the proof of the non-
vanishing eigenvectors and their sign structure for $M_{\epsilon}$, so we only
prove this part. In fact, using that $M_{\epsilon}$ has zero diagonal and is
supported on a bipartite graph, we later show that it is enough to prove that
the first $n$ eigenvectors (among the $2n$) are non-vanishing eigenvectors
with the desired sign structure.

Consider $M_{\epsilon}=D(\bm{u})\otimes\begin{bmatrix}0&1\\\
1&0\end{bmatrix}-\epsilon A$ as an $\epsilon$ perturbation of
$D(\bm{u})\otimes\begin{bmatrix}0&1\\\ 1&0\end{bmatrix}$ for $\epsilon$
sufficiently small and fix $k\in[n]$. Let
$\lambda_{\epsilon}=\sum_{i=0}^{\infty}\epsilon^{i}\lambda^{(i)}$ be the
$k^{th}$ eigenvalue of $M_{\epsilon}$ and
$\bm{\psi}_{\epsilon}=\sum_{i=0}^{\infty}\epsilon^{i}\bm{\psi}^{(i)}$ be the
corresponding eigenvector, with

$\lambda^{(0)}=-(n-k+1)\quad\text{and}\quad\bm{\psi}^{(0)}=\bm{e}_{k}\otimes\begin{bmatrix}1\\\
1\end{bmatrix},$

which is the $k^{th}$ eigenpair of $D(\bm{u})\otimes\begin{bmatrix}0&1\\\
1&0\end{bmatrix}$. For notational convenience, we use the indices

$x_{j}=2(k+j)-1\quad\text{and}\quad y_{j}=2(k+j),$

so that $\bm{\psi}^{(0)}$ is supported on the interval $[x_{0},y_{0}]$, and
$[2n]$ is the set of indices ranging from $x_{-(k-1)}$ to $y_{n-k}$. As in the
proof of Proposition 3.8, it suffices to prove the following claim for all
$j$.

Claim: The vector $\bm{\psi}^{(j)}$ is supported inside the interval
$[x_{-j},y_{j}]$, and

$\displaystyle x_{-j}\in[2n]\;\Rightarrow$
$\displaystyle\quad\mathrm{sign}\big{(}\bm{\psi}^{(j)}(x_{-j})\big{)}=\mathrm{sign}\big{(}\bm{\psi}^{(j)}(y_{-j})\big{)}=(-1)^{j},$
$\displaystyle y_{j}\in[2n]\;\Rightarrow$
$\displaystyle\quad\mathrm{sign}\big{(}\bm{\psi}^{(j)}(x_{j})\big{)}=\mathrm{sign}\big{(}\bm{\psi}^{(j)}(y_{j})\big{)}=+1.$

We proceed by induction on $j$. For $j=0$,
$\bm{\psi}^{(0)}=\bm{e}_{k}\otimes\begin{bmatrix}1\\\ 1\end{bmatrix}$ and the
claim holds. Now suppose that the desired claim holds for all vectors
$\bm{\psi}^{(0)},\ldots,\bm{\psi}^{(j-1)}$. Equation (2.2) gives the recursive
formula

$\bm{\psi}^{(j)}=\big{(}D(\bm{u})\otimes\begin{bmatrix}0&1\\\
1&0\end{bmatrix}-\lambda^{(0)}\big{)}^{+}\left[A\bm{\psi}^{(j-1)}+\sum_{i=1}^{j}\lambda^{(i)}\bm{\psi}^{(j-i)}\right]$

By our inductive hypothesis, the term
$\sum_{i=1}^{j}\lambda^{(i)}\bm{\psi}^{(j-i)}$ is supported inside the
interval $[x_{-j+1},y_{j-1}]$, and $A\bm{\psi}^{(j-1)}$ is supported inside
the larger interval
$[x_{-j+1}-1,y_{j-1}+1]=[y_{-j},x_{j}]\subset[x_{-j},y_{j}]$. Since
$\big{(}D(\bm{u})\otimes\begin{bmatrix}0&1\\\
1&0\end{bmatrix}-\lambda^{(0)}\big{)}^{+}$ is block diagonal with respect to
the blocks $\\{x_{i},y_{i}\\}$, $i=-(k-1),\ldots,n-k$, $\bm{\psi}^{(j)}$ is
supported inside $[x_{-j},y_{j}]$. Denote the $\\{x_{i},y_{i}\\}$ block of
$\big{(}D(\bm{u})\otimes\begin{pmatrix}0&1\\\
1&0\end{pmatrix}-\lambda^{(0)}\big{)}^{+}$ by $C_{i}$ and let
$r=-\lambda^{(0)}=n-k+1>0$. We have

$C_{j}=\frac{1}{r^{2}-(r-j)^{2}}\begin{pmatrix}r&r-j\\\
r-j&r\end{pmatrix}\quad\text{for }j\neq 0.$

Now, if $x_{-j}\in[2n]$, then

$\displaystyle\mathrm{sign}\left(\begin{bmatrix}\bm{\psi}^{(j)}(x_{-j})\\\
\bm{\psi}^{(j)}(y_{-j})\end{bmatrix}\right)$
$\displaystyle=\mathrm{sign}\left(C_{-j}\begin{bmatrix}[A\bm{\psi}^{(j-1)}](x_{-j})\\\
[A\bm{\psi}^{(j-1)}](y_{-j})\end{bmatrix}\right)$
$\displaystyle=\mathrm{sign}(\bm{\psi}^{(j-1)}(x_{-j+1}))\,\mathrm{sign}\left(C_{-j}\begin{bmatrix}0\\\
1\end{bmatrix}\right)$
$\displaystyle=(-1)^{j-1}\mathrm{sign}\left(\frac{1}{r^{2}-(r+j)^{2}}\begin{bmatrix}r+j\\\
r\end{bmatrix}\right)=(-1)^{j}\begin{bmatrix}1\\\ 1\end{bmatrix},$

where we used the inductive hypothesis that
$\mathrm{sign}(\bm{\psi}^{(j-1)}(x_{-j+1}))=(-1)^{j-1}$. Now suppose
$y_{j}\in[2n]$. Then $r>r-j>0$ and, by our inductive hypothesis,
$\mathrm{sign}\big{(}[A\bm{\psi}^{(j-1)}](x_{j})\big{)}=1$ and
$[A\bm{\psi}^{(j-1)}](y_{j})=0$, so

$\displaystyle\mathrm{sign}\left(\begin{bmatrix}\bm{\psi}^{(j)}(x_{j})\\\
\bm{\psi}^{(j)}(y_{j})\end{bmatrix}\right)$
$\displaystyle=\mathrm{sign}\left(C_{j}\begin{bmatrix}1\\\
0\end{bmatrix}\right)$
$\displaystyle=\mathrm{sign}\left(\frac{1}{r^{2}-(r-j)^{2}}\begin{bmatrix}r\\\
r-j\end{bmatrix}\right)=\begin{bmatrix}1\\\ 1\end{bmatrix}.$

This proves our inductive step and, hence, our desired claim holds for all
$j$. Therefore, if $\bm{\psi}_{1},\ldots,\bm{\psi}_{2n}$ are the eigenvalues
of $M_{\epsilon}$, then
$\mathrm{sign}(\bm{\psi}_{k})=\bm{\xi}_{k}\otimes\begin{pmatrix}1\\\
1\end{pmatrix}$ for all $k\in[n]$. The sign structure for the other $n$
eigenvectors follows from noting that $M_{\epsilon}$ has zero diagonal and is
strictly supported on a bipartite graph with bipartition
$\\{1,3,\ldots,2n-1\\}$ and $\\{2,4,\ldots,n\\}$. This implies that
$\bm{\psi}_{2n-k+1}$, the eigenvector for the $k^{th}$ largest eigenvalue, has
sign structure $\bm{\xi}_{k}\otimes\begin{pmatrix}1\\\ -1\end{pmatrix}$. Thus
we have proved that $M_{\epsilon}$ has simple eigenvalues with the desired
sign structure.

What remains is to consider the total nodal count. As in the proof of
Proposition 3.8, for $\delta$ sufficiently small, the eigenvectors
$\bm{\varphi}_{1},\ldots,\bm{\varphi}_{2n}$ of $M$ have the same sign
structure as $\bm{\psi}_{1},\ldots,\bm{\psi}_{2n}$. The total nodal count of
$M$ equals the total nodal count of $M_{\epsilon}$, which is ${2n\choose 2}$,
plus $\sum_{i=1}^{\beta}\nu(M,(i,i+4))$ (see Equation (3.1) for definition).
The calculated sign structure has the property that

$\bm{\varphi}_{k}(i)\bm{\varphi}_{k}(i+4)<0\quad\text{if and only if}\quad
k=\lceil i/2\rceil+1\ \text{or}\ k=2n-\lceil i/2\rceil.$

Therefore, $\nu(M,(i,i+4))=2$ for every $(i,i+4)\in E(H^{(0)}_{2n,\beta})$,
and the total nodal count equals

${2n\choose 2}+2\beta.$

∎

######  Remark 3.10.

In the proof of Proposition 3.9, we provided a zero-diagonal matrix
$M_{\epsilon}:=D(\bm{u})\otimes\begin{bmatrix}0&1\\\ 1&0\end{bmatrix}-\epsilon
A\in\mathcal{S}_{0}(P_{2n})$ that satisfies the Nodal Count Condition 1.1. The
existence of such a matrix is a key ingredient in the proof of Lemma 4.3, a
crucial lemma in the proof of Theorem 1.6.

###  3.5. Nodal count for bipartite graphs

Here we show, in contrast to Theorem 1.3, that if $G$ is bipartite and
$A\in\mathcal{S}_{0}(G)$ satisfies (NCC), then its nodal count per edge is
exactly $n/2$, implying that its average nodal count is exactly
$\frac{|E(G)|}{2}=\frac{n-1}{2}+\frac{\beta(G)}{2}$.

######  Proposition 3.11.

Suppose $G=([n],E)$ is bipartite, $n$ is even, and $A\in\mathcal{S}_{0}(G)$
satisfies Nodal Count Condition 1.1. Then $\nu(A,(ij))=n/2$ for any edge
$(i,j)\in G$ and the average nodal count is

$\frac{1}{n}\sum_{(ij)\in
E(G)}\nu(A,(ij))=\frac{|E(G)|}{2}=\frac{n-1}{2}+\frac{\beta(G)}{2}.$

###### Proof.

Since $G$ is bipartite, there exists $u\in\\{-1,1\\}^{n}$ such that
$u_{i}u_{j}=-1$ for any edge $(i,j)\in G$. If $A\in\mathcal{S}_{0}(G)$, then
$A_{ij}u_{i}u_{j}=-A_{ij}$ for any $i,j$. Let $U=\mathop{\rm diag}(u)$ so that
it is real orthogonal with $U^{-1}=U$, and $UAU=-A$. In particular, if $v$ is
an eigenvector with eigenvalue $\lambda$, then $Uv$ is an eigenvector with
eigenvalue $-\lambda$. Suppose that $A$ satisfies (NCC), then all the
eigenvalues are simple and come in pairs of $\pm\lambda$, and since there is
an even number of them then $0$ is not an eigenvalue of $A$. So, for any
eigenvector $v$, the vector $Uv$ is a different eigenvector and
$\mathrm{sign}(Uv(i)Uv(j))=-\mathrm{sign}(v(i)v(j))$,
$\nu(i,j,v)+\nu(i,j,Uv)=1$ for every edge $(i,j)\in G$. It follows that
$\nu(A,(ij))=n/2$ for every edge. ∎

######  Remark 3.12.

Note that a bipartite $G$ with an $A\in\mathcal{S}_{0}(G)$ that satisfies
(NCC) must have a perfect matching, and hence $n$ is even, otherwise
$\det(A)=0$ for all $A\in\mathcal{S}_{0}(G)$ (see [17, p. 307] for example),
in which case Theorem 4.1 says any $A\in\mathcal{S}_{0}(G)$ fails to satisfy
(NCC).

##  4\. The graph characterization of the Nodal Count Condition for
$\mathcal{S}_{0}(G)$

Constant diagonal matrices are quite important in practice, as this class
includes the adjacency matrix and normalized Laplacian matrix of a graph and
the unnormalized Laplacian of a regular graph. However, unlike for
$\mathcal{S}(G)$, where it is known that for any $G$ graph a generic matrix in
$\mathcal{S}(G)$ satisfies (NCC), the case of matrices in $\mathcal{S}_{0}(G)$
satisfying (NCC) is more subtle. For instance, there exist graphs for which no
matrix in $\mathcal{S}_{0}(G)$ satisfies (NCC). The following theorem is a
restatement of Theorem 1.6 and provides a full characterization. Recall
Definition 1.5: a graph $G$ is said to be _sub-determinantal_ if $\det(A)=0$
for all $A\in\mathcal{S}_{0}(G)$, and said to be _determinantal_ otherwise.

######  Theorem 4.1.

For any simple connected graph $G$ exactly one of the following two holds:

  1. (1)

If $G$ is determinantal, then the set of matrices in $\mathcal{S}_{0}(G)$ that
fail to satisfy Nodal Count Condition 1.1 is a closed (semi-algebraic) set of
positive co-dimension.

  2. (2)

If $G$ is sub-determinantal, then any $A\in\mathcal{S}_{0}(G)$ fails to
satisfy Nodal Count Condition 1.1 in one of the following ways:

    1. (a)

Either $\lambda=0$ is a multiple eigenvalue of $A$, or

    2. (b)

$\lambda=0$ is a simple eigenvalue and the corresponding eigenvector
$\bm{\varphi}$ satisfies $\bm{\varphi}(i)\bm{\varphi}(j)=0$ for every edge
$(ij)\in E(G)$.

We prove this theorem by decomposing it into the following four lemmas.

######  Lemma 4.2.

For any simple connected graph $G$, either all matrices in
$\mathcal{S}_{0}(G)$ fail to satisfy Nodal Count Condition 1.1, or it is
satisfied generically. That is, if $B\subset\mathcal{S}_{0}(G)$ is the set of
matrices that fail to satisfy Nodal Count Condition 1.1, then either
$B=\mathcal{S}_{0}(G)$ or $B$ is a closed semi-algebraic set of positive co-
dimension.

###### Proof.

Assuming that there exists some $A^{\prime}\in\mathcal{S}_{0}(G)\backslash B$,
it is enough to show that the set $B$ is a closed semi-algebraic set of
positive co-dimension.

Recall that the entries of the adjugate matrix $\mathrm{adj}(A-\lambda I)$ are
(up to signing) the minors of $A-\lambda I$, and are therefore polynomials in
$A$ and $\lambda$. The rank of $\mathrm{adj}(A-\lambda I)$ is $n$ (full-rank)
when $\lambda$ is not an eigenvalue, it is the zero matrix
$\mathrm{adj}(A-\lambda I)=0$ when $\lambda$ is a repeated eigenvalue, and it
has rank one if $\lambda$ is a simple eigenvalue. In particular, if $\lambda$
is simple with normalized eigenvector $\bm{\varphi}$, then
$\mathrm{adj}(A-\lambda I)=c\bm{\varphi}\bm{\varphi}^{T}$ for a non-zero
scalar $c\neq 0$. This means that

$B=\\{A\in\mathcal{S}_{0}(G)\,|\,\exists\,k,i\in[n]\ \text{s.t.}\
\mathrm{adj}(A-\lambda_{k}(A)I)_{ii}=0\\}.$

It is clear that $B$ is closed, since $A\mapsto\lambda_{k}(A)$ is continuous,
so $A\mapsto\mathrm{adj}(A-\lambda_{k}(A)I)_{ii}$ is continuous for any
$i,k\in[n]$, and $B$ is the union of their zero sets. By Tarski-Seidenberg,
$B$ is also semi-algebraic. To be more specific, consider the algebraic sets

$\displaystyle X=$
$\displaystyle\\{(A,\lambda)\in\mathcal{S}_{0}(G)\times\mathbb{R}\,|\,\det(A-\lambda
I)=0\\},$ $\displaystyle X_{\mathrm{mult}}=$ $\displaystyle\\{(A,\lambda)\in
X\,|\,\mathrm{discriminant}(A)=0\\},$ $\displaystyle X_{i}=$
$\displaystyle\\{(A,\lambda)\in X\,|\,\mathrm{adj}(A-\lambda I)_{ii}=0\\}\
\text{for all }\ i\in[n].$

Consider the projection $\pi:X\to\mathcal{S}_{0}(G)$, so that

$B_{\mathrm{mult}}:=\\{A\in\mathcal{S}_{0}(G)\,|\,\mathrm{discriminant}(A)=0\\}=\pi(X_{\mathrm{mult}})$

is algebraic, and $B_{i}=\pi(X_{i})$ is semi-algebraic by Tarski-Seidenberg,
and therefore so is $B=B_{\mathrm{mult}}\cup[\cup_{i=1}^{n}B_{i}]$. By
assumption, there exists $A^{\prime}\in\mathcal{S}_{0}(G)\backslash B$, so
$B_{\mathrm{mult}}$ has positive codimension as an algebraic strict subset.
What remains is to show that $B_{i}$ has positive codimension. Assume, for the
sake of contradiction, that this is not the case for some $B_{i}$. Then, there
is an open neighborhood $O\subset B_{i}\setminus B_{\mathrm{mult}}$, and up to
going to a sub-neighborhood, there is $k\in[n]$ such that
$\mathrm{adj}(A-\lambda_{k}(A)I)_{ii}=0$ for all $A\in O$. Let $A\in O$ and
$A^{\prime}\notin B$ as assumed, and consider the one-parameter family
$A_{t}=tA^{\prime}+(1-t)A$ for $t\in[0,1]$. Then there is an analytic function
$\lambda(t)$, which is an eigenvalue of $A_{t}$ for all $t$ and equals
$\lambda_{k}(A_{t})$ for small $t$, by Lemma 2.1, and so
$t\mapsto\mathrm{adj}(A-\lambda(t)I)_{ii}=0$ is the zero function, and in
particular $\mathrm{adj}(A^{\prime}-\lambda(1)I)_{ii}=0$ and
$\det(A^{\prime}-\lambda(1)I)=0$, in contradiction to our assumption. ∎

######  Lemma 4.3.

If $G=C_{2n+1}$ is an odd cycle, then a generic matrix in $\mathcal{S}_{0}(G)$
satisfies Nodal Count Condition 1.1.

###### Proof.

By Lemma 4.2 it is enough to construct a matrix $A\in\mathcal{S}_{0}(G)$ that
satisfies (NCC). We do so by making use of a matrix
$\hat{A}\in\mathcal{S}_{0}(P_{2n})$, where $P_{2n}$ is the path on $2n$
vertices, with $\det(\hat{A})\neq 0$ that satisfies (NCC); we already
constructed such a matrix in Subsection 3.4 (see Remark 3.10). Consider the
matrix

$A_{\epsilon}=A+\epsilon B\in\mathcal{S}_{0}(C_{2n+1}),\qquad
A=\blockarray{ccc}{\scriptstyle 2n}&{\scriptstyle 1}\\\
\block{[cc]c}\hat{A}0{\scriptstyle 2n}\\\ 00{\scriptstyle 1}\\\ ,\qquad
B=\blockarray{ccc}{\scriptstyle 2n}&{\scriptstyle 1}\\\
\block{[cc]c}0\bm{e}_{1}+c\bm{e}_{2n}{\scriptstyle 2n}\\\
\bm{e}^{T}_{1}+c\bm{e}^{T}_{2n}0{\scriptstyle 1}\\\ ,$

where $c$ is a non-zero constant that is not equal to
$-\bm{\varphi}(1)/\bm{\varphi}(2n)$ for any eigenvector $\bm{\varphi}$ of
$\hat{A}$. The matrix $A_{\epsilon}$ is strictly supported on
$\mathcal{S}_{0}(C_{2n+1})$. Lemma 2.2 provides a small interval $(0,b)$ so
that, for all $\epsilon\in(0,b)$, the eigenvalues of $A_{\epsilon}$ are simple
and the support and signs of the eigenvectors are independent of $\epsilon$.
In order to prove $A_{\epsilon}$, $\epsilon\in(0,b)$, satisfies (NCC), all
that remains is to show that its eigenvectors do not vanish at an entry. For
$\epsilon\in(0,b)$, an eigenpair of $A_{\epsilon}$ has the form
$\lambda_{\epsilon}=\lambda^{(0)}+\epsilon\lambda^{(1)}+O(\epsilon^{2})$ and
$\bm{\varphi}_{\epsilon}=\bm{\varphi}^{(0)}+\epsilon\bm{\varphi}^{(1)}+O(\epsilon^{2})$.
We have $\lambda^{(1)}=\langle
B\bm{\varphi}^{(0)},\bm{\varphi}^{(0)}\rangle=0$ for all eigenvectors,
simplifying the analysis. We treat two cases, depending on whether
$\lambda^{(0)}=0$.

First, consider an arbitrary eigenpair of $\hat{A}$, say
$(\lambda_{\epsilon},\bm{\varphi}_{\epsilon})$, where $\lambda^{(0)}\neq 0$.
As $\mathrm{sign}(\bm{\varphi}_{\epsilon})$ is independent of $\epsilon$ in
this region, and $\bm{\varphi}^{(0)}(i)\neq 0$ for all $i\neq 2n+1$, it
suffices to consider only $\bm{\varphi}^{(1)}(2n+1)$. By Lemma 2.3,

$\bm{\varphi}^{(1)}=-(A-\lambda^{(0)}I)^{+}B\bm{\varphi}^{(0)},$

and so

$\bm{\varphi}^{(1)}(2n+1)=\frac{1}{\lambda^{(0)}}(\bm{\varphi}^{(0)}(1)+c\bm{\varphi}^{(0)}(2n))\neq
0.$

Next, consider the case $(\lambda_{\epsilon},\bm{\varphi}_{\epsilon})$, where
$\lambda^{(0)}=0$. In this setting $\bm{\varphi}^{(0)}=\bm{e}_{2n+1}$, and,
again, by Lemma 2.3, $\bm{\varphi}^{(1)}=-A^{+}B\bm{e}_{2n+1}$. This implies
that

$\bm{\varphi}^{(1)}(i)=\hat{A}^{-1}_{i,1}+c\hat{A}^{-1}_{i,2n}\quad\text{ for
all }i\in[2n].$

By Proposition 2.5, $\hat{A}^{-1}_{i,1}\neq 0$ if and only if $i$ is even, and
$A^{-1}_{i,2n}\neq 0$ if and only if $i$ is odd, so $\bm{\varphi}^{(1)}(i)\neq
0$ for all $i\in[2n]$, completing the proof. ∎

######  Lemma 4.4.

If $G$ is determinantal, namely, there exists
$A^{\prime}\in\mathcal{S}_{0}(G)$ with $\det(A^{\prime})\neq 0$, then there is
a (vertex) disjoint union of edges and odd cycles of $G$ that cover all
vertices, and a generic matrix in $\mathcal{S}_{0}(G)$ satisfies Nodal Count
Condition 1.1.

###### Proof.

By Lemma 4.2 it is enough to construct a matrix
$A_{\epsilon}\in\mathcal{S}_{0}(G)$ that satisfies (NCC), which we do by a
clever choice of $A$ with simple eigenvalues and $B$ such that we can show
$A_{\epsilon}=A+\epsilon B$ satisfies (NCC). In fact, it is enough to
construct a matrix $A_{\epsilon}\in\mathcal{S}_{0}(G)$ with simple eigenvalues
and non-vanishing eigenvectors that is only strictly supported on a subgraph
of $G$, as we can always perturb again by taking
$A_{\epsilon,\delta}=A_{\epsilon}+\delta B^{\prime}$ with $B^{\prime}$ being
the adjacency matrix of $G$, so that for small enough $\delta>0$,
$A_{\epsilon,\delta}\in\mathcal{S}_{0}(G)$ is strictly supported on $G$, and
satisfies (NCC) by Lemma 2.2 and Lemma 2.3.

Now, because there exists an $A^{\prime}\in\mathcal{S}_{0}(G)$ with
$\det(A^{\prime})\neq 0$, at least one term in the Leibniz expansion of the
determinant is non-zero, i.e., $\prod_{j=1}^{n}A^{\prime}_{j,\sigma(j)}\neq 0$
for some permutation $\sigma$. Because $A^{\prime}$ has zero-diagonal,
$\sigma$ has no $1$-cycles (i.e., $\sigma$ is a dearrangement). By associating
each cycle of $\sigma$ of length $k$ with the analogous undirected cycle
subgraph of $G$ of length $k$ (where a $2$-cycle is simply an edge), $\sigma$
encodes a vertex-disjoint cycle cover of $G$ (where an edge is considered a
$2$-cycle). Any disjoint cycle cover can be converted to one with only odd
cycles and edges, as every cycle of even length can be disjointly covered
using alternating edges. Therefore, $G$ has a vertex-disjoint cycle cover
consisting only of edges and odd cycles. Let us consider one such cover
$H_{1},\ldots,H_{s}$, and denote by $V_{1},\ldots,V_{s}$ the corresponding
partition of the vertex set $[n]$ of $G$, where each subset $V_{i}$
corresponds to the vertex set of $H_{i}$ (where, again, $H_{i}$ either an edge
or an odd cycle).

We are now prepared to construct a matrix $A_{\epsilon}\in\mathcal{S}_{0}(G)$
that satisfies (NCC) using the cycle cover associated with
$V_{1},\ldots,V_{s}$. Let $A$ be block diagonal with respect to
$V_{1},\ldots,V_{s}$, and denote the matrix $A$ restricted to the entries of
$V_{i}$ by $A_{i}$. We require that each $A_{i}\in\mathcal{S}_{0}(H_{i})$,
$i=1,\ldots,s$, satisfies (NCC) and has $\det(A_{i})\neq 0$, and that the
matrices have disjoint spectra, i.e.,
$\Lambda(A_{i})\cap\Lambda(A_{j})=\emptyset$ for all $i\neq j$. For a single
edge, we note that $\begin{pmatrix}0&1\\\ 1&0\end{pmatrix}$ satisfies (NCC)
and has non-zero determinant, and Lemma 4.3 provides such a matrix for an odd
cycle of any length. Disjoint spectra can be obtained simply by properly
scaling each $A_{i}$, as none of these matrices has a zero eigenvalue.
Furthermore, by properly scaling each $A_{i}$, we may assume that each pair
$\lambda$ and $A_{i}$, $\lambda\in\Lambda(A_{j})$, $j\neq i$, is such that
$\lambda$ is not in the finite set of Proposition 2.6 associated with $A_{i}$.

Let $\tilde{E}\subset E(G)$ denote a minimal set of edges needed to be added
to the cover $H_{1}+H_{2}+\ldots+H_{s}$ so that

$\tilde{H}=([n],\tilde{E}\cup E(H_{1})\cup\dots\cup E(H_{s}))$

is a connected subgraph of $G$. One important consequence of the minimality of
$\tilde{E}$ is that, for any path $P_{ij}:=v_{0}\,v_{1}\,\dots\,v_{k}$ between
$H_{i}$ and $H_{j}$ (i.e., $v_{0}\in V_{i}$, $v_{k}\in V_{j}$, and
$v_{p}\not\in V_{i}\cup V_{j}$ for $1<p<k$), $v_{0}$, $v_{k}$, and
$E(P_{ij})\cap\tilde{E}$ are independent of the choice of path. Therefore, we
may define the distance $d_{H}(V_{i},V_{j})$ between $H_{i}$ and $H_{j}$ to be
$|E(P_{ij})\cap\tilde{E}|$ for a path $P_{ij}$ between $H_{i}$ and $H_{j}$ in
$\tilde{H}$, and we may speak of a unique last vertex $v_{k}\in V_{j}$ of
$P_{ij}$. Let $B$ be the binary matrix with $B_{ij}=1$ if and only if
$(ij)\in\tilde{E}$. We define $A_{\epsilon}=A+\epsilon B$.

By construction, $A$ has simple eigenvalues, and so, by Lemma 2.2, there is a
small interval $(0,b)$ so that for all $\epsilon\in(0,b)$, the eigenvalues of
$A_{\epsilon}$ are simple and the support and signs of the eigenvectors are
independent of $\epsilon$. What remains is to prove that the eigenvectors of
$A_{\epsilon}$ do not vanish at a vertex. Consider an arbitrary eigenpair of
$A$ and extend it to an eigenpair of $A_{\epsilon}$ with a power series
$\lambda_{\epsilon}=\sum_{i=0}^{\infty}\epsilon^{i}\lambda^{(i)}$ and
$\bm{\varphi}_{\epsilon}=\sum_{i=0}^{\infty}\epsilon^{i}\bm{\varphi}^{(i)}$.
Because $A$ is block diagonal with simple eigenvalues, $\bm{\varphi}^{(0)}$ is
strictly supported on a single block, without loss of generality, given by
$V_{1}$. According to Lemma 2.2, it is enough to show that for every vertex
$i$ there is some $\ell$ such that $\bm{\varphi}^{(\ell)}(i)\neq 0$. We will
do so by inducting on the subsets $V_{1},\ldots,V_{s}$ according to distance
$d_{H}(V_{1},V_{j})$. Let $J_{0}=V_{1}$, $J_{r}\subset[n]$ equal the union of
all $V_{j}$ at distance $d_{H}(V_{1},V_{j})=r$, and $J_{\leq
R}=\cup_{r=0}^{R}J_{r}$.

To complete the proof, we prove by induction that $\bm{\varphi}^{(\ell)}$ is
non-zero on the vertex set $J_{\ell}$ and supported inside the ball
$J_{\leq\ell}$. By construction, this is true for $\ell=0$. For our inductive
step, suppose that our statement holds for all $\ell^{\prime}<\ell$. Because
$\langle B\bm{\varphi}^{(0)},\bm{\varphi}^{(0)}\rangle=0$, Equation (2.3)
provides a recursive formula for $\bm{\varphi}^{(\ell)}$ (when $\ell=1$
neglect the sum)

$\bm{\varphi}^{(\ell)}=-(A-\lambda^{(0)}I)^{+}B\bm{\varphi}^{(\ell-1)}+\sum_{m=2}^{\ell}\lambda^{(m)}(A-\lambda^{(0)}I)^{+}\bm{\varphi}^{(\ell-m)}.$

We note that $(A-\lambda^{(0)}I)^{+}$ is block-diagonal with respect to
$V_{1},\ldots,V_{s}$, and so
$(A-\lambda^{(0)}I)^{+}\bm{\varphi}^{(\ell^{\prime})}$ is supported in the
ball $J_{\leq\ell^{\prime}}$ for all $\ell^{\prime}<\ell$. Therefore,

$\bm{\varphi}^{(\ell)}|_{J_{r}}=-\left((A-\lambda^{(0)}I)^{+}B\bm{\varphi}^{(\ell-1)}\right)|_{J_{r}}\qquad\text{
for all }\ r\geq\ell.$

Because the matrix $B$ is non-zero precisely on the edge set $\tilde{E}$,
$B\bm{\varphi}^{(\ell-1)}$ is supported on $J_{\leq\ell}$ and so
$\bm{\varphi}^{(\ell)}|_{J_{r}}$ is zero for $r>\ell$. What remains is to
prove that $\bm{\varphi}^{(\ell)}|_{J_{\ell}}$ does not vanish at a vertex.

Consider an arbitrary $V_{j}$ in $J_{\ell}$, and let $\tilde{v}\in V_{j}$
denote the unique last vertex of every path $P_{1j}$ from $V_{1}$ to $V_{j}$
with interior vertices not in $V_{1}\cup V_{j}$ (as described above). Then
$B\bm{\varphi}^{(\ell-1)}|_{V_{j}}$ is non-zero at $\tilde{v}$ and equal to
zero elsewhere. By Proposition 2.6 and our choice of scaling for each $A_{i}$,
$(A_{j}-\lambda^{(0)}I)^{-1}$ is entry-wise non-zero. Therefore,
$\bm{\varphi}^{(\ell)}|_{J_{r}}$ is non-vanishing, completing the proof. ∎

######  Lemma 4.5.

If $G$ is sub-determinantal, namely, $\det(A)=0$ for all
$A\in\mathcal{S}_{0}(G)$, then, for any $A\in\mathcal{S}_{0}(G)$,

  1. (1)

Either $\lambda=0$ is a multiple eigenvalue, or

  2. (2)

$\lambda=0$ is a simple eigenvalue and the corresponding eigenvector
$\bm{\varphi}$ satisfies $\bm{\varphi}(i)\bm{\varphi}(j)=0$ for every edge
$(ij)\in E(G)$.

###### Proof.

Suppose $\det(A)=0$ for all $A\in\mathcal{S}_{0}(G)$. Let $(ij)\in E(G)$ and
$E_{ij}$ be the symmetric matrix with entries $E_{ij}=E_{ji}=1$ and zero
elsewhere. Jacobi’s formula for the derivative of the determinant gives

$\frac{\partial}{\partial
t}\det(A+tE_{ij})|_{t=0}=\mathrm{trace}(E_{ij}\mathrm{adj}(A))=(\mathrm{adj}(A))_{ij}+(\mathrm{adj}(A))_{ji}=2(\mathrm{adj}(A))_{ij}.$

Since $A+tE_{ij}\in\mathcal{S}_{0}(G)$ for all $t$,
$t\mapsto\det(A+tE_{ij})\equiv 0$ and so $\frac{\partial}{\partial
t}\det(A+tE_{ij})|_{t=0}=2(\mathrm{adj}(A))_{ij}=0$. Since $\det(A)=0$, this
means that either $\lambda=0$ is multiple eigenvalue, or it is simple with an
eigenvector that satisfies $(\bm{\varphi}\bm{\varphi}^{T})_{ij}=0$. ∎

######  Corollary 4.6.

Let $G$ be a bipartite graph (any tree for example). If $G$ has no perfect
matching, then any $A\in\mathcal{S}_{0}(G)$ fails to satisfy Nodal Count
Condition 1.1.

###### Proof.

This follows from the fact that the determinant of any
$A\in\mathcal{S}_{0}(G)$ is zero if $G$ has no perfect matching. See [17, p.
307] for example. ∎

##  5\. Vanishing Eigenvectors and Eigenvalue Multiplicity

The set of matrices in $\mathcal{S}(G)$ that fails to satisfy (NCC) is an
algebraic subvariety of positive co-dimension, as stated in Theorem 1.6,
implying that any matrix $A\in\mathcal{S}(G)$ with either a repeated
eigenvalue or an eigenvector that vanishes at a vertex is arbitrarily close to
another matrix in $\mathcal{S}(G)$ that does satisfy (NCC). However, due to
the fact that many matrices in practice fail to satisfy this condition, a
great deal of research has been devoted to understanding what happens in this
case, particularly regarding nodal domains (see, for instance, [10, 11, 14,
18, 21, 20, 24] and the references cited therein). Here we make a number of
brief observations regarding the total nodal count when (NCC) fails. We break
our analysis into three cases: matrices with an eigenvector that vanishes at a
vertex, matrices with a repeated eigenvalue, and, finally, matrices with
“both”, by which we mean that there is a repeated eigenvalue with no nowhere-
vanishing eigenvector.

######  Remark 5.1.

If a matrix has a repeated eigenvalue $\lambda$ with eigenspace $V$, for any
$i\in[n]$ there is always a $\bm{\varphi}\in V$ with $\bm{\varphi}(i)=0$.
There is a nowhere-vanishing $\bm{\varphi}\in V$ if and only if for any
$i\in[n]$ there is some $\bm{\varphi}^{\prime}\in V$ with
$\bm{\varphi}^{\prime}(i)\neq 0$. Therefore, in the presence of multiplicity,
the relevant question is not whether a matrix admits some “bad” eigenbasis,
which is always the case, but, rather, whether there exists a “good” (i.e.,
nowhere-vanishing) eigenbasis.

###  5.1. Vanishing eigenvectors

Suppose $A\in\mathcal{S}(G)$ has simple eigenvalues
$\lambda_{1}<\ldots<\lambda_{n}$, but there exists an eigenvector
$\bm{\varphi}_{k}$ with $\bm{\varphi}_{k}(i)=0$ for some $i\in[n]$. In this
case, what constitutes an edge where an eigenvector changes sign is ambiguous,
and is not necessarily covered by Theorem 1.3. We give the following
illustrative example.

######  Example 5.2 (bounds fail for weak/strong formulation).

The matrix

$A=\begin{bmatrix}\phantom{-}0&-1&\phantom{-}0&\phantom{-}0\\\
-1&\phantom{-}0&-1&-1\\\ \phantom{-}0&-1&\phantom{-}1&-1\\\
\phantom{-}0&-1&-1&\phantom{-}1\end{bmatrix}$

has eigenvalues $-\sqrt{3}$, $0$, $\sqrt{3}$, $2$, with corresponding
eigenvectors

$\begin{bmatrix}1\\\ \sqrt{3}\\\ 1\\\
1\end{bmatrix},\;\begin{bmatrix}\phantom{-}2\\\ \phantom{-}0\\\ -1\\\
-1\end{bmatrix},\;\begin{bmatrix}\phantom{-}1\\\ -\sqrt{3}\\\ \phantom{-}1\\\
\phantom{-}1\end{bmatrix},\;\begin{bmatrix}\phantom{-}0\\\ \phantom{-}0\\\
-1\\\ \phantom{-}1\end{bmatrix}.$

If $A$ had non-vanishing eigenvectors, Theorem 1.3 would imply that the total
nodal count would be between $7$ and $9$. However, if we count the total
number of edges where $A_{ij}\bm{\varphi}_{k}(i)\bm{\varphi}_{k}(j)>0$ over
all $k$, there are only $4$. Counting edges where
$A_{ij}\bm{\varphi}_{k}(i)\bm{\varphi}_{k}(j)\geq 0$ also does not fix this
issue, as we obtain a total count of $10$.

This issue is due to the fact that a vertex with a value of zero may
simultaneously count as a “positive” vertex with respect to some neighbors and
a “negative” vertex to others, leading to abnormally large nodal counts.
However, because this property is of positive co-dimension, we can immediately
make the following claim (in the spirit of [20, Theorem 3.6], [18, Theorem
1.3]).

######  Proposition 5.3.

Suppose $A\in\mathcal{S}(G)$ is strictly supported on $G$ and has simple
eigenvalues with corresponding eigenvectors
$\bm{\varphi}_{1},\ldots,\bm{\varphi}_{n}$. Then there exists a choice of
signings $\bm{\xi}_{1},\ldots,\bm{\xi}_{n}\in\\{\pm 1\\}^{n}$ with
$\mathrm{sign}(\bm{\xi}_{k}(i))=\mathrm{sign}(\bm{\varphi}_{k}(i))$ for all
$\bm{\varphi}_{k}(i)\neq 0$ for which the total nodal count
$\sum_{k=1}^{n}\nu(A,\bm{\xi}_{k})$ satisfies the bounds of Theorem 1.3.

###### Proof.

Given a matrix $B\in\mathcal{S}(G)$, the eigenvalues and eigenvectors of
$A_{\epsilon}=A+\epsilon B$ are real analytic functions of
$\epsilon\in\mathbb{R}$, so $A_{\epsilon}$ either fails to satisfy (NCC) for
all $\epsilon\in\mathbb{R}$, or it satisfies (NCC) for all $\epsilon\in(0,T)$
for some $T>0$ depending on $B$. There must be some $B\in\mathcal{S}(G)$ for
which the latter case holds, as the non-existence of such a matrix would
contradict Theorem 1.6. Hence, we may choose some $B\in\mathcal{S}(G)$ such
that $A_{\epsilon}$ satisfies (NCC) for all $\epsilon\in(0,T)$, for some
$T>0$. Lemma 2.2 provides a possibly smaller interval $(0,b)$ such that the
sign structure of the eigenvectors of $A_{\epsilon}$ is independent of
$\epsilon\in(0,b)$ and agrees with that of the non-zero entries of
$\bm{\varphi}_{1},\ldots,\bm{\varphi}_{n}$. We let
$\bm{\xi}_{1},\ldots,\bm{\xi}_{n}$ equal the sign structure of the
eigenvectors of $A_{\epsilon}$, $0<\epsilon<\min\\{b,T\\}$, implying that the
total nodal count satisfies the bounds of Theorem 1.3, as $A_{\epsilon}$
satisfies (NCC). ∎

###  5.2. Eigenvalue Multiplicity

When a matrix $A\in\mathcal{S}(G)$ has a repeated eigenvalue, e.g.,
$\lambda_{k}=\lambda_{k+1}$ for some $k$, there is no longer a notion of a
total nodal count, as there is no longer a fixed eigenbasis. The question is
then whether $A$ has a nowhere-vanishing eigenbasis, and if so, does its nodal
count obey the bounds of Theorem 1.3. In this subsection, we provide two
sufficient conditions on $A$ under which every choice of a non-vanishing
eigenbasis satisfies the bounds of Theorem 1.3. However, we first describe a
naive perturbative approach. If we perturb $A$ to a nearby $A^{\prime}$ that
satisfies (NCC), in which case the bounds of Theorem 1.3 hold for
$A^{\prime}$, and we manage to do so without changing the sign structure of
the chosen eigenbasis of $A$, then the initial eigenbasis must satisfy the
bounds of Theorem 1.3. The caveat is, as seen in Lemma 2.2 part (1), that such
a perturbation dictates the initial eigenbasis, not the other way around. To
illustrate this problem, we show that diagonal perturbations, which are
commonly used to resolve multiplicity, can produce sign structures that do not
match that of any eigenbasis of the original matrix. For the resolution of
eigenvalue multiplicity via diagonal perturbations see Minami-type estimates
in the theory of Anderson localization [9] or the DAD theorem of Garza-Vargas
[13] for details.

######  Example 5.4 (diagonal perturbations can ruin eigenspace sign
structure).

Let $A$ be the adjacency matrix of the cycle $C_{4}$ on $4$ vertices. The
nullspace of $A$

$\mathrm{null}(A)=\\{(a,b,-a,-b)^{T}\,|\,a,b\in\mathbb{R}\\}$

is of dimension two, and the vectors $\bm{x}=(1,0-1,0)^{T}/\sqrt{2}$ and
$\bm{y}=(0,1,0,-1)^{T}/\sqrt{2}$ form an orthonormal basis for
$\mathrm{null}(A)$. Consider the matrix $A_{\epsilon}=A+\epsilon
D\in\mathcal{S}(C_{4})$, where $D=\mathrm{diag}(D_{1},D_{2},D_{3},D_{4})$,
$\|D\|_{2}=1$, is a diagonal matrix, and $D_{1}+D_{3}\neq D_{2}+D_{4}$. The
restriction of $D$ to $\mathrm{null}(A)$ is diagonalized by $\bm{x}$ and
$\bm{y}$, with

$\begin{bmatrix}\bm{x}^{T}\\\
\bm{y}^{T}\end{bmatrix}D\begin{bmatrix}\bm{x}&\bm{y}\end{bmatrix}=\begin{bmatrix}(D_{1}+D_{3})/2&0\\\
0&(D_{2}+D_{4})/2\end{bmatrix},$

so, by Lemma 2.2 part (1) and Lemma 2.3 part (3), $A_{\epsilon}$ has simple
eigenvalues for all $\epsilon\in(0,b)$ for some $b>0$, with real analytic
eigenvectors,

$\displaystyle\bm{x}_{\epsilon}$
$\displaystyle=\bm{x}+\epsilon\bigg{[}A^{+}\big{(}\tfrac{D_{1}+D_{3}}{2}I-D\big{)}\bm{x}-\frac{\bm{x}^{T}DA^{+}D\bm{y}}{\frac{D_{1}+D_{3}}{2}-\frac{D_{2}+D_{4}}{2}}\,\bm{y}\bigg{]}+O(\epsilon^{2}),$
$\displaystyle\bm{y}_{\epsilon}$
$\displaystyle=\bm{y}+\epsilon\bigg{[}A^{+}\big{(}\tfrac{D_{2}+D_{4}}{2}I-D\big{)}\bm{y}-\frac{\bm{x}^{T}DA^{+}D\bm{y}}{\frac{D_{2}+D_{4}}{2}-\frac{D_{1}+D_{3}}{2}}\,\bm{x}\bigg{]}+O(\epsilon^{2}),$

of corresponding eigenvalues
${}_{\bm{x}}\lambda_{\epsilon}=\epsilon(D_{1}+D_{3})/2+O(\epsilon^{2})$, and
${}_{\bm{y}}\lambda_{\epsilon}=\epsilon(D_{2}+D_{4})/2+O(\epsilon^{2})$. We
have $A^{+}=\frac{1}{4}A$, and, after a series of calculations, note that

$\bm{x}_{\epsilon}=\frac{1}{\sqrt{2}}\begin{bmatrix}1\\\
\frac{\epsilon(D_{1}-D_{3})(2D_{4}-D_{1}-D_{3})}{4(D_{1}-D_{2}+D_{3}-D_{4})}\\\
-1\\\
\frac{\epsilon(D_{1}-D_{3})(2D_{2}-D_{1}-D_{3})}{4(D_{1}-D_{2}+D_{3}-D_{4})}\end{bmatrix}+O(\epsilon^{2})\quad\text{and}\quad\bm{y}_{\epsilon}=\frac{1}{\sqrt{2}}\begin{bmatrix}\frac{\epsilon(D_{2}-D_{4})(2D_{3}-D_{2}-D_{4})}{4(-D_{1}+D_{2}-D_{3}+D_{4})}\\\
1\\\
\frac{\epsilon(D_{2}-D_{4})(2D_{1}-D_{2}-D_{4})}{4(-D_{1}+D_{2}-D_{3}+D_{4})}\\\
-1\end{bmatrix}+O(\epsilon^{2}).$

For $D$ fixed and $\epsilon$ sufficiently small, the sign structure of
$\bm{x}_{\epsilon}$ and $\bm{y}_{\epsilon}$ matches that of eigenvectors in
$\mathrm{null}(A)$, i.e.,
$\mathrm{sign}(\bm{x}_{\epsilon})=\mathrm{sign}(\bm{\psi}_{1})$ and
$\mathrm{sign}(\bm{y}_{\epsilon})=\mathrm{sign}(\bm{\psi}_{2})$ for some
$\bm{\psi}_{1},\bm{\psi}_{2}\in\mathrm{null}(A)$, only if

$\displaystyle\mathrm{sign}(2D_{4}-D_{1}-D_{3})$
$\displaystyle=-\mathrm{sign}(2D_{2}-D_{1}-D_{3})\quad\text{and}$
$\displaystyle\mathrm{sign}(2D_{3}-D_{2}-D_{4})$
$\displaystyle=-\mathrm{sign}(2D_{1}-D_{2}-D_{4}).$

Without loss of generality, suppose that $D_{1}=1$ and $D_{2}>D_{4}$. By
inspection,

$\mathrm{vol}(\\{(D_{2},D_{3},D_{4})\in[-1,1]^{3}\,|\,2D_{4}\leq 1+D_{3}\leq
2D_{2}\text{ and }2D_{3}\leq D_{2}+D_{4}\leq 2\\})=10/9,$

and so the fraction of diagonal matrices $D$ with $\|D\|_{2}=1$ that satisfies
both of the above conditions is $5/18$, implying that $72.\bar{2}\%$ of the
possible diagonal perturbations (measured w.r.t. the uniform measure on the
cube $\|D\|_{2}=1$) of $A$ do not preserve the sign structure of the
nullspace.

######  Remark 5.5.

The above example can be generalized to any cycle on $4n$ vertices, with
$n\in\mathbb{N}$, in which case

$\mathrm{null}(A)=\\{\bm{\varphi}\in\mathbb{R}^{4n}\,|\,\bm{\varphi}(i)=-\bm{\varphi}(j)\text{
for all }i\equiv 0,j\equiv 2\bmod 4\text{ and }i\equiv 1,j\equiv 3\bmod 4\\},$

and, for any diagonal $D$, the restriction $D|_{\mathrm{null}(A)}$ is
diagonalized by the orthonormal basis
$\frac{1}{\sqrt{2n}}\bm{1}_{n}^{T}\otimes(1,0,-1,0)^{T}$,
$\frac{1}{\sqrt{2n}}\bm{1}_{n}^{T}\otimes(0,1,0,-1)^{T}$. Computing the exact
proportion of diagonal perturbations $A+\epsilon D$, $\|D\|_{2}=1$, that do
not preserve the sign structure of the nullspace is significantly more
involved in this case, and left to the interested reader.

Nevertheless, we can provide sufficient conditions on a matrix
$A\in\mathcal{S}(G)$ such that any nowhere-vanishhing eigenbasis of $A$ would
satisfy the bounds of Theorem 1.3. For instance, Berkolaiko’s rank-one
argument [6], though stated for simple eigenvalues, still holds in this case
and provides an interesting consequence of multiplicity.

######  Lemma 5.6.

Let $A\in\mathcal{S}(G)$ be strictly supported on $G$ with eigenvalues

$\lambda_{1}\leq\ldots\leq\lambda_{k-1}<\lambda_{k}=\ldots=\lambda_{k+m-1}<\lambda_{k+m}\leq\ldots\leq\lambda_{n}.$

Any nowhere-vanishing eigenvector $\bm{\varphi}$ in the eigenspace of
$\lambda_{k}=\ldots=\lambda_{k+m-1}$ has

$\nu(A,\bm{\varphi})\geq k+(m-1)-1.$

###### Proof.

Consider the spectral counting function $\lambda\mapsto N(A,\lambda)$ which
equals to the number of eigenvalues of $A$ (counting with multiplicity) that
are no larger than $\lambda$. We aim to show that

$\nu(A,\bm{\varphi})\geq N(A,\lambda)-1,$

for any nowhere-vanishing $\bm{\varphi}\in\ker(A-\lambda I)$. We proceed by
induction on the first Betti number $\beta(G)$ using Berkolaiko’s rank-one
argument (see [6]). When $\beta(G)=0$, $A$ is an acyclic irreducible matrix,
and Fielder’s matrix tree theorem states that if $\lambda$ has a nowhere-
vanishing eigenvector $\bm{\varphi}$, then $\lambda$ is simple and
$\nu(\bm{\varphi}_{k})=N(A,\lambda)-1$ [12, Corollary 2.5]. Now, let
$\beta(G)>0$ and suppose that our desired result holds for all connected
graphs $H$ with $\beta(H)<\beta(G)$. Let $A\in\mathcal{S}(G)$ be strictly
supported on $G$, $\lambda$ be an eigenvalue of $A$, possibly multiple, with a
nowhere-vanishing eigenvector $\bm{\varphi}$. Because $\beta(G)>0$, there
exists an edge $(ij)\in E(G)$ such that its removal does not disconnect $G$.
Let $H$ be the graph obtained from $G$ by removing $(ij)$, so that
$\beta(H)=\beta(G)-1$. We construct a rank one matrix

$R=A_{ij}\bm{\varphi}_{k}(i)\bm{\varphi}_{k}(j)\big{[}\mathbf{e}_{i}/\bm{\varphi}_{k}(i)-\mathbf{e}_{j}/\bm{\varphi}_{k}(j)\big{]}\big{[}\mathbf{e}_{i}/\bm{\varphi}_{k}(i)-\mathbf{e}_{j}/\bm{\varphi}_{k}(j)\big{]}^{T},$

such that $R\bm{\varphi}=0$, and the matrix $A^{\prime}=A+R$ has
$A^{\prime}_{ij}=0$ and $A^{\prime}_{rs}=A_{rs}$ for any other $r\neq s$. So
$A^{\prime}$ is strictly supported on the graph $H$, and
$A^{\prime}\bm{\varphi}=\lambda\bm{\varphi}$. Hence the induction hypothesis
gives

$\displaystyle\nu(A,\bm{\varphi})$
$\displaystyle=\nu(A^{\prime},\bm{\varphi})+1$ $\displaystyle\geq$
$\displaystyle\;N(A^{\prime},\lambda)\qquad$ if $\displaystyle\quad
A_{ij}\bm{\varphi}_{k}(i)\bm{\varphi}_{k}(j)>0,\ \text{and}$ (5.1)
$\displaystyle\nu(A,\bm{\varphi})$
$\displaystyle=\nu(A^{\prime},\bm{\varphi})$ $\displaystyle\geq$
$\displaystyle\;N(A^{\prime},\lambda)-1\qquad$ if $\displaystyle\quad
A_{ij}\bm{\varphi}_{k}(i)\bm{\varphi}_{k}(j)<0.$ (5.2)

If $A_{ij}\bm{\varphi}_{k}(i)\bm{\varphi}_{k}(j)<0$ then $R$ is negative semi-
definite and, by Weyl’s inequality, $N(A^{\prime},\lambda)=N(A+R,\lambda)\geq
N(A,\lambda)$, and so (5.2) gives $\nu(A,\bm{\varphi})\geq N(A,\lambda)-1$ as
needed. If, on the other hand,
$A_{ij}\bm{\varphi}_{k}(i)\bm{\varphi}_{k}(j)>0$ then $R$ is rank-one and, by
Weyl’s inequality, $N(A^{\prime},\lambda)=N(A+R,\lambda)\geq N(A,\lambda)-1$,
and so (5.1) gives $\nu(A,\bm{\varphi})\geq N(A,\lambda)-1$ as needed. ∎

This implies the following bounds for matrices with eigenvalue multiplicity.

######  Proposition 5.7.

Let $A\in\mathcal{S}(G)$ be strictly supported on $G$ with $r$ distinct
eigenvalues of multiplicities $m_{1},\ldots,m_{r}$, $\sum_{i=1}^{r}m_{i}=n$.
Then the total nodal count, for any non-vanishing eigenbasis
$\bm{\varphi}_{1},\ldots,\bm{\varphi}_{n}$ of $A$, is bounded by

${n\choose 2}+\sum_{i=1}^{r}{m_{r}\choose
2}\leq\sum_{k=1}^{n}\nu(A,\bm{\varphi}_{k}).$

In particular, if $\sum_{i=1}^{r}{m_{r}\choose 2}\geq\beta(G)$, then the
bounds of Theorem 1.3 hold for any non-vanishing eigenbasis.

###### Proof.

Let $\bm{\varphi}_{1},\ldots,\bm{\varphi}_{n}$ be a nowhere vanishing
eigenbasis of $A$, and suppose that
$\lambda_{k-1}<\lambda_{k}=\ldots=\lambda_{k+m-1}<\lambda_{k+m}$. Then, by
Lemma 5.6,

$\sum_{j=k}^{k+m-1}\left[\nu(A,\bm{\varphi}_{j})-(j-1)\right]\geq\sum_{j=k}^{k+m-1}\left[k+m-2-(j-1)\right]=\sum_{i=1}^{m}(m-i)={m\choose
2},$

and therefore
$\sum_{j=1}^{n}\left[\nu(A,\bm{\varphi}_{j})-(j-1)\right]\geq\sum_{i=1}^{r}{m_{r}\choose
2}$ as needed. ∎

We conclude that when $\sum_{i=1}^{r}{m_{i}\choose 2}\geq\beta(G)$, Theorem
1.3 holds for all non-vanishing eigenbases. Next, we show that when
$\sum_{i=1}^{r}{m_{i}\choose 2}\leq\beta(G)+n-1=|E(G)|$, the bounds of Theorem
1.3 might still hold for all non-vanishing eigenbasis due to transversality.

######  Proposition 5.8.

If $A\in\mathcal{S}(G)$ is strictly supported on $G$ and satisfies the
transversality condition of Lemma 2.4, then, for any non-vanishing eigenbasis
of $A$, say $\bm{\varphi}_{1},\ldots,\bm{\varphi}_{n}$, the total nodal count
$\sum_{k=1}^{n}\nu(A,\bm{\varphi}_{k})$ satisfies the bounds from Theorem 1.3.
Explicitly:

  1. (1)

The transversality condition of Lemma 2.4 is that

$\mathcal{S}(G)+\\{AX-XA:X\in\mathcal{A}(n)\\}=\mathcal{S}(n).$

  2. (2)

A necessary condition for transversality is

$\dim(\mathcal{S}(G))+\dim(\\{AX-
XA:X\in\mathcal{A}(n)\\})\geq\dim(\mathcal{S}(n)).$

If $A$ has $r$ distinct eigenvalues of multiplicities $m_{1},\ldots,m_{r}$,
$\sum_{i=1}^{r}m_{i}=n$, this means that

$|E(G)|=\beta(G)-1+n\geq\sum_{i=1}^{r}{m_{i}\choose 2}.$

###### Proof.

The statement follows directly from Lemma 2.4 and Theorem 1.3. ∎

###  5.3. Vanishing Eigenvectors and Eigenvalue Multiplicity

We now consider the case where there is eigenvalue multiplicity and there is
no non-vanishing orthogonal basis for the corresponding eigenspace. This
setting is the most complex, and in general can have quite unusual behavior.
The star graph is the standard example of the issues that can arise.

######  Example 5.9 (most choices of eigenbasis do not satisfy Fiedler’s
matrix tree theorem).

Let $A$ be the adjacency matrix of $G$, the star graph on $n$ vertices. The
rank of $A$ is two and $A$ has nullspace

$\mathrm{null}(A)=\\{\bm{x}\in\mathbb{R}^{n}\,|\,\bm{x}(1)=0,\,\bm{x}^{T}\bm{1}=0\\}.$

Any perturbation $A^{\prime}$ of this matrix with simple eigenvalues and non-
vanishing eigenvectors must satisfy Fiedler’s matrix tree theorem [12], and so
must have nodal count $\nu(A^{\prime},\bm{\varphi}_{k})=k-1$ for all
$k\in[n]$. However, we note that, of all the orthonormal bases of
$\mathrm{null}(A)$, an exponentially small proportion of them have an
eigenvector $\bm{\varphi}$ that, upon arbitrarily small perturbation (to, say,
$\bm{\varphi}_{\epsilon}$), can satisfy
$\nu(A^{\prime},\bm{\varphi}_{\epsilon})=1$ (see [21, Lemma 4.4] and [18,
Figure 2] for more details). This implies that the sign structure of the large
majority of eigenbases of $A$ are not achievable by any
$A^{\prime}\in\mathcal{S}(G)$ satisfying (NCC).

## Acknowledgements

The second author thanks Mehtaab Sawhney for interesting conversions regarding
diagonal perturbations. The first author was supported by the Simons
Foundation Grant 601948, DJ. The authors thank Louisa Thomas for improving the
style of presentation. The authors thank Adi Alon for assistance with graphic
design.

## References

  * [1] Lior Alon, Ram Band, and Gregory Berkolaiko.  Nodal statistics on quantum graphs.  Communications in Mathematical Physics, 362:909–948, 2018.
  * [2] Lior Alon, Ram Band, and Gregory Berkolaiko.  Universality of nodal count distribution in large metric graphs.  Experimental Mathematics, pages 1–35, 2022.
  * [3] Lior Alon and Mark Goresky.  Morse theory for discrete magnetic operators and nodal count distribution for graphs.  Journal of Spectral Theory, 2023.
  * [4] Lior Alon and Mark Goresky.  Nodal count for a random signing of a graph with disjoint cycles.  arXiv preprint arXiv:2403.01033, 2024.
  * [5] Ram Band.  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(2007):20120504, 2014.
  * [6] Gregory Berkolaiko.  A lower bound for nodal count on discrete and metric graphs.  Communications in mathematical physics, 278(3):803–819, 2008.
  * [7] Gregory Berkolaiko.  Nodal count of graph eigenfunctions via magnetic perturbation.  Analysis & PDE, 6(5):1213–1233, 2013.
  * [8] Yves Colin de Verdière.  Magnetic interpretation of the nodal defect on graphs.  Analysis & PDE, 6(5):1235–1242, 2013.
  * [9] Jean-Michel Combes, François Germinet, and Abel Klein.  Generalized eigenvalue-counting estimates for the Anderson model.  Journal of Statistical Physics, 135:201–216, 2009.
  * [10] E. Brian Davies, Graham M.L. Gladwell, Josef Leydold, and Peter F. Stadler.  Discrete nodal domain theorems.  Linear Algebra Appl., 336(1):51–60, 2001.
  * [11] E. Brian Davies, Josef Leydold, and Peter F Stadler.  Discrete nodal domain theorems.  arXiv preprint math/0009120, 2000.
  * [12] Miroslav Fiedler.  Eigenvectors of acyclic matrices.  Czechoslovak Mathematical Journal, 25(4):607–618, 1975.
  * [13] Jorge Garza-Vargas.  Minimum eigenvalue gap for the model DAD.  2023\.
  * [14] Graham ML Gladwell and H Zhu.  Courant’s nodal line theorem and its discrete counterparts.  Quarterly Journal of Mechanics and Applied Mathematics, 55(1):1–15, 2002.
  * [15] Roger A Horn and Charles R Johnson.  Matrix analysis.  Cambridge university press, 2012.
  * [16] Tosio Kato.  Perturbation theory for linear operators, volume 132.  Springer Science & Business Media, 2013.
  * [17] László Lovász and Michael D Plummer.  Matching theory, volume 367.  American Mathematical Soc., 2009.
  * [18] Theo McKenzie and John Urschel.  Nodal decompositions of a symmetric matrix.  arXiv preprint arXiv:2305.10598, 2023.
  * [19] Franz Rellich.  Perturbation theory of eigenvalue problems.  CRC Press, 1969.
  * [20] John C Urschel.  Nodal decompositions of graphs.  Linear Algebra and its Applications, 539:60–71, 2018.
  * [21] John C Urschel and Ludmil T Zikatanov.  Spectral bisection of graphs and connectedness.  Linear Algebra and its Applications, 449:1–16, 2014.
  * [22] Riaz A Usmani.  Inversion of a tridiagonal Jacobi matrix.  Linear Algebra and its Applications, 212(213):413–414, 1994.
  * [23] Harald K Wimmer.  Rellich’s perturbation theorem on hermitian matrices of holomorphic functions.  Journal of mathematical analysis and applications, 114(1):52–54, 1986.
  * [24] Hao Xu and Shing-Tung Yau.  Nodal domain and eigenvalue multiplicity of graphs.  J. Comb., 3(4):609–622, 2012.