# On the notion of positive rank of a matrix

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

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 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}$.

• 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.
– Mr.
Jan 21 '15 at 2:24
• 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. Jan 21 '15 at 2:34
• 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)})}$? Jan 21 '15 at 2:36
• I did not think about that. Also I believe you meant $O(n^2)$ bit lengths in comment, correct?
– Mr.
Jan 21 '15 at 2:42
• 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. Jan 21 '15 at 4:33