Bounding the spectral gap of a simple symmetric matrix

Question

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!

Answer 1

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.

Answer 2

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