<p>There are examples of $n\times n$ real matrices of rank at most $3$ and non-negative rank at least $\sqrt{2n}$. So the non-negative rank cannot be bounded by any function of the rank in general. The construction I am aware of goes through extension complexity. An explanation follows.</p>

<p>The extension complexity $xc(K)$ of a convex set $K$ in $\mathbb{R}^d$ is the smallest possible number of facets of a (higher-dimensional) polytope that projects to $K$. (Equivalently the smallest possible number of constraints in a linear program for $K$). A famous theorem of Yannakakis shows that if there exist $A$, $b$ and $v_1, \ldots, v_n$ such that $K = \{x: Ax \leq b\} = \mathrm{conv}(v_1, \ldots, v_n)$, then 
$$
xc(K) = \mathrm{rank}^+(S),
$$
where $S$ is the slack matrix, defined by $S = b1^T - A^TV$ for $V = (v_1, \ldots, v_n)$, i.e. the matrix whose columns are the $v_i$.</p>

<p>A <a href="http://arxiv.org/abs/1107.0371" rel="nofollow">result by Fiorini, Rothvoss, and Tiwari</a> shows that there exist two-dimensional $n$-gons with extension complexity at least $\sqrt{2n}$. Since any $n$-gon $P$ in $\mathbb{R}^2$ can be written as $P = \{x: Ax \leq b\} = \mathrm{conv}(v_1, \ldots, v_n)$ for $A$ an $n\times 2$ matrix, $b$ an $n\times 1$ vector and $V = (v_1, \ldots, v_n)$ a $2\times n$ matrix, the slack  matrix $S = b1^T - A^TV$ of $P$ is the sum of a rank $1$ and a rank $2$ matrix, and therefore is of rank at most $3$. On the other hand by Yannakakis's and Fiorini et al.'s results $\mathrm{rank}^+(S) = xc(P) \geq \sqrt{2n}$. </p>

CC BY-SA 3.0
2015-01-21T02:24:20.443Z
So what is preventing $0-1$ matrix to have such separation? I do not see it from your answer. It seems picking right $K$ could give us just right $b,A,V$? Would this approach not work? It seems that would prove same with $0-1$ matrix as well.
Turbo
CC BY-SA 3.0
2015-01-21T02:34:19.650Z
A 0-1 slack matrix is quite restrictive for $K$. In fact the theorem I stated from Fiorini et all uses an $n$-gon with *transcendental* vertices. They show a slightly weaker bound for an $n$-gon with integer vertices bounded by $O(n^2)$. But large bit lengths are crucial to their approach.
Sasho Nikolov
CC BY-SA 3.0
2015-01-21T02:36:13.320Z
Also doesn't Lovett's bound for the log-rank conjecture imply that $\mathrm{rank}^+(M) \leq 2^{D(M)} \leq 2^{\tilde{O}(\sqrt{\mathrm{rank}(M)})}$?
Sasho Nikolov
CC BY-SA 3.0
2015-01-21T02:42:56.947Z
I did not think about that. Also I believe you meant $O(n^2)$ bit lengths in comment, correct?
Turbo
CC BY-SA 3.0
2015-01-21T04:33:43.590Z
A facet of an $n$-dimensional polytope is an $n-1$ dimensional face. I meant that each point in the $n$-gon is a vector with integer coordinates bounded by $O(n^2)$ in magnitude: see Theorem 8 in the paper I linked.
Sasho Nikolov
CC BY-SA 3.0
2015-01-24T07:47:47.627Z
If $A$ is $0/1$ is it sufficient to consider minimum number of $rank=1$ $0/1$ matrices that sum to $A$ in order to compute $rank^+(A)$?
Turbo
CC BY-SA 3.0
2015-01-24T17:56:17.793Z
My guess is that it's not, but I don't know.
Sasho Nikolov
CC BY-SA 3.0
2015-02-06T03:42:48.470Z
We know $D(M)\leq log ( rk(M) )log (rk^+(M))$. Lovett's result only states, $D(M)\leq exp(\sqrt{rk(M)})$. Lovett's result is consistent with fact that $log (rk^+(M)) = rk(M)^c$. Since we will obtain $D(M)\leq exp(\sqrt{rk(M)})\leq rk(M)^c log (rk(M)) = log (rk(M)) log( rk^+(M))$. So we still could have no relation between $rk(M)$, $rk^+(M)$.
Turbo
CC BY-SA 3.0
2015-02-06T06:46:16.800Z
@Turbo What you are saying makes no sense to me! Do you disagree that $\mathrm{rank}(M) \leq \mathrm{rank}^+(M) \leq 2^{D(M)} \leq 2^{\tilde{O}(\sqrt{\mathrm{rank}(M)})}$ are all known inequalities for Boolean matrices? Isn't that a non-trivial relationship between rank and positive rank? In what you write $\exp(\sqrt{\mathrm{rank}(M)}) \leq \mathrm{rank(M)}^c\log(\mathrm{rank}(M))$ is not true except for very small rank. And while Lovett's result is consistent with stronger inequalities, I don't see what that has to do with anything.
Sasho Nikolov
CC BY-SA 3.0
2015-02-06T08:22:56.720Z
Actually I did not know the result $rank^+(M)\leq 2^{D(M)}$. I do not know why I wrote $exp(\sqrt{rk(M)})\leq rk(M)^{c+1}$ (I am wrong in this). However I did not know the previous inequality.
Turbo
CC BY-SA 3.0
2015-02-06T20:00:13.410Z
The proof for that is the same as the proof that $\mathrm{rank}(M) \leq 2^{D(M)}$. $M$ can be partitioned into $2^{D(M)}$ combinatorial rectangles, and, therefore, $M$ is the sum of $2^{D(M)}$ 0-1 matrices of rank 1.
Sasho Nikolov
CC BY-SA 3.0
2015-02-26T02:43:01.833Z
instead of "So what is preventing 0−1 or finite positive alphabet matrix to have such separation?", if I ask "So what is preventing a generic positive matrix to have such separation?", is there an explanation? In essence I am asking if we have no alphabet restriction except positive entries, would such separation be rare finds?
Turbo
CC BY-SA 3.0
2018-01-04T22:48:36.170Z
We know $rank(A)\leq rank^+(A)$. Do we know  $rank(A)=rank^+(A)$ where $A$ is $0/1$ matrix?
Turbo
CC BY-SA 3.0
2018-01-04T22:57:02.667Z
By this I mean is it possible the Nisan-Wigderson-Kushilevitz example of $\log_36\approx1.6\dots$ separation affect here? That is is it known $(rank(A))^{\log_36}\leq rank^+(A)$ holds?
Turbo
CC BY-SA 3.0
2015-01-21T02:16:51.950Z
2015-01-21T20:48:08.033Z
2015-01-21T20:48:08.033Z
Sasho Nikolov
<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">"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 subexponentially related for a $0/1$ matrix $A$, then the log-rank conjecture holds.</p>

