# Lower bound on Spectral Gap of Rank one + Diagonal

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.

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.