×

On the number of distinct rows of a matrix with bounded subdeterminants. (English) Zbl 1393.05262

Summary: 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 I. Heller [Pac. J. Math. 7, 1351–1364 (1957; Zbl 0079.01903)] 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}({1}/{\log\log n})}\), the number \(m\) of rows of \(A\) is bounded by a polynomial in \(n\).

MSC:

05D99 Extremal combinatorics
15B36 Matrices of integers
90C10 Integer programming

Citations:

Zbl 0079.01903
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] R. P. Anstee, Forbidden configurations, discrepancy and determinants, European J. Combin., 11 (1990), pp. 15–19, . · Zbl 0735.05016
[2] R. P. Anstee, L. Rónyai, and A. Sali, Shattering news, Graphs Combin., 18 (2002), pp. 59–73, . · Zbl 0990.05123
[3] S. Artmann, F. Eisenbrand, C. Glanzer, T. Oertel, S. Vempala, and R. Weismantel, A note on non-degenerate integer programs with small subdeterminants, Oper. Res. Lett., 44 (2016), pp. 635–639, .
[4] S. Artmann, R. Weismantel, and R. Zenklusen, A strongly polynomial algorithm for bimodular integer linear programming, in Proceedings of the 49th Annual ACM Symposium on Theory of Computing (STOC), ACM, New York, 2017, pp. 1206–1219. · Zbl 1369.68350
[5] R. Bixby and W. Cunningham, Short cocircuits in binary matroids, European J. Combin., 8 (1987), pp. 213–225, . · Zbl 0642.05013
[6] N. Bonifas, M. Di Summa, F. Eisenbrand, N. Hähnle, and M. Niemeier, On sub-determinants and the diameter of polyhedra, Discrete Comput. Geom., 52 (2014), pp. 102–115, . · Zbl 1310.52013
[7] A. DasGupta, Probability for Statistics and Machine Learning. Fundamentals and Advanced Topics, Springer Texts in Statistics, Springer-Verlag, New York, 2011, . · Zbl 1233.62001
[8] M. Dyer and A. Frieze, Random walks, totally unimodular matrices, and a randomised dual simplex algorithm, Math. Program., 64 (1994), pp. 1–16, . · Zbl 0820.90066
[9] D. Haussler and E. Welzl, Epsilon-nets and simplex range queries, Discrete Comput. Geom., 2 (1987), pp. 127–151, . · Zbl 0619.68056
[10] I. Heller, On linear systems with integral valued solutions, Pacific J. Math., 7 (1957), pp. 1351–1364, . · Zbl 0079.01903
[11] J. Kung, Combinatorial geometries representable over GF(3) and GF(q). \textupI. The number of points, Discrete Comput. Geom., 5 (1990), pp. 83–95, . · Zbl 0697.51007
[12] J. Kung, The long-line graph of a combinatorial geometry. II. Geometries representable over two fields of different characteristics, J. Combin. Theory Ser. B, 50 (1990), pp. 41–53, . · Zbl 0645.05026
[13] J. Lee, Subspaces with well-scaled frames, Linear Algebra Appl., 114/115 (1989), pp. 21–56, . · Zbl 0675.90061
[14] A. Pajor, Sous-espaces \(l^n_1\) des espaces de Banach, Ph.D. thesis, Travaux en Cours 16, Hermann, Paris, 1985. · Zbl 1032.46021
[15] N. Sauer, On the density of families of sets, J. Combin. Theory Ser. A, 13 (1972), pp. 145–147, . · Zbl 0248.05005
[16] A. Schrijver, Theory of Linear and Integer Programming, John Wiley and Sons, New York, 1986. · Zbl 0665.90063
[17] S. Shelah, A combinatorial problem; stability and order for models and theories in infinitary languages, Pacific J. Math., 41 (1972), pp. 247–261. · Zbl 0239.02024
[18] W. T. Tutte, A homotopy theorem for matroids. I, II, Trans. Amer. Math. Soc., 88 (1958), pp. 144–174, . · Zbl 0081.17301
[19] V. Vapnik and A. Chervonenkis, On the uniform convergence of relative frequencies of events to their probabilities, Theory Probab. Appl., 16 (1971), pp. 264–280, . · Zbl 0247.60005
[20] S. Veselov and A. Chirkov, Integer program with bimodular matrix, Discrete Optim., 6 (2009), pp. 220–222, . · Zbl 1159.90463
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.