<p>Is there an exponential separation between $rank_{\Bbb R}^+(A)$ and $rank_{\Bbb R}(A)$ for a general non-negative real matrix $A$ (as opposed to just $0/1$) or is this problem also open?</p>

<p>I checked the references in Jukna's book, but I am still unable to clarify the above question.</p>

<communication-complexity><definitions>
On the notion of positive rank of a matrix
Turbo
# On the notion of positive rank of a matrix

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

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 subexponentially related for a $0/1$ matrix $A$, then the log-rank conjecture holds.

Is there an exponential separation between $rank\_{\Bbb R}^+(A)$ and $rank\_{\Bbb R}(A)$ for a general non-negative real matrix $A$ (as opposed to just $0/1$) or is this problem also open?

I checked the references in Jukna's book, but I am still unable to clarify the above question.

**Tags:** communication-complexity, definitions


---

## 1 answers

### Answer by username_1 on 2015-01-21. Score: 9 | Accepted answer

There are examples of $n\times n$ real matrices of rank at most $3$ and non-negative rank at least $\sqrt{2n}$. So the non-negative rank cannot be bounded by any function of the rank in general. The construction I am aware of goes through extension complexity. An explanation follows.

The extension complexity $xc(K)$ of a convex set $K$ in $\mathbb{R}^d$ is the smallest possible number of facets of a (higher-dimensional) polytope that projects to $K$. (Equivalently the smallest possible number of constraints in a linear program for $K$). A famous theorem of Yannakakis shows that if there exist $A$, $b$ and $v\_1, \ldots, v\_n$ such that $K = \{x: Ax \leq b\} = \mathrm{conv}(v\_1, \ldots, v\_n)$, then
$$
xc(K) = \mathrm{rank}^+(S),
$$
where $S$ is the slack matrix, defined by $S = b1^T - A^TV$ for $V = (v\_1, \ldots, v\_n)$, i.e. the matrix whose columns are the $v\_i$.

