Lower bound on Spectral Gap of Rank one + Diagonal

Question

For some $x\in\mathbb{R}^n, \|x\|_2^2=1$ and $\alpha\geq 0$, consider the positive semi-definite matrix $$ X_\alpha := xx^T + \alpha\sum_{k=1}^nx_k^2e_ke_k^T. $$ Suppose for simplicity that the coordinates of $x$ are ordered such that $$ 0\leq x_1^2\leq ... \leq x_n^2. $$ I'm interested in a non-trivial lower bound on the spectral gap $$ \sigma(\alpha):=\lambda_1(X_\alpha)-\lambda_2(X_\alpha)\geq\ ?? $$ It's easy to see that $$ \begin{cases}\sigma(0)= 1& \\\sigma(\alpha)/\alpha\rightarrow x_n^2-x_{n-1}^2 \end{cases} $$ But I'm not sure about any inequalities for the intermediate cases.

Via the Matrix Determinant Lemma and this previous MO answer we have that $$ \lambda_2(X_\alpha)\in[\alpha x_{n-1}^2,\alpha x_n^2] $$ but I'm not sure of any interesting lower bounds on $\lambda_1(X_\alpha)$ that could be useful.

One line of reasoning I tried following is to say the eigenvalues of $xx^T$ are $\{0,1\}$ and thus so long as $$\alpha x_n^2 < 1/2$$ the worst case scenario is that the eigenvalues of $xx^T$ get closer by an amount $\alpha x_n^2$, but this seemed crude and doesn't capture a very large range of $\alpha$.

Another line of reasoning is to consider how close $\sum_{k=1}^nx_k^2e_ke_k^T$ is to a matrix of the form $$ \begin{bmatrix}\mathbf{0} & \mathbf{0}\\ \mathbf{0} & \mu\mathbf{Id}_{i\times i} \end{bmatrix} $$

in, say, the operator norm. I believe the closest matrix occurs when $\mu = 1/2(x_n^2 + \min_{x_k\neq 0}x_k^2)$. Using this, we can apply perturbation theory to obtain some bounds, but this didn't produce anything for me.

Any references or insight would be appreciated.

Answer 1

One simple lower bound on the largest eigenvalue of $X_{\alpha}$ is $$ \lambda_1(X_{\alpha}) = \sup_{u \ne 0} \frac{u^T X_{\alpha} u}{u^T u} \ge x^T X_{\alpha} x = 1 + \alpha \sum_{k=1}^n x_k^4. $$ In particular, this should be a very good estimate for small $\alpha$. For large $\alpha$, from the matrix determinant lemma you linked to, we know that the eigenvalues of $X_{\alpha}$ satisfy $$ 0 = 1 - \sum_{k=1}^n \frac{x_k^2}{\lambda - \alpha x_k^2} . $$ Multiply through by $\lambda - \alpha x_n^2$. If $\lambda > \alpha x_n^2$ then $$ 0 = \lambda - \alpha x_n^2 - x_n^2 - \sum_{k=1}^{n-1} \frac{\lambda - \alpha x_n^2}{\lambda - \alpha x_k^2} x_k^2 \le \lambda - (\alpha+1) x_n^2 , $$ since the sum in this region is positive. As there is a root $\lambda_1 > \alpha x_n^2$ but $\lambda - (\alpha+1) x_n^2 < 0$ for $\alpha x_n^2 < \lambda < (\alpha+1) x_n^2$, it follows that $$ \lambda_1 \ge (\alpha+1) x_n^2. $$ Combining this with the first bound (i.e., the maximum of both) should give you a decent bound for all $\alpha$. Note to recover the asymptotic behavior of $\sigma(\alpha)$ for large $\alpha$ you need a better upper bound on $\lambda_2$ to show that it's close to $\alpha x_{n-1}^2$; I haven't done that here but I think a similar approach to the above could get you there.