1
$\begingroup$

Consider the $n\times n$ matrix $F$ defined by the following expression $$ F=A-\epsilon 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 conditions on $A$ and $B$ such that $F$ is positive semi-definite when the scalar $\epsilon>0$ is small enough.

Of course, this works if $B$ is negative semi-definite but I am looking for more general conditions, if possible.

$\endgroup$
2
$\begingroup$

Some thoughts:

It's easy to explain the case in which $B$ is symmetric positive-semidefinite.

Write $A = a \mathbf 1\mathbf 1^T$, where $\mathbf 1$ is the column-vector of $1$s. Note that $$ x^T(A - \epsilon B)x = x^TAx - \epsilon (x^TBx) $$ $A - \epsilon B$ is positive semidefinite if the above is non-negative for all vectors $x$. Consequently, we must have $x^TAx = 0 \implies x^TBx = 0$, which in turn means that $Ax = 0 \implies Bx = 0$. In other words, the nullspace of $B$ must include the nullspace of $A$.

From this, we may conclude that $B$ must also be a multiple of $\mathbf 1\mathbf 1^T$ (i.e. it must also be a constant matrix).

More generally, we can write $B = B^+ - B^-$ where $B^\pm$ are positive semidefinite with $B^+B^- = B^-B^+ = 0$ (in particular: $B^\pm$ are simultaneously diagonalizable). We have $$ x^T(A - \epsilon B)x = x^T(A + \epsilon B^-)x - \epsilon x^TB^+x\\ = [a(\mathbf 1^Tx)^2 + \epsilon x^TB^-x] - \epsilon x^TB^+ x $$ It is necessary (but not sufficient) that we have $(A + \epsilon B^-)x = 0 \implies B^+ x = 0$ for sufficiently small $\epsilon$.

Among the vectors $x$ such that $\mathbf 1^Tx = 0$, this condition becomes $B^- x = 0 \implies B^+ x = 0$. This tells us that if $B$ has an eigenvector parallel to $\mathbf 1$, we must have $B^- = 0$, which reduces to our earlier case.


Note that there are some examples in which $B$ is not positive semidefinite. In particular, we can take $$ B = \pmatrix{0&1\\1&0}, \quad a = 1 $$ In general: I suspect that if all diagonal entries of $B$ are zero, then $B$ will satisfy the required condition.

$\endgroup$
  • $\begingroup$ Thanks, this is useful. I also feel that if the diagonal of $B$ is zero then there should be $\epsilon$ small enough so that $F$ is positive semi-definite. If $n=2$ then this works since for $\epsilon$ small enough $$F=\left[\begin{array}{cc} a & a-\epsilon b\\ a-\epsilon b & a \end{array}\right]$$ is diagonally dominant but I'm unable to generalize the argument to $n>2$. $\endgroup$ – user_lambda Jun 11 '17 at 19:27

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.