On integral polytopes related to Edmonds' problem

Abstract

In this paper, we study polyhedral aspects on commutative and noncommutative Edmonds' problems for computing the rank of linear symbolic matrix $A={\sum }_{k=1}^m{A}_k{x}_k$. We regard them as linear optimization over integral polytopes $\mathcal{P}(A)$ and $\mathcal{Q}(A)$, respectively, which are obtained by the convex hulls of exponent vectors of subdeterminants of~$A$ and its blow-ups $A^{\{d\}}={\sum }_{k=1}^m{A}_k\otimes X_k$ $(d=1,2,\dots )$. By extending previously known results on nc-rank, we establish a hierarchy of integral polytopes $\mathcal{P}(A)\subseteq {\mathcal{P}}^{\le 2}(A)\subseteq {\mathcal{P}}^{\le 3}(A)\subseteq \cdots =\mathcal{Q}(A)$ and show that the integrality gap of $\mathcal{Q}(A)$ relative to $\mathcal{P}(A)$ is at least $1/2$. Further, we show that if each $A_k$ is rank-2 skew-symmetric, then the above hierarchy terminates at the second level and the integrality gap is improved to $2/3$.