3
$\begingroup$

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!

$\endgroup$

1 Answer 1

3
$\begingroup$

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

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