12
$\begingroup$

Let $A, B, C \in \mathbb{R}^{n\times n}$ such that $N = \begin{bmatrix} A & B\\ B^{\top} & C\end{bmatrix}$ is a symmetric positive definite matrix. I'm trying to show that the following matrix

$$ M = \begin{bmatrix} A & B & 0\\ B^{\top} & C & -B^{\top} \\ - A & -B & A\end{bmatrix} $$ has eigenvalues with positive real part. Numerical tests suggest this is true, but I cannot prove it.

Edit It is not true that $M + M^\top$ has positive eigenvalues, i.e. that $\langle x, Mx\rangle \geq 0$ for all $x$, which is (?) a sufficient condition for $M$ to have eigenvalues with positive real parts.

Edit 2 After further numerical tests, letting $\lambda_{\min}$ the smallest eigenvalue of $N$, and $v_{\min}$ the smallest real part of the eigenvalues of $M$, it seems like we should have a bound like $$ v_{\min} \geq \rho \cdot \lambda_{\min} $$ where the constant $\rho$ is $\simeq 0.963$.

Edit 3 I expect that we can answer the question by finding the right factorization for $M$. For instance it is easy to show that $$ \begin{bmatrix} A & B & -A\\ B^{\top} & C & -B^{\top} \\ - A & -B & A\end{bmatrix} $$ has positive eigenvalues since it equals $ \begin{bmatrix} I & 0 & -I \\ 0& I & 0\end{bmatrix}^{\top}N \begin{bmatrix} I & 0 & -I \\ 0& I & 0\end{bmatrix}$

$\endgroup$
3
  • $\begingroup$ Even when n = 1, I am at a loss to prove the result, the closed form expression for the eigenvalues is not informative wolframalpha.com/input/… $\endgroup$
    – PAb
    Nov 3, 2021 at 13:29
  • 1
    $\begingroup$ Did you notice the identity $\det M=\det A\det N$ ? $\endgroup$ Nov 5, 2021 at 10:58
  • $\begingroup$ Thanks ! No I did not. However I think the relationship does not hold anymore when subtracting $\lambda Id$ from $M$, so the eigenvalues of $M$ are not those of $N$ and $A$. But maybe we can manage to use this identity to prove the expected result. $\endgroup$
    – PAb
    Nov 5, 2021 at 11:28

4 Answers 4

8
+150
$\begingroup$

