PDFLINK |
Equiangular Lines and Eigenvalue Multiplicities
Communicated by Notices Associate Editor Emilie Purvine
Sphere packing, spherical codes, and other geometric arrangement problems have captivated the minds of Kepler, Newton, Gauss, and countless others. Viazovska’s recent breakthrough proof of the optimality of sphere packing arrangements in dimensions 8 and 24 was recognized in her 2022 Fields Medal citation. Despite the substantial interest and effort, these problems remain poorly understood especially in high dimensions, where precise answers are exceedingly rare.
This article delves into a recent solution of a longstanding problem on optimal configurations of equiangular lines. This is a rare instance of a high-dimensional packing problem that we now understand quite precisely. As we embark on our exploration of equiangular lines, we will see a beautiful link to spectral graph theory. A surprising revelation regarding eigenvalue multiplicities emerges, and it plays a pivotal role in cracking the geometric arrangement problem.
Equiangular Lines
How many lines can there be in all passing through the origin, and pairwise forming equal angles? In two dimensions, the answer is three. ,
In three dimensions, which is already harder to visualize, it turns out that the answer is six, attained by the six main diagonal lines of a regular icosahedron.
Let denote the maximum number of equiangular lines in Although the determination of each . turns out to be a finite problem, the complexity of the computation grows rapidly. The exact value of is known for only finitely many (e.g., see
A short and elegant linear algebraic argument by Gerzon
Let be unit vectors, one along each line, with pairwise inner products Let . which can be viewed as a symmetric , matrix, and thus determined by the entries on and above the diagonal. Thus lie in a vector space. Furthermore, -dimensional if is equal to , if The . matrix with on the diagonal and ’s elsewhere has full rank. So are linearly independent. Therefore .
These constructions of quadratically many equiangular lines turn out to have pairwise angles approach as the dimension increases. What happens if we fix the angle and let the dimension grow?
Let be the maximum number of lines in with pairwise angle The case of fixed . and large is particularly interesting. It turns out that the number of lines grows linearly in More precisely, . for some constant
With Zilin Jiang, Jonathan Tidor, Yuan Yao, and Shengtong Zhang (students and a postdoc at MIT at the time of the work), we gave a complete answer to this question
While much attention has been given to the spectral gap due to its connections to important properties like expansion and mixing (e.g., see the survey
History
While the general problem of equiangular lines has appeared in papers at least as early as the 1940s, the fixed angle version was considered in a 1973 paper by Lemmens and Seidel
The next case was solved in a 1989 paper by Neumaier
As for Neumaier wrote in his paper that “the next interesting case will require substantially stronger techniques.” ,
Progress on this problem stalled until Bukh
Jiang and Polyanskii
Results
Our work
First, let us state the result when is an odd integer, as the answer has a simpler form.
We now know that Theorem 3 holds for for some constant
To state the result for all other angles, we need some notation.
In other words, imagine enumerating all graphs in order of their number of vertices, computing the largest eigenvalue, and halting the first time comes up. Then is the number of vertices in the corresponding graph.Footnote2 Now we are ready to state the main result from
The computation of given is an interesting problem that we do not fully understand. For example, we do not know how to certify that some has There are some necessary conditions on . in order that For example . should be a Perron number, namely a positive real algebraic integer whose Galois conjugates are all real and less than in absolute value. However, being Perron is not sufficient for
Examples for Theorem 5. Here is a graph on vertices with top eigenvalue .
Connection to Spectral Graph Theory
The classic Algebraic Graph Theory (Graduate Text in Mathematics) by Godsil and Royle dedicates an entire chapter to equiangular lines, which the authors call “one of the founding problems of algebraic graph theory.” Let us explain the connection between equiangular lines and spectral graph theory.
Given equiangular lines in pick a unit vector , along the direction of for each There are two choices for . We make the choice arbitrarily for now and revisit this choice later. Since the lines pairwise form angle . we have , for all Define a graph . with vertices and an edge between , and if .
The Gram matrix has ones on the diagonal and off diagonal, with signs determined by the graph (here : is the identity matrix and is the all-ones matrix)
The Gram matrix has rank at most since , Furthermore, the Gram matrix is positive semidefinite. Conversely, any positive semidefinite . matrix with rank at most and ones on the diagonal is the Gram matrix of some collection of unit vectors in Indeed, we can recover . up to isometry from their Gram matrix using the Cholesky decompostion.
Via the above correspondence, for a given and the following two quantities are both equal to , :
- (a)
the maximum number of lines in with pairwise angle ;
- (b)
the maximum number of vertices of a graph for which
is positive semidefinite and has rank at most .
Proof Outline
Lower bound constructions for
As an example, let us show
We need to exhibit unit vectors in with pairwise inner products Rather than providing the coordinates of the vectors, which would be quite unwieldy, it suffices to provide their Gram matrix. The associated graph . turns out to be a disjoint union of triangles along with isolated vertices.
It remains to verify that the associated matrix
is positive semidefinite and has rank at most Indeed, positive semidefiniteness follows from being a positive linear combination of .
- •
which is positive semidefinite since the top eigenvalue of a triangle is , and ,
- •
which is also positive semidefinite. ,
As for rank, each of the triangle components of contributes a new dimension to its kernel. So the dimension of the kernel is Thus . Since . we have , This finishes the proof of . .
The same argument shows the general lower bound from Theorem 5.
Upper bound on
Applying the rank–nullity theorem, we have
The rank of the Gram matrix is at most since the vectors live in Since . ,
where denotes the multiplicity of as an eigenvalue of Already we see the connection between equiangular lines and eigenvalue multiplicities. .
The graph cannot have more than one eigenvalue greater than Indeed, otherwise their span would contain a unit vector . satisfying and It would contradict the positive semidefiniteness of the Gram matrix as .
Thus, for to be an eigenvalue of we must be in one of the following two situations: ,
- (a)
is the largest eigenvalue of In the more interesting case of . this case turns out to produce the equality case when the dimension , is large. The optimal giving the maximal value of ends up being a disjoint union of small graphs each with top eigenvalue at most This matches the lower bound construction from earlier, giving . This case is easy to analyze. We skip the details and refer the readers to .
JTYZZ21 .- (b)
is the second largest eigenvalue of This is the harder and more interesting case. The crux of the argument is to show that this case is suboptimal when the dimension . is large. Note that this situation could indeed occur for optimal configurations in small dimensions, such as constructions giving .
We want to show that the second largest eigenvalue of has small multiplicity. By a short argument that we omit, we can assume that is connected. Not all connected graphs have small second eigenvalue multiplicity. For example, a clique on vertices has top eigevalue with multiplicity and all , remaining eigenvalues equal to .
Balla et al.
It turns out that one can always switch the graph to get bounded maximum degree. Here is a precise statement taken from
To complete the proof of Theorem 5 on the maximum number of equiangular lines with a fixed angle, recall we are left with the case when is the second largest eigenvalue of a connected graph By .Theorem 6, we can assume that has bounded degree. By Theorem 2, we have So . and thus , When . having , is suboptimal compared to the case of being the largest eigenvalue of in which the optimal value is , .
Switching to a Bounded Degree Graph
Let us sketch the proof of Theorem 6. We start with unit vectors with pairwise inner products We form the “negative graph” . with vertices where , is an edge if We want to show that we can negate some subset of vectors to turn . into a bounded degree graph. Flipping each to has the effect of interchanging the neighborhood and non-neighborhood of vertex .
Forbidden induced subgraphs
We start by identifying two types of forbidden induced subgraphs of using the positive-semidefiniteness of , :
- (I)
Large clique;
- (II)
Some vertex two large subsets , and with no edges between them, such that is complete to and empty to (i.e., no edges between to ).
Here “large” means a large constant. We will be rather imprecise with constants and quantifiers in this proof sketch, so as to not be bogged down by details.
Let us first address (I). The Gram matrix restricted to an clique is -vertex
The sum of entries is
The proof of (II) is based on a similar idea except that we need a slightly more complicated test vector for positive semidefiniteness. The Gram matrix restricted to
Our test vector
Here
Switching argument
Using the above forbidden induced subgraphs, let us now argue that
By Ramsey’s theorem,Footnote3 not having a large clique implies that we must have a large independent set
Balla
Consider any vertex
Thus, for every vertex
Finally, we claim that the resulting graph has bounded degree. Suppose some vertex
Sublinear Second Eigenvalue Multiplicity
Let us now discuss Theorem 2. It says that a connected
We view
Bounded degree. A complete graph on
Connectedness. A disjoint union of
Second eigenvalue. The following graph has eigenvalue 0 with linear multiplicity. One such eigenvector is shown (unlabeled vertices are set to zero).
Furthermore, here is a graph whose least eigenvalue
So Theorem 2 is really about the top of the spectrum. Essentially the same proof shows that for any constant
Proof of sublinear second eigenvalue multiplicity
Let us prove that
The first inequality is quite wasteful and so the inequality on its own is not enough to give a sublinear bound on
A key new idea is to delete a small net from the graph. An
Let us write