An official website of the United States government
Size of nodal domains of the eigenvectors of a graph
Consider an eigenvector of the adjacency matrix of aG(n,p) graph. A nodal domain is a connected component of the set of vertices where this eigenvector has a constant sign. It is known that with high probability, there are exactly two nodal domains for each eigenvector corresponding to a nonleading eigenvalue. We prove that with high probability, the sizes of these nodal domains are approximately equal to each other.
more »
« less
- Award ID(s):
- 1807316
- PAR ID:
- 10144899
- Publisher / Repository:
- Wiley Blackwell (John Wiley & Sons)
- Date Published:
- Journal Name:
- Random Structures & Algorithms
- Volume:
- 57
- Issue:
- 2
- ISSN:
- 1042-9832
- Page Range / eLocation ID:
- p. 393-438
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
Abstract Covariance matrices are fundamental to the analysis and forecast of economic, physical and biological systems. Although the eigenvalues $$\{\lambda _i\}$$ and eigenvectors $$\{\boldsymbol{u}_i\}$$ of a covariance matrix are central to such endeavours, in practice one must inevitably approximate the covariance matrix based on data with finite sample size $$n$$ to obtain empirical eigenvalues $$\{\tilde{\lambda }_i\}$$ and eigenvectors $$\{\tilde{\boldsymbol{u}}_i\}$$, and therefore understanding the error so introduced is of central importance. We analyse eigenvector error $$\|\boldsymbol{u}_i - \tilde{\boldsymbol{u}}_i \|^2$$ while leveraging the assumption that the true covariance matrix having size $$p$$ is drawn from a matrix ensemble with known spectral properties—particularly, we assume the distribution of population eigenvalues weakly converges as $$p\to \infty $$ to a spectral density $$\rho (\lambda )$$ and that the spacing between population eigenvalues is similar to that for the Gaussian orthogonal ensemble. Our approach complements previous analyses of eigenvector error that require the full set of eigenvalues to be known, which can be computationally infeasible when $$p$$ is large. To provide a scalable approach for uncertainty quantification of eigenvector error, we consider a fixed eigenvalue $$\lambda $$ and approximate the distribution of the expected square error $$r= \mathbb{E}\left [\| \boldsymbol{u}_i - \tilde{\boldsymbol{u}}_i \|^2\right ]$$ across the matrix ensemble for all $$\boldsymbol{u}_i$$ associated with $$\lambda _i=\lambda $$. We find, for example, that for sufficiently large matrix size $$p$$ and sample size $n> p$, the probability density of $$r$$ scales as $1/nr^2$. This power-law scaling implies that the eigenvector error is extremely heterogeneous—even if $$r$$ is very small for most eigenvectors, it can be large for others with non-negligible probability. We support this and further results with numerical experiments.more » « less
-
Let (M,g) be a compact n-dimensional Riemannian manifold without boundary, where the metric g is C^1-smooth. Consider the sequence of eigenfunctions u_k of the Laplace operator on M. Let B be a ball on M. We prove that the number of nodal domains of u_k that intersect B is not greater than C_1Volume(B)k+C_2k^{(n-1)/n}, where C_1 and C_2 depend on (M,g) only. The problem of local bounds for the volume and for the number of nodal domains was raised by Donnelly and Fefferman, who also proposed an idea how one can prove such bounds. We combine their idea with two ingredients: the recent sharp Remez type inequality for eigenfunctions and the Landis type growth lemma in narrow domains.more » « less
-
Improving upon results of Rudelson and Vershynin, we establish delocalization bounds for eigenvectors of independent‐entry random matrices. In particular, we show that with high probability every eigenvector is delocalized, meaning any subset of its coordinates carries an appropriate proportion of its mass. Our results hold for random matrices with genuinely complex as well as real entries. As an application of our methods, we also establish delocalization bounds for normal vectors to random hyperplanes. The proofs of our main results rely on a least singular value bound for genuinely complex rectangular random matrices, which generalizes a previous bound due to the first author, and may be of independent interest.more » « less
-
We are interested in the number of nodal domains of eigenfunctions of sub-Laplacians on sub-Riemannian manifolds. Specifically, we investigate the validity of Pleijel’s theorem, which states that, as soon as the dimension is strictly larger than , the number of nodal domains of an eigenfunction corresponding to the -th eigenvalue is strictly (and uniformly, in a certain sense) smaller than for large . In the first part of this paper we reduce this question from the case of general sub-Riemannian manifolds to that of nilpotent groups. In the second part, we analyze in detail the case where the nilpotent group is a Heisenberg group times a Euclidean space. Along the way, we improve known bounds on the optimal constants in the Faber–Krahn and isoperimetric inequalities on these groups.more » « less
