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

Abstract

An integer matrix $\mathbf{A}$ is $\Delta$-modular if the determinant of each $\text{rank}(\mathbf{A})\times \text{rank}(\mathbf{A})$ submatrix of $\mathbf{A}$ has absolute value at most $\Delta$. The study of $\Delta$-modular matrices appears in the theory of integer programming, where an open conjecture is whether integer programs defined by $\Delta$-modular constraint matrices can be solved in polynomial time if $\Delta$ is considered constant. The conjecture is only known to hold true when $\Delta \in \{1,2\}$. In light of this conjecture, a natural question is to understand structural properties of $\Delta$-modular matrices. We consider the column number question -- how many nonzero, pairwise non-parallel columns can a rank-$r$ $\Delta$-modular matrix have? We prove that for each positive integer $\Delta$ and sufficiently large integer $r$, every rank-$r$ $\Delta$-modular matrix has at most $\left(\genfrac{}{}{0ex}{}{r+1}{2}\right)+80{\Delta }^7\cdot r$ nonzero, pairwise non-parallel columns, which is tight up to the term $80{\Delta }^7$. This is the first upper bound of the form $\left(\genfrac{}{}{0ex}{}{r+1}{2}\right)+f(\Delta )\cdot r$ with $f$ a polynomial function. Underlying our results is a partial list of matrices that cannot exist in a $\Delta$-modular matrix. We believe this partial list may be of independent interest in future studies of $\Delta$-modular matrices.