On the Number of Distinct Rows of a Matrix with Bounded Subdeterminants

Abstract

Let $A \in \mathbb{Z}^{m \times n}$ be a matrix with $\mathrm{rank}(A) = n$, whose $(n \times n)$-submatrices have a determinant of at most ${\mathop{\vartriangle}}$ in absolute value. Assume that $A$ does not contain the zero-row, nor any duplicate rows, and neither two rows where one is the negation of the other. Under these assumptions, we show that $m \leq \frac{1}{2} \cdot {\mathop{\vartriangle}}^{\log_2\log_2{\mathop{\vartriangle}} + 2} \cdot n^2$ for ${\mathop{\vartriangle}} \geq 2$ and $m \leq \frac{1}{2} \cdot (n^2 + n)$ for ${\mathop{\vartriangle}} = 1$. The latter case is an immediate consequence of a well-known bound by Heller [Pacific J. Math., 7 (1957), pp. 1351--1364] showing that totally unimodular matrices admit at most $\frac{1}{2} \cdot (n^2 + n)$ distinct rows. Our result extends Heller's bound in the sense that even for ${\mathop{\vartriangle}} = n^{\mathcal{O}(\sfrac{1}{\log\log n})}$, the number $m$ of rows of $A$ is bounded by a polynomial in $n$.