{"id":"arxiv/2609.19703","url":"https://arxiv.org/abs/2609.19703","tags":["math.CO","cs.DM"],"score":0,"title":"On integral polytopes related to Edmonds' problem","domain":"math.CO","source":"arxiv","authors":["Hiroshi Hirai"],"reviews":0,"subject":"math.CO","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-09-17","reactions":{}}