Using Schur Complement to prove a matrix is negative definite

Question

Need to find range of values of $\epsilon$ for which $$\begin{bmatrix} A+\epsilon B & \epsilon C \\ \epsilon C^\top & \epsilon D \end{bmatrix} \prec 0$$ given that $A,D \prec 0$ and $\epsilon > 0$.

The way I am going about it is using Schur Complement Lemma whereby this matrix is negative definite iff $ \epsilon D \prec 0$ and $A+\epsilon B-\epsilon CD^{-1}C^\top \prec 0$. Should the value of $\epsilon$ depend on the maximum eigenvalue of $A-\epsilon CD^{-1}C^\top$? What is the right way to go about it?

Answer 1

Please correct me if I made any mistake in the following:

You can use the Rayleigh Quotient to establish that $\lambda_{\text{max}}(M+N) \leq \lambda_{\text{max}}(M) + \lambda_{\text{max}}(N)$ for any symmetric matrices $M,N$ with the same size.

From the comments above one can infer that each element of the Schur Complement must be symmetric. Since $\lambda_{\text{max}}(A) < 0$ (true with the given condition that $A \prec 0$), one can find a small enough $\epsilon > 0$ such that $$ \begin{align*} \lambda_{\text{max}}(A + \epsilon(B - CD^{-1}C^T)) &\leq \lambda_{\text{max}}(A) + \lambda_{\text{max}}(\epsilon(B - CD^{-1}C^T))\\ &= \lambda_{\text{max}}(A) + \epsilon\cdot\lambda_{\text{max}}(B - CD^{-1}C^T) \\ &< 0, \end{align*} $$ since $A,B,C,D$ are all known. So a feasible set of $\epsilon > 0$ is simply the ones that satisfy the inequality above, but note that the inequality is simply sufficient and the result may only be a subset of all feasible $\epsilon$'s.

Answer 2

One could use the generalized eigenvalue problem

$$ A\,v = \lambda\,(C\,D^{-1}C^\top - B)\,v, \tag{1} $$

with $\lambda$ and $v$ one of the eigenvalue-eigenvector pairs associated with this.

Namely, when setting $\epsilon$ equal to one of those generalized eigenvalues one gets that

\begin{align} \det\!\left(A + \epsilon\,(B - C\,D^{-1}C^\top)\right) &= 0, \\ A + \epsilon\,(B - C\,D^{-1}C^\top) &\nprec 0. \end{align}

The eigenvalues of $A + \epsilon\,(B - C\,D^{-1}C^\top)$ should change continuously when changing the value of $\epsilon$. Therefore, in order for that matrix to switch from negative definite to not being negative definite one of its eigenvalues has to become equal to zero, which only happens at one of the generalized eigenvalues. Denoting $\lambda_1$ as the smallest positive generalized eigenvalue of $(1)$. From this it follows that at least for $0 < \epsilon < \lambda_1$ it holds that $A + \epsilon\,(B - C\,D^{-1}C^\top) \prec 0$.

I am not sure how one can directly find if there might be more intervals for $\epsilon$ after $\lambda_1$ where the inequality is satisfied. However, the remaining positive generalized eigenvalues should be the only candidates for the bounds of those intervals.