On the column number and forbidden submatrices for $Δ$-modular matrices Article Swipe

MAKE IMPACT

Joseph Paat , Ingo Stallknecht , Zach Walsh , Luze Xu · YOU? · · 2022 · Open Access · · DOI: https://doi.org/10.48550/arxiv.2212.03819

An integer matrix $\mathbf{A}$ is $Δ$-modular if the determinant of each $\text{rank}(\mathbf{A}) \times \text{rank}(\mathbf{A})$ submatrix of $\mathbf{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 $Δ\in \{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 $\binom{r+1}{2} + 80Δ^7 \cdot r$ nonzero, pairwise non-parallel columns, which is tight up to the term $80Δ^7$. This is the first upper bound of the form $\binom{r+1}{2} + f(Δ)\cdot 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.

Type

preprint

Language

en

Landing Page

http://arxiv.org/abs/2212.03819

PDF

https://arxiv.org/pdf/2212.03819

OA Status

green

Related Works

10

OpenAlex ID

https://openalex.org/W4310926648

Raw OpenAlex JSON

OpenAlex ID

https://openalex.org/W4310926648

Canonical identifier for this work in OpenAlex

DOI

https://doi.org/10.48550/arxiv.2212.03819

Digital Object Identifier

Title

On the column number and forbidden submatrices for $Δ$-modular matrices

Work title

Type

preprint

OpenAlex work type

Language

en

Primary language

Publication year

2022

Year of publication

Publication date

2022-12-07

Full publication date if available

Authors

Joseph Paat, Ingo Stallknecht, Zach Walsh, Luze Xu

List of authors in order

Landing page

https://arxiv.org/abs/2212.03819

Publisher landing page

PDF URL

https://arxiv.org/pdf/2212.03819

Direct link to full text PDF

Open access

Yes

Whether a free full text is available

OA status

green

Open access status per OpenAlex

OA URL

https://arxiv.org/pdf/2212.03819

Direct OA link when available

Concepts

Combinatorics, Conjecture, Integer (computer science), Rank (graph theory), Matrix (chemical analysis), Mathematics, Modular form, Discrete mathematics, Pure mathematics, Computer science, Composite material, Programming language, Materials science

Top concepts (fields/topics) attached by OpenAlex

Cited by

0

Total citation count in OpenAlex

Related works (count)

10

Other works algorithmically related by OpenAlex

Full payload