Next: Exercise Up: The spectrum of a Previous: Diagonally dominant matrices

# Support structure of eigenvectors

Given a real vector , let the support (resp. positive support , negative support ) of be the set (resp. , ).

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 be a graph, and let be an eigenvector of its adjacency matrix , say . Let be the subgraph of induced by . For a subset of the vertex set of , let be the number of connected components of the subgraph induced by . For a real number , let (resp. ) be the number of eigenvalues (counting multiplicities) of that are not less than (resp. greater than ). Then and .

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

Let run through the connected components of and . Put . Then the space has dimension .

For simplicity, replace by the adjacency matrix of , and then replace by . Define a real symmetric matrix by . Then has zero row sums and nonpositive off-diagonal entries, so is positive semidefinite and by Lemma 1.13.2 the number of zero eigenvalues equals . It follows that for we have . This means that intersects the space spanned by the eigenvectors with negative eigenvalue in 0, and follows. The vectors with correspond to eigenvectors with eigenvalue 0 of , and altogether there are independent such. This proves the other inequality.

Examples     (i) Let be connected and bipartite, and let be the smallest eigenvalue of . The corresponding eigenvector has different signs on the two sides of the bipartition, so and are the two sides of the bipartition, is the total number of vertices and . We have equality in both inequalities.

(ii) Let be the star . The spectrum is , , . Let be an eigenvector with eigenvalue . We can choose to be nonzero off the apex of the star. Then and , , again equality in both inequalities.

(iii) Let be the Petersen graph. It has spectrum , , . Let be an eigenvector with eigenvalue that vanishes on 4 points, so that induces with spectrum , . We find and , , again equality in both inequalities.

(iv) Let be the path of length (with vertices). The eigenvalues are for . The eigenvector corresponding to has sign changes, so that . If then has no zero entries, so that . Now we have equality in both inequalities. If , then has zero entries, so that . Also, the eigenvalue is the -th of each component of , so that and , again with equality in both inequalities.

Remark     By interlacing, the numbers and for are upper bounded by the corresponding numbers for , but it is not true that . For example, in case (ii) above we have but the multiplicity of in the spectrum of is .

Next: Exercise Up: The spectrum of a Previous: Diagonally dominant matrices
Andries Brouwer 2003-09-30