2
$\begingroup$

Consider the $n\times n$ matrix $F$ defined as $$ 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 $B$ such that $F$ is positive definite when the scalar $\varepsilon>0$ is small enough.

Over at Mathoverflow Fedor Petrov shows that $F$ is positive semidefinite for $\varepsilon$ small enough if $B$ is positive definite on the subspace $H:\sum_i x_i=0$. It seems that a similar argument should works to show that $F$ is positive definite. I am probably missing something but can't figure out what.

Edit: Following Fedor's arguments, here is how I think the proof would go:

Since $B$ is negative definite on $H$, we have that $(Bx,x)\leqslant -c\|x\|^2$ for $x\in H$. We can write any vector $z$ as $z=x+y$ where $x\in H$ and $y \perp H$. Then \begin{align}((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\|\end{align} for $\varepsilon>0$ small enough. This last expression is strictly convex in $\left(\|x\|,\|y\|\right)$ when $\varepsilon>0$ is small enough and reaches it minimum of 0 at $\left(\|x\|,\|y\|\right)=(0,0)$ or, equivalently, at $z=0$. Since $((A-\varepsilon B)z,z)>0$ for any $z\neq 0$, $((A-\varepsilon B)z,z)$ is positive definite.

Is there anything wrong with this proof?

$\endgroup$
1
$\begingroup$

The sufficient condition given in that MO answer is already one that makes $F$ positive definite for small $\varepsilon>0$.

In general, suppose $A$ and $B$ are two Hermitian matrices of the same sizes (whether they are entrywise positive/nonnegative is unimportant). If $A-\varepsilon B$ is positive semidefinite for every small $\varepsilon>0$, then by passing $\varepsilon$ to the limit, $A$ must be positive semidefinite. If $A$ is indeed positive semidefinite, denote its restriction on $(\ker A)^\perp$ as $A_1$. Then $A_1$ is positive definite and we may write $F=A-\varepsilon B$ in the form of $$ F=\pmatrix{A_1-\varepsilon X&-\varepsilon Y^\ast\\ -\varepsilon Y&-\varepsilon Z}. $$ Therefore, a necessary condition for $F$ to be positive semidefinite for every small $\varepsilon>0$ is that $A$ is positive semidefinite and $Z=(I-A^+A)B(I-A^+A)$ is negative semidefinite on $\ker A$.

However, if $A$ is positive semidefinite but $Z$ is negative definite on $\ker A$, we get a sufficient condition. This should be evident, because $F$ is congruent to $(-\varepsilon Z)\oplus S$, where \begin{align} S&=A_1-\varepsilon X-(-\varepsilon Y^\ast)(-\varepsilon Z)^{-1}(-\varepsilon Y)\\ &=A_1-\varepsilon (X-Y^\ast Z^{-1}Y) \end{align} is the Schur complement of $-\varepsilon Z$ in $F$. Since $A_1$ is positive definite and $Z$ is negative definite, $-\varepsilon Z,\ S,\ (-\varepsilon Z)\oplus S$ and in turn $F$ are positive definite when $\varepsilon>0$ is small.

In your case, $A$ is a positive multiple of the all-one matrix. So, $A$ is positive semidefinite, $\ker A=\{x\in\mathbb R^n:\sum_ix_i=0\}$ and $I-A^+A$, the orthogonal projection on $\ker A$, is the matrix $P$ in the MO answer you mentioned.

$\endgroup$
  • $\begingroup$ Thanks a lot for your answer! 1) Why can we write $F$ in that matrix form? 2) Given how $Z$ is written, what is the difference between "$Z$ is negative definite" and "$Z$ is negative definite on ker $A$"? Because of the projection matrix $I-A^+A$ aren't we restricting any vector $x$ to ker $A$ anyway? 3) When discussing a necessary condition for $F$ to be positive semidefinite, why is $Y$ not playing a role? Is it because it shows up in $F/(A_1-\varepsilon X)$ with $\varepsilon^2$. 4) How do we know that $F$ is congruent to $(-\varepsilon Z) \bigoplus S$? Thanks! $\endgroup$ – user_lambda Jul 11 '18 at 15:10
  • 1
    $\begingroup$ @user_lambda 1) This is just a change of basis. 2) No difference. I meant to write "B is negative definite on $\ker A$", but that was ambiguous, as $\ker A$ isn't an invariant subspace of $B$. So, I edited that $B$ to $Z$. 3) $Y$ doesn't play a role because $A_1$ is positive definite. When $\varepsilon$ is small, $A_1$, as a quadratic form, dominates $\varepsilon(X-Y^\ast Z^{-1}Y)$. In some sense this is similar to completing square, but that might take too long to explain here. 4) See the LDU decomposition in the linked Wikipedia entry for Schur complement. $\endgroup$ – user1551 Jul 11 '18 at 16:08

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.