7
$\begingroup$

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!

$\endgroup$
7
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Sorry, why is your first claim true? $\endgroup$ – Sandeep Silwal Dec 4 '19 at 4:58
  • $\begingroup$ @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$. $\endgroup$ – MTyson Dec 4 '19 at 5:18
  • 1
    $\begingroup$ 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$ $\endgroup$ – David E Speyer Dec 4 '19 at 13:46
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.