2022/12/07 by Joseph Paat, Paat, Joseph, Ingo Stallknecht +5
Computer Science · Mathematics · #Advanced Algebra and Logic #Advanced Topology and Set Theory #Combinatorics (math.CO) #Constraint Satisfaction and Optimization #FOS: Mathematics #Optimization and Control (math.OC)
paper · pdf · doi:10.48550/arxiv.2212.03819
openalex publication_date 2022/12/07 · openalex created_date 2022/12/21 · openalex updated_date 2026/07/28
An integer matrix A is Δ-modular if the determinant of each rank(A) × rank(A) submatrix of A has absolute value at most Δ. The study of Δ-modular matrices appears in the theory of integer programming, where an open conjecture is whether integer programs defined by Δ-modular constraint matrices can be solved in polynomial time if Δ is considered constant. The conjecture is only known to hold true when Δ∈ \1,2\. In light of this conjecture, a natural question is to understand structural properties of Δ-modular matrices. We consider the column number question -- how many nonzero, pairwise non-parallel columns can a rank-r Δ-modular matrix have? We prove that for each positive integer Δ and sufficiently large integer r, every rank-r Δ-modular matrix has at most \binomr+12 + 80Δ7 ⋅ r nonzero, pairwise non-parallel columns, which is tight up to the term 80Δ7. This is the first upper bound of the form \binomr+12 + f(Δ)⋅ r with f a polynomial function. Underlying our results is a partial list of matrices that cannot exist in a Δ-modular matrix. We believe this partial list may be of independent interest in future studies of Δ-modular matrices.