# Maximum number of negative entries in a matrix with positive diagonal and given rank

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!

• Do you have results for special d, e.g. d = 1 or d = N-1? (sorry, MathJax seems to be broken somehow...) – Dirk Liebhold Feb 1 '18 at 10:40
• The case where $d=1$ is easy. When $d=N-1$, actually all the off-diagonal entries can be negative. – Richard D. Feb 2 '18 at 3:37
• 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. – Abel Molina Feb 5 '18 at 9:13