The minimum number of distinct eigenvalues of an -vertex simple graph is the least number of distinct eigenvalues of a real symmetric matrix whose off-diagonal entry is nonzero iff is an graph edge of (Ahmadi et al. 2013). The diagonal entries are unrestricted. The adjacency matrix is one admissible choice, so is at most the number of distinct values in the graph spectrum.

An empty graph of positive order has , as witnessed by the identity matrix. For the complete graph with , the matrix with every entry equal to 1 has exactly two distinct eigenvalues. A real symmetric matrix with only one distinct eigenvalue is a scalar multiple of the identity matrix, so .

Nguyen (2026) proved the sparse-complement conjecture. If has vertices and its graph complement has at most edges, then .

See also

Graph Complement, Graph Spectrum, Symmetric Matrix

Explore with Wolfram|Alpha

References

Ahmadi, B.; Alinaghipour, F.; Cavers, M. S.; Fallat, S.; Meagher, K.; and Nasserasr, S. "Minimum Number of Distinct Eigenvalues of Graphs." Elec. J. Linear Algebra 26, 673-691, 2013. https://doi.org/10.13001/1081-3810.1679.Nguyen, B. T. "The Sparse-Complement Conjecture for Two Distinct Eigenvalues." 6 Nov 2026. https://arxiv.org/abs/2611.09111v1.

Cite this as:

Weisstein, Eric W. "Minimum Number of Distinct Eigenvalues." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/MinimumNumberofDistinctEigenvalues.html

Subject classifications