Excluding a Line Minor via Design Matrices and Column Number Bounds for the Circuit Imbalance Measure

For a real matrix \(\textbf A \in \mathbb{R}^{d \times n}\) with non-collinear columns, we show that \(n \le O(d^{4} \kappa_\textbf A)\) where \(\kappa_\textbf A\) is the circuit imbalance measure of \(\textbf A\). The circuit imbalance measure \(\kappa\) is a real analogue of \(\Delta\)-modularity for integer matrices, satisfying \(\kappa_\textbf A \le \Delta_\textbf A\) for integer \(\textbf A\). The circuit imbalance measure has numerous applications in the context of linear programming (see Ekkbatani, Natura and Végh (2022) for a survey). Our result generalizes the \(O(d^{4} \Delta_\textbf A)\) bound of Averkov and Schymura (2023) for integer matrices and provides the first polynomial bound holding for all parameter ranges on real matrices.