Lower-bounding minimal eigenvalue via the Schur complement

Question

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!

Answer 1

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