Integral polytopes clarify rank problems in symbolic matrices
On integral polytopes related to Edmonds' problem
Discrete Mathematics
Summary
This paper looks at how to better understand the rank of certain symbolic matrices, which are matrices with variables instead of fixed numbers. The authors study geometric shapes called polytopes that represent these matrices in two different ways, one connected to normal matrices and another to a more complex, 'noncommutative' version. They reveal a sequence of polytopes that bridge these two versions and measure how different they can be from each other. For special types of matrices built from rank-2 skew-symmetric blocks, they find the sequence stops early and the difference is smaller.
What this means in practice
- •For algorithm designers: Determine tighter bounds for rank computations of symbolic matrices used in optimization problems.
- •For computational algebra developers: Improve symbolic computation tools by exploiting the structure of integral polytopes linked to matrix ranks.
A theory result. No direct application yet.
Authors
Hiroshi Hirai
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 ${\cal P}(A)$ and ${\cal 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,\ldots)$. By extending previously known results on nc-rank, we establish a hierarchy of integral polytopes ${\cal P}(A) \subseteq {\cal P}^{\leq 2}(A) \subseteq {\cal P}^{\leq 3}(A) \subseteq \cdots = {\cal Q}(A)$ and show that the integrality gap of ${\cal Q}(A)$ relative to ${\cal 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$.