Column Number of Delta-modular matrices: Refined Analysis via Sauer Matrices

Abstract

In this paper, we build upon the analysis initiated by Gennadiy Averkov and Matthias Schymura (2022) and establish that the number of distinct columns of a $\Delta$-modular matrix $A\in {\mathbb{Z}}^{m\times n}$ of rank $m$ is $O(m^3\Delta )$. This upper bound was previously known only for odd values of $\Delta$. Recall that a matrix is called $\Delta$-modular if the maximum of the absolute values of its $m\times m$ minors equals $\Delta$.