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 = ∑_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} = ∑_k=1^m A_k ⊗ X_k (d=1,2,…). By extending previously known results on nc-rank, we establish a hierarchy of integral polytopes cal P(A) ⊆ cal P^{≤ 2}(A) ⊆ cal P^{≤ 3}(A) ⊆ ⋯ = 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.

Solving the scattering problem for open wave-guide networks, I: Fundamental solutions and integral equations
Charles L. Epstein
Pure and Applied Analysis18 Jul 2026Peer-reviewedLicence not statedFull text5 citedGeneral mathematicsOpenAlex
An Integral Equation for the Surface Current in the Problem of the Natural Modes of a Waveguide Containing a Resistive Film
I. M. Braver, Kh. L. Garb, P. Sh. Fridberg
arXiv27 Oct 2026PreprintCC BY 4.0Full textMathematical physics General physicsarXiv
Integral Dependence over One-Sided Ideals, Part II: G-Left Ideals and the Köthe Problem
Masood Aryapoor
arXiv22 Sep 2026PreprintCC BY-NC-SA 4.0Full textAlgebra & number theoryarXiv
The Prouhet--Tarry--Escott problem for subsets with small doubling in integral domains
Ernie Croot, Junzhe Mao, Chi Hoi Yip
arXiv4 Sep 2026PreprintarXiv licenceFull textAlgebra & number theory Combinatorics & discrete mathematicsarXiv
Nonzero Forms related to Hopf Problem of Six-Sphere
Jun Ling
HAL18 Sep 2026PreprintLicence Ouverte 2.0Full textGeneral mathematicsHAL

Cite

BibTeX RIS

BibTeX

@misc{hirai2026integral,
  title = {{On integral polytopes related to Edmonds' problem}},
  author = {Hiroshi Hirai},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.19703},
  eprint = {2609.19703},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.19703},
  note = {CC BY 4.0},
}

RIS

TY  - UNPB
TI  - On integral polytopes related to Edmonds' problem
AU  - Hiroshi Hirai
PY  - 2026
DA  - 2026/09/17
PB  - arXiv
DO  - 10.48550/arxiv.2609.19703
UR  - https://arxiv.org/abs/2609.19703
AB  - In this paper, we study polyhedral aspects on commutative and noncommutative Edmonds' problems for computing the rank of linear symbolic matrix A = ∑_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} = ∑_k=1^m A_k ⊗ X_k (d=1,2,…). By extending previously known results on nc-rank, we establish a hierarchy of integral polytopes cal P(A) ⊆ cal P^≤ 2(A) ⊆ cal P^≤ 3(A) ⊆ ⋯ = 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.
ER  -

Abstract

Related

Cite