Interlacing and the Second Largest Eigenvalue

Apparently, I described a very elegant argument to give a lower bound on the second largest eigenvalue of the adjacency matrix of a regular graph last year. This was pointed out in two recent preprints by Eero Räty, Benny Sudakov, and Istvan Tomon. This blog post is to describe the very short argument and how I derived it (stole it) from a remark in the book Distance-Regular Graphs by Brouwer, Cohen, and Neumaier (BCN). This shows yet again that BCN is an endless source of wisdom if you find the right interpretation of the words written there.

Note that Igor Balla found more or less the same bound on the second largest eigenvalue in 2021, but with a different argument.

1. Approximately Strongly Regular Graphs

Some time ago I wrote a paper on what I coined approximately strongly regular graphs. This is a relaxation of the notion of a strongly regular graph and I wrote it because often when I try to construct an object, the object under investiation feels close to a strongly regular graph, but is not it. Recall that strongly regular graphs are essentially the regular graphs with three distinct eigenvalues $ {k, r, s}$ where $ {k \geq r \geq 0 > s}$. (Here I slightly am lying. My usual definition of a strongly regular graph also includes some graphs with only two distinct eigenvalues.) One of the strongest existence condition for strongly regular graphs is the so-called Krein condition. They state that

$ \displaystyle (r+1)(k+r+2rs) \leq (k+r)(s+1)^2 $

and

$ \displaystyle (s+1)(k+s+2rs) \leq (k+s)(r+1)^2. $

For approximately strongly regular graphs, I only wanted to keep regularity as a condition, nothing else. So say that we have a graph of order $ {v}$ with degree $ {k}$, second largest eigenvalue $ {r}$ and smallest eigenvalue $ {s}$. I found the bounds

$ \displaystyle (s+r^2)v + 2(k-r)(r-s) \geq 0 $

and

$ \displaystyle (r+s^2)v + 2(k-s)(s-r) \geq 0. $

Below let us discuss the argument.

2. The Proof

When I wanted to proof this, my first idea was to adjust the standard proof for the Krein conditions for so-called association schemes. But this this is very technical and I have no idea how this should actually work. Take a look at Theorem 2.3.2 in BCN to get an idea. But right after Theorem 2.3.2 in BCN there is a great remark! Let $ {E}$ be the orthogonal projection matrix on some eigenspace of our graph. Then $ {E}$ is idempotent, so the eigenvalues of $ {E}$ are $ {0}$ and $ {1}$. Hence, the eigenvalues of the tensor product $ {E \otimes E}$ are $ {0}$ and $ {1}$. But we also know that the Hadamard or bad student’s product $ {E \circ E}$ is a principal submatrix of $ {E \otimes E}$. Hence, the eigenvalues of $ {E \circ E}$ interlace those of $ {E \otimes E}$, so they are in $ {[0, 1]}$. This gives you the Krein conditions for strongly regular graphs and, more generally, association schemes.

So how do we generalize this? We forget about the eigenspace, all we need is a matrix $ {E}$ with eigenvalues in $ {[0, 1]}$. Then $ {E \circ E}$ will also have eigenvalues in $ {[0, 1]}$. And we can simply take the matrix which we would take for a strongly-regular graph, say for the first inequality above

$ \displaystyle E = \frac{1}{s-r}(A – rI – \tfrac{k-r}{s} J). $

Here $ {A}$ is the adjacency matrix, $ {I}$ the identity matrix, and $ {J}$ the all-ones matrix. Then $ {E \circ E}$ is easy to calculate as we have $ {A \circ A = A}$, $ {A \circ I = 0}$, $ {A \circ J = A}$, $ {I \circ I = I}$, $ {I \circ J = I}$, and $ {J \circ J = J}$. In particular, it is a linear combination of $ {A}$, $ {I}$, and $ {J}$, so we know its eigenvalues. Rearranging yields the first bound above. For the other bound one switches the roles of $ {r}$ and $ {s}$.

Note that one can improve on these bounds as soon as one knows more about the eigenspaces of the graph.

3. The Second Largest Eigenvalues

Now when I wrote my paper I did not care about bounding the second largest eigenvalue, but luckily a standard trace trick (we have that $ {vk = tr(A^2) = }$ the sum of the squares of the eigenvalues) shows that $ {-(1+r) s \geq k/4}$. Then our first inequality implies

$ \displaystyle (-k + 4r^2(r+1)) v + 2k (k + 4r(r+1)) \geq 0. $

If $ {k \leq (1/2 – \varepsilon)v}$, then the term $ {(-k + 4r^2(r+1))v}$ dominates the equation and we see that $ {r = \Omega(k^{3/4})}$. In the note by Räty, Tomon, and Sudakov, you will find that bound with slightly more details added.

PS: I lack a bit of time to proof-read this post. I might correct typos later and will mention it here.

Edit 22 November 2023: Today Igor Balla got added as a co-author to the short note.