<p>This is not an answer, but another version, <strong>NOT</strong> equivalent to the original of this excellent, but perhaps hard to grasp question.
Define the <em>bipartite clique partition number</em> of a graph as the least number of its complete bipartite subgraphs that cover each edge exactly once.
Similarly define the <em>support of the fractional bipartite clique partition number</em> 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.</p>

<p>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.</p>

CC BY-SA 3.0
2015-01-28T06:50:20.277Z
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?
Turbo
CC BY-SA 3.0
2015-01-28T07:19:08.617Z
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.
domotorp
CC BY-SA 3.0
2015-01-28T07:26:24.500Z
I've edited my "answer," hopefully now it's ok and self-explanatory.
domotorp
CC BY-SA 3.0
2015-01-27T21:47:25.707Z
2015-01-28T07:25:06.343Z
2015-01-28T07:25:06.343Z
domotorp
<p>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 <a href="http://cjtcs.cs.uchicago.edu/articles/2016/2/cj16-02.pdf" rel="nofollow noreferrer">http://cjtcs.cs.uchicago.edu/articles/2016/2/cj16-02.pdf</a> says the gap can be at least subexponential.</p>

CC BY-SA 3.0
2018-01-07T03:27:17.333Z
Thm 1.1. gives an exponential separation for partial matrices. I thought your question was for full matrices. Then the paper gives constant separation.
Sasho Nikolov
CC BY-SA 3.0
2018-01-06T22:19:50.647Z
2018-01-07T08:44:10.927Z
2018-01-07T08:44:10.927Z
Turbo
<p>The <em>positive rank</em> of a square matrix is defined in Theorem $3$ of <a href="http://dx.doi.org/10.1016/0022-0000(91)90024-Y" rel="nofollow noreferrer">"Expressing Combinatorial Optimization Problems by Linear Programs"</a> 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$.</p>

<p>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.</p>

<p>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$? </p>

<p>I think Theorem 1.1 in <a href="http://cjtcs.cs.uchicago.edu/articles/2016/2/cj16-02.pdf" rel="nofollow noreferrer">http://cjtcs.cs.uchicago.edu/articles/2016/2/cj16-02.pdf</a> answers this.</p>

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

<p>The converse is direct.</p>

CC BY-SA 3.0
2018-01-06T22:14:26.840Z
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
CC BY-SA 3.0
2018-01-07T01:00:09.190Z
@SashoNikolov do we know what happens if non-negative rank and real rank are not quasipolynomially related?
Turbo
CC BY-SA 3.0
2018-01-07T03:31:44.607Z
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
CC BY-SA 3.0
2018-01-07T08:57:16.147Z
@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?
Turbo
<co.combinatorics><communication-complexity>
On the notion of positive rank
Turbo
# On the notion of positive rank

(Asked by: username_0 on 2015-01-24)

The *positive rank* of a square matrix is defined in Theorem $3$ of ["Expressing Combinatorial Optimization Problems by Linear Programs"](http://dx.doi.org/10.1016/0022-0000(91)90024-Y) 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.

**Tags:** co.combinatorics, communication-complexity
> **Comments:**
> **username_1**: 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.  
> **username_0**: @SashoNikolov do we know what happens if non-negative rank and real rank are not quasipolynomially related?  
> **username_1**: 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.  
> **username_0**: @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?  

---

## 2 answers

### Answer by username_2 on 2015-01-27. Score: 4

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.

> **Comments:**
> **username_0**: 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?  
> **username_2**: 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.  
> **username_2**: I've edited my "answer," hopefully now it's ok and self-explanatory.  

---

### Answer by username_0 on 2018-01-06. Score: 0

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.

> **Comments:**
> **username_1**: Thm 1.1. gives an exponential separation for partial matrices. I thought your question was for full matrices. Then the paper gives constant separation.  

---

