6
$\begingroup$

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.

Improve this question
$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$
    – Sasho Nikolov
    Commented Jan 6, 2018 at 22:14
  • $\begingroup$ @SashoNikolov do we know what happens if non-negative rank and real rank are not quasipolynomially related? $\endgroup$
    – Turbo
    Commented Jan 7, 2018 at 1:00
  • $\begingroup$ 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. $\endgroup$
    – Sasho Nikolov
    Commented Jan 7, 2018 at 3:31
  • $\begingroup$ @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? $\endgroup$
    – Turbo
    Commented Jan 7, 2018 at 8:57

2 Answers 2

Reset to default
4
$\begingroup$

This is not an answer, but another version, NOT equivalent to the original of this excellent, but perhaps hard to grasp question. Define the bipartite clique partition number of a graph as the least number of its complete bipartite subgraphs that cover each edge exactly once. Similarly define the support of the fractional bipartite clique partition number of a graph as the least number of its complete bipartite subgraphs that have a positive weighing such that for each edge the sum of the weights of the subgraphs containing it is exactly one. The question is whether these two parameters are always equal or not.

I find it quite surprising that while fractional version are studied a lot, I've never heard of studying the size of the support of the fractional version. I also wonder whether this latter parameter has any applications. Also, the question could be asked about several other parameters.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Could you clarify why bipartite clique number corresponds to 0/1 decomposition and fractional version corresponds to positive rank? Is Huang-Sudokov result on Alon-Saks-Seymour conjecture relevant here? $\endgroup$
    – Turbo
    Commented Jan 28, 2015 at 6:50
  • 1
    $\begingroup$ I don't think it's relevant as there the biclique partition number is small, here we want it to be large and the support of the fractional version small. $\endgroup$
    – domotorp
    Commented Jan 28, 2015 at 7:19
  • $\begingroup$ I've edited my "answer," hopefully now it's ok and self-explanatory. $\endgroup$
    – domotorp
    Commented Jan 28, 2015 at 7:26
0
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thm 1.1. gives an exponential separation for partial matrices. I thought your question was for full matrices. Then the paper gives constant separation. $\endgroup$
    – Sasho Nikolov
    Commented Jan 7, 2018 at 3:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.