Support structure of eigenvectors

Given a real vector $u$, let the support ${\rm supp}\ u$ (resp. positive support ${\rm supp}^+\ u$, negative support ${\rm supp}^-\ u$) of $u$ be the set $\{i\vert u_i \ne 0\}$ (resp. $\{i\vert u_i > 0\}$, $\{i\vert u_i < 0\}$).

It is possible to bound the number of connected components of the positive and negative supports of an eigenvector of a graph.

Proposition 1.14.1   Let $\Gamma$ be a graph, and let $u$ be an eigenvector of its adjacency matrix $A$, say $Au = au$. Let $\Delta$ be the subgraph of $\Gamma$ induced by ${\rm supp}\ u$. For a subset $S$ of the vertex set of $\Delta$, let $N(S)$ be the number of connected components of the subgraph induced by $S$. For a real number $r$, let $g_r$ (resp. $h_r$) be the number of eigenvalues (counting multiplicities) of $\Delta$ that are not less than $r$ (resp. greater than $r$). Then $N({\rm supp}^+\ u) + N({\rm supp}^-\ u) \le g_a$ and $N({\rm supp}^+\ u) + N({\rm supp}^-\ u) - N({\rm supp}\ u) \le h_a$.

Proof:     For a subset $S$ of the vertex set of $\Delta$, let $I_S$ be the diagonal matrix with ones on the positions indexed by elements of $S$ and zeros elsewhere.

Let $C$ run through the connected components of ${\rm supp}^+\ u$ and ${\rm supp}^-\ u$. Put $u_C = I_C u$. Then the space $U := \langle u_C \vert C \rangle$ has dimension $N({\rm supp}^+\ u) + N({\rm supp}^-\ u)$.

For simplicity, replace $A$ by the adjacency matrix of $\Delta$, and then replace $A$ by $A-aI$. Define a real symmetric matrix $B$ by $B_{CD} = u_C^\top A u_D$. Then $B$ has zero row sums and nonpositive off-diagonal entries, so $B$ is positive semidefinite and by Lemma 1.13.2 the number of zero eigenvalues equals $N({\rm supp}\ u)$. It follows that for $y \in U$ we have $y^\top A y \ge 0$. This means that $U$ intersects the space spanned by the eigenvectors with negative eigenvalue in 0, and $N({\rm supp}^+\ u) + N({\rm supp}^-\ u) \le g_a$ follows. The vectors $y$ with $y^\top A y = 0$ correspond to eigenvectors with eigenvalue 0 of $B$, and altogether there are $N({\rm supp}\ u)$ independent such. This proves the other inequality. $\Box$

Examples     (i) Let $\Gamma$ be connected and bipartite, and let $a$ be the smallest eigenvalue of $\Gamma$. The corresponding eigenvector $u$ has different signs on the two sides of the bipartition, so ${\rm supp}^+\ u$ and ${\rm supp}^-\ u$ are the two sides of the bipartition, $N({\rm supp}^+\ u) + N({\rm supp}^-\ u)$ is the total number of vertices and $N({\rm supp}\ u) = 1$. We have equality in both inequalities.

(ii) Let $\Gamma$ be the star $K_{1,m}$. The spectrum is $\sqrt{m}^1$, $0^{m-1}$, $(-\sqrt{m})^1$. Let $u$ be an eigenvector with eigenvalue $a = 0$. We can choose $u$ to be nonzero off the apex of the star. Then $N({\rm supp}^+\ u) + N({\rm supp}^-\ u) = N({\rm supp}\ u) = m$ and $g_a = m$, $h_a = 0$, again equality in both inequalities.

(iii) Let $\Gamma$ be the Petersen graph. It has spectrum $3^1$, $1^5$, $(-2)^4$. Let $u$ be an eigenvector with eigenvalue $a = 1$ that vanishes on 4 points, so that ${\rm supp}\ u$ induces $3K_2$ with spectrum $1^3$, $(-1)^3$. We find $N({\rm supp}^+\ u) + N({\rm supp}^-\ u) = N({\rm supp}\ u) = 3$ and $g_a = 3$, $h_a = 0$, again equality in both inequalities.

(iv) Let $\Gamma$ be the path of length $m$ (with $m+1$ vertices). The eigenvalues are $\theta_k = 2 \cos (k\pi/(m+2))$ for $k = 1,...,m+1$. The eigenvector $u$ corresponding to $\theta_k$ has $k-1$ sign changes, so that $N({\rm supp}^+\ u) + N({\rm supp}^-\ u) = k$. If $gcd(k,m+2) = 1$ then $u$ has no zero entries, so that $N(u) = 1$. Now we have equality in both inequalities. If $gcd(k,m+2) = r$, then $u$ has $r-1$ zero entries, so that $N(u) = r$. Also, the eigenvalue $a = \theta_k$ is the $k/r$-th of each component of ${\rm supp}\ u$, so that $g_a = k$ and $h_a = k-r$, again with equality in both inequalities.

Remark     By interlacing, the numbers $g_a$ and $h_a$ for $\Delta$ are upper bounded by the corresponding numbers for $\Gamma$, but it is not true that $N({\rm supp}\ u) \le f_a := g_a - h_a$. For example, in case (ii) above we have $N({\rm supp}\ u) = m$ but the multiplicity of $0$ in the spectrum of $\Gamma$ is $m-1$.