3
$\begingroup$

Consider the $n\times n$ matrix $F$ defined by the following expression $$ F=A-\varepsilon B $$ where $A$ is a constant matrix such that $a_{ij}=a>0$ for all $i,j$ and where $B$ is a symmetric matrix such that $b_{ij}\geq 0$ for all $i,j$.

I would like to find sufficient conditions on $A$ and $B$ such that $F$ is positive semi-definite when the scalar $\varepsilon>0$ is small enough.

Of course, this works if $B$ is negative semi-definite. It also works for $n=2$ if the diagonal elements of $B$ are 0. In this case $$ F=\left[\begin{array}{cc} a & a-\varepsilon b\\ a-\varepsilon b & a \end{array}\right] $$is diagonally dominant for $\varepsilon$ small enough. Sadly I'm unable to generalize this zero-diagonal case to $n>2$.

$\endgroup$
1
  • 1
    $\begingroup$ A sufficient condition is that $B$ is strictly negative definite on the orthogonal complement of the vector $(1,1,...,1)$. $\endgroup$ – Michael Renardy Jun 12 '17 at 14:49
3
$\begingroup$

Let $P$ denote an orthogonal projection onto the hyperplane $H:\sum x_i=0$. If $A-\varepsilon B$ is positive semi-definite, so is $P(A-\varepsilon B)P=-\varepsilon PBP$, thus we get a necessary condition: $PBP$ should be non-positive definite.

If $PBP$ is negative definite on $H$ (that is, the quadratic form $(Bx,x)$ is negative definite on $H$: $(Bx,x)\leqslant -c\|x\|^2$), this is a sufficient condition, that is, then $A-\varepsilon B$ is actually non-negative definite. Indeed, take a vector $z=x+y$, where $x\in H$, $y\perp H$. We get $$((A-\varepsilon B)z,z)=n\|y\|^2-\varepsilon (Bx,x)-2\varepsilon (Bx,y)-\varepsilon (By,y)\geqslant (n-1/2)\|y\|^2+c\varepsilon \|x\|^2-2\cdot \varepsilon \cdot \|B\|\cdot\|x\|\cdot\|y\|\geqslant 0$$ if $\varepsilon >0$ is small enough. If $PB$ has non-trivial kernel on $H$, the situation is more delicate. Namely, we may write any vector as $z=x_1+x_2+y$, where $y\perp H$ as before; $x_1,x_2\in H$, $Bx_2\perp H$ and $(Bx_1,x_1)\leqslant -c \|x_1\|^2$. We have $(Az,z)=n\|y\|^2$ as before and $(Bz,z)=2(Bx_1,y)+2(Bx_2,y)+(By,y)+(Bx_1,x_1)$. There are two subcases:

1) $Bx_2=0$ always, that is, the kernel of $PB$ on $H$ is contained in the kernel of $B$. Then the same argument works.

This is already necessary and sufficient condition. Indeed, if

2) $Bx_2\ne 0$ for some $x_2$. Then for any fixed $\varepsilon>0$ taking $x_1=0$ and $y$ of suitable sign and very small we get $((A-\varepsilon B)(x_2+y),(x_2+y))<0$.

$\endgroup$
3
  • $\begingroup$ Thanks a lot for this answer. I'm confused about something: how do we get $$-\varepsilon(By,y)-2\varepsilon(Bx,y)\geqslant-1/2\|y\|^{2}-2\cdot\varepsilon\cdot\|B\|\cdot\|x\|\cdot\|y\|?$$ In particular, how does $1/2$ show up in there? $\endgroup$ – user_lambda Jun 13 '17 at 13:00
  • 1
    $\begingroup$ For small enough $\varepsilon$ it holds, yes? $\endgroup$ – Fedor Petrov Jun 13 '17 at 13:39
  • $\begingroup$ It seems that a similar argument would show that if $B$ is negative definite on $H$ and $\varepsilon$ is small enough than $F$ is positive definite. Is this also true? $\endgroup$ – user_lambda Jul 10 '18 at 17:06

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.