4
$\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 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.

$\endgroup$
8
$\begingroup$

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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