# Bounding the spectral gap of a simple symmetric matrix

I have a seemingly innocent linear algebra problem that I cannot solve, and which I hope that you would kindly offer some insight into. Here is the description: Let $$\mathbf{a} = (a_1, a_2, \dots, a_d)^{T}$$ be a positive probability vector, $$i.e.$$ $$\Vert \mathbf{a}\Vert_1=1$$ and $$a_i > 0$$ for all $$i$$. Let matrix $$A$$ be defined as follows: $$A = \textrm{diag}(\mathbf{a}) - \mathbf{a}\mathbf{a}^{T}$$ where $$\textrm{diag}(\mathbf{a})$$ means the diagonal matrix with the $$i$$th diagonal entry being $$a_i$$. It is straightforward to show that $$\mathbf{1}_d$$, the all-one vector of dimension $$d$$, is an eigenvector of $$A$$ of eigenvalue $$0$$. And Gershgorin circle theorem also shows that all $$A$$'s eigenvalues are greater or equal to $$0$$. My question is:

What is the smallest eigenvalue of $$A$$ that is not zero?

I carried out the calculation when $$d = 3$$ and realized that there may not be a simple analytic formula to it and hence a nice lower bound is also greatly appreciated.

Thank you so much!

Let $$x$$ be the smallest nonzero eigenvalue of $$A$$. It is the reciprocal of the largest root of $$f(t)=-\det(t(D-aa^\top)-I),$$ where $$D$$ is the diagonal matrix. By the matrix determinant lemma, \begin{align} f(t)&=-\det(tD-I)(1-ta^\top(tD-I)^{-1}a)\\ &=-\det(tD-I)\left(1-\sum_{i=1}^d \frac{ta_i^2}{ta_i-1}\right)\\ &=-\det(tD-I)\left(1-\sum_{i=1}^d a_i\left(1+\frac{1}{ta_i-1}\right)\right)\\ &=\det(tD-I)\left(\sum_{i=1}^d \frac{a_i}{ta_i-1}\right)\\ &=\frac{d}{dt}\det(tD-I). \end{align} Gideon Peyser's 1967 paper "On the Roots of the Derivative of a Polynomial With Real Roots" gives $$a_2^{-1}+\frac{a_1^{-1}-a_2^{-1}}{2}\le x^{-1}\le a_1^{-1}-\frac{a_1^{-1}-a_2^{-1}}{d},$$ where $$a_1$$ and $$a_2$$ are the smallest and second smallest entries of $$a$$ respectively.
• @SandeepSilwal Up to a sign, $t^d f(1/t)$ is the characteristic polynomial of $A$. The multiset of nonzero roots of $f(t)$ therefore equals the multiset of the reciprocals of nonzero eigenvalues of $A$. – MTyson Dec 4 '19 at 5:18
• It might be worth pointing out explicitly: Since $f(t)$ is the deriviative of $\prod (t a_j-1)$, by Rolle's theorem, the roots of $f$ are interlaced with the $a_j^{-1}$, so the nonzero eigenvalues of $A$ are interlaced with the $a_j$ – David E Speyer Dec 4 '19 at 13:46
Here is an elementary bound. The second eigenvalue of $$A$$ satisfies $$\lambda_2(A)> \max_k\min_{i\ne k}a_ia_k=(\max_ka_k)(\min_ia_i).$$ To prove it, let $$A_k$$ be the principal submatrix obtained by deleting the $$k$$th row and column. By interlacing, we have $$\lambda_2(A)>\lambda_1(A_k)$$. Now apply Gershgorin to $$A_k$$: there exists an index $$i\ne k$$ such that $$\lambda_1(A_k)\ge a_i(1-a_i)-\sum_{j\ne i,k}a_ia_j=a_ia_k.$$
Improvement. Actually, one has $$\lambda_2(A)\ge\min_ia_i$$. To see this, write $$A=D+B$$ with $$D={\rm diag}(a_1,\ldots,a_n)$$ and $$B=-aa^T$$. By Weyl's inequality, we have $$\lambda_2(A)\ge\lambda_1(D)+\lambda_2(B)=\min_ia_i+0.$$ Remark that this bound is accurate, as if $$a_1=\cdots=a_{n-1}=\min_ia_i$$ and $$a_n=1-(n-1)a_1$$, then the spectrum of $$A$$ is given by $$0$$, $$a_1$$ (multiplicity $$n-2$$) and $$na_1a_n$$. Hence $$\lambda_2=a_1$$.