Skip to Main Content

Equiangular Lines and Eigenvalue Multiplicities

Yufei Zhao

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 GSY21).

A short and elegant linear algebraic argument by Gerzon LS73, reproduced in the footnote,⁠Footnote1 shows that . A matching quadratic lower bound was proved by de Caen dC00. Despite further progress, there remains a constant factor gap between the current lower and upper bounds.

1

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 -dimensional vector space. Furthermore, if , is equal to if . The matrix with ’s on the diagonal and 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 Buk16, in contrast to .

Question 1.

For fixed , determine .

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 JTYZZ21. We will state the main results shortly. A key step in our solution is a new result in spectral graph theory concerning eigenvalue multiplicities. In this article, when we talk about the eigenvalues of a graph , we are always referring to eigenvalues of the adjacency matrix .

Theorem 2.

Every connected bounded degree graph has sublinear second eigenvalue multiplicity. More precisely, the second largest eigenvalue of the adjacency matrix of an -vertex connected graph with maximum degree has multiplicity .

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 HLW06 on expander graphs), little is known about eigenvalue multiplicities. Theorem 2 is one of the first general results of this form. We will explore the eigenvalue multiplicity problem later in this article. It remains a tantalizing open problem to improve the bound of in Theorem 2. The best lower bound we know is on the order of .

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 LS73, who determined the value of for all . In particular, they showed that

The next case was solved in a 1989 paper by Neumaier Neu89, who showed that

As for , Neumaier wrote in his paper that “the next interesting case will require substantially stronger techniques.”

Progress on this problem stalled until Bukh Buk16 reignited interest in the problem in his 2016 paper. He showed that for some constant for each . Bukh furthermore conjectured that for any integer . This was followed by work by Balla, Dräxler, Keevash, and Sudakov BDKS18, who showed that

Jiang and Polyanskii JP20 formulated a conjecture for as a function of . We defer the precise statement until Theorem 5 since it requires a new definition. They proved their conjecture for all , where the threshold comes from a problem they solved in spectral graph theory. They also explained why this is a natural barrier for all existing methods, clarifying Nermaier’s earlier comment. The missing key turned out to be sublinear second eigenvalue multiplicities (Theorem 2).

Results

Our work JTYZZ21 determined the limit of as for all , confirming earlier conjectures of Bukh Buk16 and Jiang and Polyanskii JP20. For many values of , specifically those where the limit is greater than , the theorem actually gives the exact value of for large .

First, let us state the result when is an odd integer, as the answer has a simpler form.

Theorem 3.

For every integer , there is some so that

We now know that Theorem 3 holds for for some constant Bal21, whereas conjecturally is enough. The bottleneck lies in improving Theorem 2.

To state the result for all other angles, we need some notation.

Definition 4.

The spectral radius order of is defined to be the minimum possible number of vertices of a graph with top eigenvalue . We set if no such graph exists.

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 JTYZZ21. See Table 1 for examples.

2

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 Sch23.

Table 1.

Examples for Theorem 5. Here is a graph on vertices with top eigenvalue .

\renewcommand{\arraystretch}{2} \setlength{\unitlength}{1.0pt} \setlength{\extrarowheight}{0.0pt}\begin{tikzpicture}[ v/.style={circle, fill, minimum size = 2pt,inner sep = 0pt}, baseline={([yshift=-.8ex]current bounding box.center)}, scale=.4] \node[v] (1) at (0,0) {}; \node[v] (2) at (1,0) {}; \draw(1)--(2); \end{tikzpicture}
\renewcommand{\arraystretch}{2} \setlength{\unitlength}{1.0pt} \setlength{\extrarowheight}{0.0pt}\begin{tikzpicture}[v/.style={circle, fill, minimum size = 2pt,inner sep = 0pt}, baseline={([yshift=-.8ex]current bounding box.center)}, scale=.2] \node[v] (1) at (90:1) {}; \node[v] (2) at (210:1) {}; \node[v] (3) at (-30:1) {}; \draw(1)--(2)--(3)--(1); \end{tikzpicture}
\renewcommand{\arraystretch}{2} \setlength{\unitlength}{1.0pt} \setlength{\extrarowheight}{0.0pt}\begin{tikzpicture}[v/.style={circle, fill, minimum size = 2pt,inner sep = 0pt}, baseline={([yshift=-.8ex]current bounding box.center)}, scale=.4] \node[v] (1) at (0,0) {}; \node[v] (2) at (1,0) {}; \node[v] (3) at (1,1) {}; \node[v] (4) at (0,1) {}; \draw(1)--(2)--(3)--(4)--(1)--(3) (2)--(4); \end{tikzpicture}
\renewcommand{\arraystretch}{2} \setlength{\unitlength}{1.0pt} \setlength{\extrarowheight}{0.0pt}\begin{tikzpicture}[v/.style={circle, fill, minimum size = 2pt,inner sep = 0pt}, baseline={([yshift=-.8ex]current bounding box.center)}, scale=.2] \node[v] (1) at (90:1) {}; \node[v] (2) at (210:1) {}; \node[v] (3) at (-30:1) {}; \draw(3)--(1)--(2); \end{tikzpicture}
Theorem 5.

