Suppose $A \in \mathbb{R}^{n \times n}$ has positive entries on it main diagonal and $\mbox{rank}(A) =: d < n$. Then, what is the maximum number of many negative entries $A$ can contain?

If, in addition, $A$ is positive semidefinite (PSD), then using the fact that in $d$-dimensional space there are at most $d+1$ vectors with pairwise negative inner product and Turán's Theorem from graph theory we can bound the number of negative entries by roughly $$\left(\frac{d-1}{d}\right) n^2$$

But what if $A$ is not PSD?

I've been stuck with this problem for a while. Any helpful reference is greatly appreciated!

  • 1
    $\begingroup$ Do you have results for special d, e.g. d = 1 or d = N-1? (sorry, MathJax seems to be broken somehow...) $\endgroup$ – Dirk Liebhold Feb 1 '18 at 10:40
  • $\begingroup$ The case where $d=1$ is easy. When $d=N-1$, actually all the off-diagonal entries can be negative. $\endgroup$ – Richard D. Feb 2 '18 at 3:37
  • $\begingroup$ Sounds like d=N-2 might be the first “intermediate” case on the upper part of the range, then. Perhaps getting a formula for it would help. $\endgroup$ – Abel Molina Feb 5 '18 at 9:13

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.