# Lower-bounding minimal eigenvalue via the Schur complement

Suppose that $$M=\left( \begin{array}{cc} A & B\\ B^\top & C \end{array} \right)$$ for some symmetric matrices $$A$$ and $$C$$, and $$C$$ is invertible. Is it true that: $$\lambda_{\min}(M) \ge \min\left\{\lambda_{\min}(C)~,~\lambda_{\min}(A-BC^{-1}B^\top)\right\}~?$$ Here, $$\lambda_{\min}$$ refers to the minimum eigenvalue of a matrix. Even if the above inequality is incorrect, is there a way to lower bound $$\lambda_{\min}(A)$$ in terms of $$\lambda_{\min}(C)$$ and $$\lambda_{\min}(A-BC^{-1}B^\top)$$? You may even assume that $$M$$ is non-negative definite, and $$A=u^\top u~, ~B = u^\top X~\textrm{and}~C= X^\top X$$ for some vector $$u$$ and some matrix $$X$$, if that helps! Any help will be greatly appreciated!

The assumption that $$A,B$$ and $$C$$ take the forms of $$A=uu^\top,\ B=u^\top X\text{ and }C=X^\top X$$ is useless. Once $$M$$ is assumed to be positive semidefinite, it always admits a decomposition $$M=Y^\top Y$$ and one can always take $$\pmatrix{u&X}=Y$$.
In general, when $$M$$ is positive semidefinite, the inequality $$\lambda_\min(M)\ge\min\{\lambda_\min(C),\lambda_\min(S)\}$$ is true when $$M$$ is singular, because both sides of the inequality are zero.
When $$M$$ is positive definite, let $$S=A-BCB^\top$$. Since $$M=P^\top\left(S\oplus C\right)P$$ where $$P=\pmatrix{I&0\\ C^{-1}B^\top&I},$$ if $$x$$ is a unit eigenvector of $$M$$ corresponding to the minimum eigenvalue and $$y=Px$$, we have \begin{aligned} \lambda_\min(M)=x^\top Mx &=y^\top\left(S\oplus C\right)y\\ &\ge\lambda_\min\left(S\oplus C\right)\|y\|^2\\ &\ge\min\{\lambda_\min(C),\lambda_\min(S)\}\,\sigma_\min(P)^2. \end{aligned} Note that we cannot replace the factor $$\sigma_\min(P)^2$$ in the above by any positive constant. In particular, the inequality in your question is false in general. For instance, let $$A=(r^2+1)I,\,B=rI$$ and $$C=I$$. Then $$S=A-BCB^\top$$ is always equal to $$I$$ and $$M$$ is close to singular when $$r$$ is sufficiently large. Therefore $$\lim_{r\to+\infty}\lambda_\min(M)=0 \text{ while} \min\{\lambda_\min(C),\lambda_\min(S)\}=1.$$ In this counterexample, $$\sigma_\max(P)\ge\|C^{-1}B^\top\|=r$$. Since $$\det(P)=1\ge\sigma_\max(P)\sigma_\min(P)^{n-1}$$, we have $$\sigma_\min(P)\le\frac{1}{r^{n-1}}$$. Therefore $$\lim_{r\to+\infty}\sigma_\min(P)=0$$.