# On the notion of positive rank

The positive rank of a square matrix is defined in Theorem $3$ of "Expressing Combinatorial Optimization Problems by Linear Programs" by Mihalis Yannakakis as follows: given a $n\times n$ matrix $A$, the positive rank $rank_{\Bbb R}^+(A)$ is the smallest $m$ such that $A=LR$ for a non-negative $n\times m$ matrix $L$, and non-negative $m\times n$ matrix $R$.

This concept is valuable in communication complexity, since it was shown that if $rank_{\Bbb R}^+(A)$ and $rank_{\Bbb R}(A)$ could be quasi-polynomially related for a $0/1$ matrix $A$, then the log-rank conjecture holds.

Is there an example of a $0/1$ matrix $A$ whose positive rank is strictly smaller than the dimension $m$ of any positive decomposition of $A$ into $0/1$ matrices $L,R$?

I think Theorem 1.1 in http://cjtcs.cs.uchicago.edu/articles/2016/2/cj16-02.pdf answers this.

Do we know that if non-negative rank and real rank are not quasipolynomially related then the log-rank conjecture fails?

The converse is direct.

• Since you found an answer to your original question, you should post it as an answer (with some details in addition to the link, for the benefit of others who will find this question in the future), and accept it. Do not just change the question to something else. – Sasho Nikolov Jan 6 '18 at 22:14
• @SashoNikolov do we know what happens if non-negative rank and real rank are not quasipolynomially related? – T.... Jan 7 '18 at 1:00
• By the log-rank conjecture, for any boolean matrix $M$, $\log \mathrm{rank}(M) \le \log \mathrm{rank}_{+}(M) \le \log \mathrm{rank}_{0,1}(M) \le D(M) \le (\log\mathrm{rank}(M))^{O(1)}$. So, assuming the conjecture, all these notions are quasipolynomially related for boolean matrices. I am pretty sure I made the exact same comment to an old question of yours. – Sasho Nikolov Jan 7 '18 at 3:31
• @SashoNikolov AFAWK can real rank ($rank(M)$) only be quasipolynomially related to $rank_{0,1}(M)$ which is $0/1$ decomposition (over $\Bbb R$ where $1+1=2$ holds) rank and related to partition number) and to non-negative rank ($rank_+(M)$) while real rank could be polynomially related (may be even linearly related) to boolean semiring rank ($rank_\Bbb B(M)$) where $1+1=1$ holds which is related to covering number? – T.... Jan 7 '18 at 8:57

I found an answer to original query of whether positive decomposition rank and $0/1$ decomposition rank over reals have large gap that holds for partial matrices. Theorem 1.1 in http://cjtcs.cs.uchicago.edu/articles/2016/2/cj16-02.pdf says the gap can be at least subexponential.