A [result by Fiorini, Rothvoss, and Tiwari](http://arxiv.org/abs/1107.0371) shows that there exist two-dimensional $n$-gons with extension complexity at least $\sqrt{2n}$. Since any $n$-gon $P$ in $\mathbb{R}^2$ can be written as $P = \{x: Ax \leq b\} = \mathrm{conv}(v\_1, \ldots, v\_n)$ for $A$ an $n\times 2$ matrix, $b$ an $n\times 1$ vector and $V = (v\_1, \ldots, v\_n)$ a $2\times n$ matrix, the slack matrix $S = b1^T - A^TV$ of $P$ is the sum of a rank $1$ and a rank $2$ matrix, and therefore is of rank at most $3$. On the other hand by Yannakakis's and Fiorini et al.'s results $\mathrm{rank}^+(S) = xc(P) \geq \sqrt{2n}$.

> **Comments:**
> **username_0**: So what is preventing $0-1$ matrix to have such separation? I do not see it from your answer. It seems picking right $K$ could give us just right $b,A,V$? Would this approach not work? It seems that would prove same with $0-1$ matrix as well.  
> **username_1**: A 0-1 slack matrix is quite restrictive for $K$. In fact the theorem I stated from Fiorini et all uses an $n$-gon with *transcendental* vertices. They show a slightly weaker bound for an $n$-gon with integer vertices bounded by $O(n^2)$. But large bit lengths are crucial to their approach.  
> **username_1**: Also doesn't Lovett's bound for the log-rank conjecture imply that $\mathrm{rank}^+(M) \leq 2^{D(M)} \leq 2^{\tilde{O}(\sqrt{\mathrm{rank}(M)})}$?  
> **username_0**: I did not think about that. Also I believe you meant $O(n^2)$ bit lengths in comment, correct?  
> **username_1**: A facet of an $n$-dimensional polytope is an $n-1$ dimensional face. I meant that each point in the $n$-gon is a vector with integer coordinates bounded by $O(n^2)$ in magnitude: see Theorem 8 in the paper I linked.  
> **username_0**: If $A$ is $0/1$ is it sufficient to consider minimum number of $rank=1$ $0/1$ matrices that sum to $A$ in order to compute $rank^+(A)$?  
> **username_1**: My guess is that it's not, but I don't know.  
> **username_0**: We know $D(M)\leq log ( rk(M) )log (rk^+(M))$. Lovett's result only states, $D(M)\leq exp(\sqrt{rk(M)})$. Lovett's result is consistent with fact that $log (rk^+(M)) = rk(M)^c$. Since we will obtain $D(M)\leq exp(\sqrt{rk(M)})\leq rk(M)^c log (rk(M)) = log (rk(M)) log( rk^+(M))$. So we still could have no relation between $rk(M)$, $rk^+(M)$.  
> **username_1**: @username_0 What you are saying makes no sense to me! Do you disagree that $\mathrm{rank}(M) \leq \mathrm{rank}^+(M) \leq 2^{D(M)} \leq 2^{\tilde{O}(\sqrt{\mathrm{rank}(M)})}$ are all known inequalities for Boolean matrices? Isn't that a non-trivial relationship between rank and positive rank? In what you write $\exp(\sqrt{\mathrm{rank}(M)}) \leq \mathrm{rank(M)}^c\log(\mathrm{rank}(M))$ is not true except for very small rank. And while Lovett's result is consistent with stronger inequalities, I don't see what that has to do with anything.  
> **username_0**: Actually I did not know the result $rank^+(M)\leq 2^{D(M)}$. I do not know why I wrote $exp(\sqrt{rk(M)})\leq rk(M)^{c+1}$ (I am wrong in this). However I did not know the previous inequality.  
> **username_1**: The proof for that is the same as the proof that $\mathrm{rank}(M) \leq 2^{D(M)}$. $M$ can be partitioned into $2^{D(M)}$ combinatorial rectangles, and, therefore, $M$ is the sum of $2^{D(M)}$ 0-1 matrices of rank 1.  
> **username_0**: instead of "So what is preventing 0−1 or finite positive alphabet matrix to have such separation?", if I ask "So what is preventing a generic positive matrix to have such separation?", is there an explanation? In essence I am asking if we have no alphabet restriction except positive entries, would such separation be rare finds?  
> **username_0**: We know $rank(A)\leq rank^+(A)$. Do we know  $rank(A)=rank^+(A)$ where $A$ is $0/1$ matrix?  
> **username_0**: By this I mean is it possible the Nisan-Wigderson-Kushilevitz example of $\log_36\approx1.6\dots$ separation affect here? That is is it known $(rank(A))^{\log_36}\leq rank^+(A)$ holds?  

---