Let . Let and be the spectral radius order.

(a)

If , then there is some so that

(b)

If , then

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 .

\renewcommand{\arraystretch}{1} \setlength{\unitlength}{1.0pt} \setlength{\extrarowheight}{0.0pt}\begin{tikzpicture} [v/.style={circle, fill, minimum size = 2pt,inner sep = 0pt}, scale=.7, font=\footnotesize] \begin{scope} \draw(0:1)--(0:-1); \draw(60:1)--(60:-1); \draw(120:1)--(120:-1); \end{scope} \begin{scope}[xshift=2.8cm] \draw[-stealth] (0,0)--(0:1) node[label=below:$v_1$]{}; \draw[-stealth] (0,0)--(60:1) node[label=right:$v_2$]{}; \draw[-stealth] (0,0)--(120:1) node[label=left:$v_3$]{}; \end{scope} \begin{scope}[xshift=5.8cm] \node[v,label=below:$1$] (1) at (-30:.5) {}; \node[v,label=above:$2$] (2) at (90:.5) {}; \node[v,label=below:$3$] (3) at (210:.5) {}; \draw(1)--(3); \end{scope} \node[rectangle, draw, align=left, font=\footnotesize] at (8.3,0.5) { edge: obtuse\\ nonedge: acute }; \end{tikzpicture}

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. BDKS18 observed some important constraints on . Recall that in constructing from a set of equiangular lines, we took one unit vector along each line. In doing so, we made an arbitrary choice whether to take or . Recall that the edges of correspond to inner product while nonedges correspond to inner product . Switching some vector to its negative changes the graph by swapping all the edges and nonedges out of the corresponding vertex.

It turns out that one can always switch the graph to get bounded maximum degree. Here is a precise statement taken from JTYZZ21, based on BDKS18. We will sketch a proof in the next section.

Theorem 6 (Switching to bounded degree).

For every , there exists that depends on only, so that given any configuration of lines (in any dimension) with pairwise angle , we can choose one unit vector along each line so that each of these unit vectors has inner product with at most other unit vectors.

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 -vertex clique is

The sum of entries is , which must be nonnegative due to the matrix being positive semidefinite. So . In other words, has no clique on more than vertices.

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 is

Our test vector assigns a small constant to , as well as to each vertex of , and likewise to each vertex of . Then

Here . The first approximation ignores the negligible contributions from diagonal matrix entries, which is valid if and are large compared to .

Switching argument

Using the above forbidden induced subgraphs, let us now argue that can be switched to a bounded degree graph.

By Ramsey’s theorem,⁠Footnote3 not having a large clique implies that we must have a large independent set , whose size grows with .

3

Balla Bal21 later found another proof not using Ramsey’s theorem, leading to a better quantitative result. We now know that, in Theorem 6, one can take to be .

Consider any vertex outside . We claim that has either a bounded number of neighbors in or a bounded number of non-neighbors in . Indeed, let and be respectively the neighbors and non-neighbors of in . There are no edges between and since they are both contained in the independent set . If and were both large, then together with they would form a type II forbidden configuration.

Thus, for every vertex outside , by negating the vector corresponding to if necessary, we may assume that has only a bounded number of neighbors in .

Finally, we claim that the resulting graph has bounded degree. Suppose some vertex has many neighbors. Let be a large but bounded subset of neighbors of . Recall that each vertex in has a bounded number of neighbors in . Let be minus the neighborhood of . Then would once again violate (II).

Sublinear Second Eigenvalue Multiplicity

Let us now discuss Theorem 2. It says that a connected -vertex graph with maximum degree⁠Footnote4 has second eigenvalue multiplicity at most . Before diving into the proof, let us discuss some near-miss examples that illustrate the necessity of the hypotheses.

4

We view as a constant, though the dependence on is quite mild as the hidden leading constant is .

Bounded degree. A complete graph on vertices has second eigenvalue multiplicity . Other examples with linear eigenvalue multiplicity include strongly regular graphs, such as Paley graphs.

Connectedness. A disjoint union of edges has top eigenvalue repeated times. So the theorem is false without the connectivity hypothesis.

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 has linear multiplicity, arising from the eigenvector of with eigenvalue .

So Theorem 2 is really about the top of the spectrum. Essentially the same proof shows that for any constant , the -th largest eigenvalue of a connected graph with maximum degree has multiplicity .

Proof of sublinear second eigenvalue multiplicity

Let us prove that for a connected -vertex graph with maximum degree and second largest eigenvalue . We use the trace method to bound eigenvalue multiplicities. Write for the eigenvalues of , including multiplicities. We have

The first inequality is quite wasteful and so the inequality on its own is not enough to give a sublinear bound on . The right-hand side counts closed walks of length in . Such a walk must stay in the radius neighborhood of its starting vertex. This leads us to examine the spectral radius of balls in , which we refer to informally as a “local spectral radius.” See Figure 1.

Figure 1.

A key idea in the proof of Theorem 2 is that removing a net of vertices (white dots) significantly lowers local spectral radii ( of the dark disk).

