Maximal determinants of sparse zero-one matrices

Abstract

We give upper bounds for the determinant of an $n\times n$ zero-one matrix containing $kn$ ones for integral $k$. Our results improve upon a result of Ryser for $k=o(n^{1/3})$. For fixed $k\ge 3$ it was an open question whether Hadamard's inequality could be exponentially improved. We answer this in the affirmative. Our results stem from studying matrices with row sums $k$ and bounding their Gram determinants. Our technique allows us to give upper bounds when these matrices are perturbed.

23 pages

Cited by in corpus (2)

• An Asymptotic Determinant Bound on 0-1 Matrices with Fixed Row Sums
• Maximum determinant and permanent of sparse 0-1 matrices