Maximal determinants of sparse zero-one matrices

2019/02/25 by Scheinerman, Daniel
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1902.09644

Abstract

We give upper bounds for the determinant of an n× 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≥ 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.

Related

• A Survey of the Hadamard Maximal Determinant Problem
• Lower bounds on maximal determinants of +-1 matrices via the probabilistic method
• New lower bounds for the maximal determinant problem
• Maximum determinant and permanent of sparse 0-1 matrices
• An Asymptotic Determinant Bound on 0-1 Matrices with Fixed Row Sums