\renewcommand{\arraystretch}{1} \setlength{\unitlength}{1.0pt} \setlength{\extrarowheight}{0.0pt}\begin{tikzpicture} \fill[pink] (0,0) circle (1); \fill[red] (0.3,-.3) circle (.4); \foreach\x/\y in { -0.89/-0.28, -0.91/-0.14, -0.89/-0.02, -0.88/0.16, -0.89/0.32, -0.87/0.42, -0.79/-0.58, -0.72/-0.46, -0.78/-0.3, -0.75/-0.13, -0.75/0.03, -0.71/0.1, -0.81/0.28, -0.76/0.41, -0.77/0.57, -0.6/-0.78, -0.61/-0.6, -0.58/-0.44, -0.66/-0.33, -0.65/-0.13, -0.57/0.03, -0.67/0.14, -0.56/0.3, -0.66/0.45, -0.62/0.56, -0.59/0.75, -0.44/-0.9, -0.46/-0.73, -0.45/-0.64, -0.41/-0.52, -0.49/-0.29, -0.52/-0.15, -0.44/0.02, -0.44/0.22, -0.47/0.24, -0.43/0.42, -0.49/0.59, -0.44/0.75, -0.29/-0.85, -0.3/-0.78, -0.31/-0.61, -0.32/-0.46, -0.33/-0.3, -0.32/-0.11, -0.3/0.03, -0.29/0.14, -0.32/0.35, -0.33/0.39, -0.33/0.56, -0.33/0.77, -0.34/0.87, -0.15/-0.91, -0.15/-0.73, -0.16/-0.62, -0.13/-0.49, -0.13/-0.31, -0.16/-0.11, -0.21/-0.04, -0.17/0.1, -0.13/0.34, -0.18/0.41, -0.18/0.59, -0.13/0.72, -0.13/0.92, 0.03/-0.96, -0.02/-0.77, -0.04/-0.62, -0.03/-0.46, -0.02/-0.29, 0.02/-0.21, -0.01/0.02, 0.01/0.11, -0.01/0.29, -0.04/0.41, -0.04/0.59, -0.03/0.72, 0.01/0.93, 0.13/-0.93, 0.16/-0.76, 0.21/-0.6, 0.18/-0.5, 0.22/-0.31, 0.17/-0.12, 0.16/0.01, 0.17/0.12, 0.16/0.3, 0.12/0.5, 0.19/0.6, 0.13/0.73, 0.17/0.88, 0.3/-0.88, 0.29/-0.75, 0.29/-0.59, 0.31/-0.43, 0.26/-0.32, 0.33/-0.21, 0.33/0.0, 0.33/0.15, 0.27/0.31, 0.34/0.5, 0.27/0.6, 0.32/0.73, 0.31/0.87, 0.47/-0.88, 0.5/-0.73, 0.43/-0.57, 0.46/-0.44, 0.43/-0.28, 0.47/-0.18, 0.43/0.08, 0.45/0.15, 0.52/0.32, 0.45/0.43, 0.44/0.63, 0.48/0.78, 0.47/0.86, 0.62/-0.74, 0.59/-0.61, 0.58/-0.45, 0.6/-0.32, 0.58/-0.12, 0.59/-0.02, 0.62/0.19, 0.62/0.33, 0.6/0.44, 0.58/0.57, 0.63/0.77, 0.74/-0.59, 0.7/-0.48, 0.75/-0.31, 0.78/-0.14, 0.72/-0.02, 0.76/0.08, 0.73/0.25, 0.73/0.46, 0.76/0.56, 0.89/-0.43, 0.9/-0.32, 0.95/-0.1, 0.87/0.02, 0.87/0.14, 0.9/0.24, 0.89/0.43 } \fill[white] (\x,\y) circle (.03); \end{tikzpicture}

A key new idea is to delete a small net from the graph. An -net in a graph is a subset of vertices such that every vertex in lies within distance from some vertex in the -net. We show that deleting a net significantly reduces local spectral radii. This observation combined with the earlier inequality yields a good upper bound on the multiplicity of in with the net removed. Finally, to bound , observe that by the Cauchy eigenvalue interlacing theorem, deleting vertices can reduce each eigenvalue multiplicity by at most .

Lemma 7 (Finding a small net).

For every and , every connected -vertex graph has an -net of size at most .

Proof.

First replace the graph by a spanning tree. Pick an arbitrary vertex as the root. Pick a vertex furthest from the root, and walk steps towards the root to end up at vertex . Add to the net and keep only the the subtree containing the root after deleting . This removes at least vertices. Repeat.

Lemma 8 (Net removal reduces spectral radius).

If (with at least one vertex) is obtained from by deleting an -net, then .

Proof.

We can assume that has no isolated vertices. Write for the adjacency matrix of , and the matrix obtained by zeroing out the rows and columns corresponding to vertices of the deleted net. Clearly entrywise. Let be a vertex of . Consider the diagonal entries indexed by in and . They count closed walks of length starting at . There are always strictly more such walks in than in since at least one such walk passes through the net. Thus entrywise, and the lemma follows.

Let us write