A simple brute force method worked (even though I'm not happy with this).

Let $\zeta=\xi+i\eta$ be a non-positive eigenvalue of $M$ and $\left[\begin{matrix} x & y & z \end{matrix}\right]^T$ be a corresponding eigenvector. This gives equations \begin{align} Ax + By \qquad &= \zeta x \\ B^Tx + Cy - B^Tz &= \zeta y\\ -Ax -By + Az &= \zeta z \end{align} From the first and the third, one obtains $$z = -\zeta(\zeta-A)^{-1}x \mbox{ and } x-z = (1+\zeta(\zeta-A)^{-1})x.$$ To ease the notation, put $A(\zeta):=1+\zeta(\zeta-A)^{-1}=(2\zeta-A)(\zeta-A)^{-1}$. From the second, $$y = (\zeta-C)^{-1}B^T(x-z) = (\zeta-C)^{-1}B^T A(\zeta) x.$$ By combining with the first, one obtains $$(\zeta-A)x = By = B(\zeta-C)^{-1}B^T A(\zeta)x.$$ Note that the imaginary part of $(\zeta- C)^{-1}$ is $$\Im\frac{1}{\zeta- C}=\Im\frac{\bar{\zeta}-C}{|\zeta-C|^2} =-\eta\frac{1}{|\zeta-C|^2}.$$ Take the inner product with $A(\zeta)x$ and look at the imaginary part: $$\Im \langle (\zeta-A)x,A(\zeta)x\rangle = -\eta \langle B|\zeta-C|^{-2}B^TA(\zeta)x,A(\zeta)x\rangle.$$ Now, since \begin{align*} A(\bar{\zeta})(\zeta-A) &= \frac{(2\bar{\zeta}-A)(\zeta-A)^2}{|\zeta-A|^2} \\ &=\frac{2|\zeta|^2\zeta-4|\zeta|^2A+2\bar{\zeta}A^2-\zeta^2A+2\zeta A^2-A^3}{|\zeta-A|^2}, \end{align*} one obtains $$2\eta\langle \frac{|\zeta|^2-\xi A }{|\zeta-A|^2}x,x\rangle =-\eta \langle B|\zeta-C|^{-2}B^TA(\zeta)x,A(\zeta)x\rangle.$$ Hence, unless $\eta=0$, $$\xi\geq\frac{|\zeta|^2}{\|A\|}>0.$$ Let's deal with the case $\eta=0$. Suppose for a contradiction that $\xi\le0$. Then \begin{align*} \langle A(\xi)(-\xi+A)x,x\rangle &= \langle B(-\xi+C)^{-1}B^T A(\xi)x,A(\xi)x\rangle\\ &\le \langle BC^{-1}B^T A(\xi)x,A(\xi)x\rangle\\ &< \langle A A(\xi)x,A(\xi)x\rangle, \end{align*} but this is in contradiction with the fact that $A(\xi)\succ0$ and $-\xi + A\succeq A(\xi)A$.

ADDED: We assume $\left[\begin{smallmatrix} A_0 & B_0 & \\ B_0^T & C_0\end{smallmatrix}\right]\succ 2\epsilon$ and will show that any eigenvalue of $\left[\begin{smallmatrix} A_0 & B_0 & \\ B_0^T & C_0 & -B_0^T \\ -A_0 & -B_0 & A_0 \end{smallmatrix}\right]$ has its real part at least $\epsilon$. To ease notation, we consider $A=A_0-2\epsilon$ and $C=C_0-2\epsilon$ instead of $A_0$ and $C_0$. By the IVT trick, it suffices to show there is no solution for $$\left[\begin{matrix} A+2\epsilon & B & \\ B^T & C+2\epsilon & -B^T \\ -(A+2\epsilon) & -B & A+2\epsilon \end{matrix}\right] \left[\begin{matrix} x \\ y \\ z \end{matrix}\right] = (\epsilon+i\eta) \left[\begin{matrix} x \\ y \\ z \end{matrix}\right],$$ with $\left[\begin{smallmatrix} A & B & \\ B^T & C\end{smallmatrix}\right]\succ 0$, $\epsilon>0$, $\eta\in\mathbb{R}$, and $\left[\begin{smallmatrix} x & y & z \end{smallmatrix}\right]\neq 0$.

The first row + the third row: $-\epsilon x + (A+\epsilon) z = i\eta (x+z).$ Hence $$x-z=(1-\frac{\epsilon+i\eta}{A+\epsilon-i\eta})x =\frac{A-2i\eta}{A+\epsilon-i\eta}x=:A(\eta)x.$$ Together with the second row: $$y=-(C+\epsilon-i\eta)^{-1}B^T(x-z)=-(C+\epsilon-i\eta)^{-1}B^TA(\eta)x.$$ It follows that $x\neq0$. Together with the first row: \begin{align*} (A+\epsilon -i\eta) x = -By = B(C+\epsilon-i\eta)^{-1}B^TA(\eta)x \end{align*} and so \begin{equation}\tag{$\ast$} \langle (A+\epsilon -i\eta) x,A(\eta)x\rangle = \langle B(C+\epsilon-i\eta)^{-1}B^TA(\eta)x, A(\eta)x\rangle.\end{equation} Do some calculations: $$A(\eta)^*(A+\epsilon -i\eta) = |A+\epsilon-i\eta|^{-2}(A+\epsilon-i\eta)^2(A+2i\eta),$$ $$(A+\epsilon-i\eta)^2(A+2i\eta) = A^3 + 2 \epsilon A^2 + \epsilon^2 A + 3 \eta^2 A + 4\epsilon \eta^2 + 2i\eta (\epsilon A + \epsilon^2 - \eta^2),$$ $$A(\eta)^*B(C+\epsilon-i\eta)^{-1}B^TA(\eta) =A(\eta)^*B\frac{C+\epsilon +i\eta}{|C+\epsilon-i\eta|^2}B^TA(\eta),$$ $$A(\eta)^*B\frac{C+\epsilon}{|C+\epsilon-i\eta|^2}B^TA(\eta) \preceq A(\eta)^*B C^{-1} B^T A(\eta) \prec A|A(\eta)|^2,$$ $$A|A(\eta)|^2 = |A+\epsilon-i\eta|^{-2}(A^3+4\eta^2A).$$ Look at the real part of $(\ast)$: for $w=|A+\epsilon-i\eta|^{-1}x$, $$\langle(2\epsilon A^2+\epsilon^2A+4\epsilon\eta^2)w,w\rangle < \langle \eta^2Aw,w\rangle.$$ Look at the imaginary part of $(\ast)$: as $\eta\neq0$ from the previous inequality, $$\langle(\epsilon A + \epsilon^2 - \eta^2)w,w\rangle =\langle A(\eta)^*B\frac{1}{|C+\epsilon-i\eta|^2}B^TA(\eta)x,x\rangle/2 \geq0.$$ Combine the last two: \begin{align*} 2\epsilon \|Aw\|^2+\epsilon^2\langle Aw,w\rangle +4\epsilon\eta^2\|w\|^2 &< \eta^2\langle Aw,w\rangle\\ &\le (\epsilon \frac{\langle Aw,w\rangle}{\|w\|^2} +\epsilon^2)\langle Aw,w\rangle\\ &\le\epsilon\|Aw\|^2 +\epsilon^2\langle Aw,w\rangle. \end{align*} We arrive at a contradiction.

$\endgroup$
3
  • $\begingroup$ Thanks a lot for the nice answer ! I'll try to derive a bound using the same technique :) $\endgroup$
    – PAb
    Nov 10, 2021 at 11:25
  • 1
    $\begingroup$ If you combine Michael Renardy's IVT trick with the above proof, you get some estimate like Edit 2 (I think I confirmed it for $\rho=0.5$ by hand). $\endgroup$ Nov 11, 2021 at 14:10
  • $\begingroup$ Once again, thank you so much: your help is invaluable! $\endgroup$
    – PAb
    Nov 12, 2021 at 10:10
5
$\begingroup$

This post is the solution to the limit case, as suggested by Denis Serre, where the Schur complement $S=C-B^TA^{-1}B$ is zero. This means that $W:=A^{-1/2}BC^{-1/2}$ is an orthogonal matrix. Now put $S=\operatorname{diag}(A^{1/2}, C^{1/2}W^T, A^{1/2})$ and consider $$N:=S^{-1}MS =\left[\begin{matrix} A & D & 0 \\ A & D & -A \\ -A & -D & A \end{matrix}\right], $$ where $D:=WCW^T\succ0$. Note that the second and the third rows are the same modulo the negative sign. Suppose $\zeta=\xi+i\eta$ is a nonzero eigenvalue of $M$. Then the corresponding eigenvector for $N$ is of the form $\left[\begin{matrix} x & y & -y \end{matrix}\right]^T$ with nonzero vectors $x$ and $y$. This gives equations $$Ax + Dy = \zeta x$$ and $$Ax + Dy + Ay = \zeta y.$$ It follows that $\zeta x = (\zeta-A)y$ and $$\zeta Dy=\zeta (\zeta-A)x = (\zeta-A)^2y=(\zeta^2-2\zeta A +A^2)y.$$ Take the inner product with $y$ and look at the imaginary part of it: $$\eta \langle Dy,y\rangle = 2\xi\eta \langle y,y\rangle - 2\eta \langle Ay,y\rangle.$$ Thus, one has $\xi>0$, provided that $\eta\neq0$. One still has the same conclusion for $\eta=0$ because $\zeta Dy=(\zeta-A)^2y$.

$\endgroup$
1
  • $\begingroup$ I got the full answer, but leave this as a record. $\endgroup$ Nov 8, 2021 at 14:07
2
$\begingroup$

This is only for the case n=1. Clearly the claim is true if B=0. Hence it suffices to show that there is never a zero or purely imaginary eigenvalue. The case of a zero eigenvalue leads to $a(ac-b^2)=0$, but this quantity is positive by assumption. The case of a purely imaginary eigenvalue $iy$ leads to the pair of equations $$A(AC-B^2)-y^2(2A+C)=0,$$ $$-A^2+2(B^2-AC)+y^2=0.$$ By elimination we conclude that $$(y^2-A^2)/2=y^2(2A+C)/A.$$ This is a contradiction, since the left hand side is less than $y^2/2$, and the right hand side is greater than $2y^2$.

$\endgroup$
3
  • $\begingroup$ Thanks. I don't understand the "it suffices..." part: why can't this matrix have an eigenvalue with non-zero real part? $\endgroup$
    – PAb
    Nov 5, 2021 at 10:37
  • $\begingroup$ PAb: If it ever had an eigenvalue with negative real part, then, for some B, it would have an eigenvalue with zero real part (intermediate value theorem). $\endgroup$ Nov 5, 2021 at 11:09
  • $\begingroup$ Thanks, that's a neat trick then ! So the 1d case is solved. However, I don't see how we can adapt this to the general case. $\endgroup$
    – PAb
    Nov 5, 2021 at 11:51
2
$\begingroup$

Since there is not much progress on this question, let me give a partial result and a direct consequence.

Denote $S=C-B^TA^{-1}B$ the Schur complement of $A$ in $N$, which is positive definite. Then $M$ factorizes $UL$ with $$U=\begin{pmatrix} A & B & 0 \\ 0 & S & -B^T \\ 0 & 0 & A \end{pmatrix},\qquad L=\begin{pmatrix} I & 0 & 0 \\ 0 & I & 0 \\ -I & 0 & I \end{pmatrix}.$$ We derive the formula $\det M=\det U\det L=(\det A)^2\det S$, that is $$\det M=\det A\cdot\det N.$$

I have also been interested in the limit case where $S=0$, because if the OP's statement is true, then it remains true for this limit. Denoting $K=A^{-1}B$, one finds the characteristic polynomial $$\chi_M(X)=X^n\det((XI-A)^2-XKK^TA).$$ This raises the sub-question:

Assume that $A,H$ are symmetric and positive definite. Is it true that the roots of $\det((XI-A)^2-XHA)$ have a positive real part ?

The answer is obviously positive when $H=h^2I$. Could this polynomial be the characteristic polynomial of some matrix $Q$ such that $Q+Q^T$ is positive definite ?

$\endgroup$
1
  • $\begingroup$ Thanks a lot for your help ! $\endgroup$
    – PAb
    Nov 10, 2021 at 11:25

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.