Lower bounds on maximal determinants of +-1 matrices via the probabilistic method

Abstract

We show that the maximal determinant D(n) for $n\times n$ $\pm 1$-matrices satisfies $R(n):=D(n)/n^{n/2}\ge {\kappa }_d>0$. Here $n^{n/2}$ is the Hadamard upper bound, and ${\kappa }_d$ depends only on $d:=n-h$, where $h$ is the maximal order of a Hadamard matrix with $h\le n$. Previous lower bounds on R(n) depend on both $d$ and $n$. Our bounds are improvements, for all sufficiently large $n$, if $d>1$. We give various lower bounds on R(n) that depend only on $d$. For example, $R(n)\ge 0.07(0.352{)}^d>3^{-(d+3)}$. For any fixed $d\ge 0$ we have $R(n)\ge (2/(\pi e){)}^{d/2}$ for all sufficiently large $n$ (and conjecturally for all positive $n$). If the Hadamard conjecture is true, then $d\le 3$ and ${\kappa }_d\ge (2/(\pi e){)}^{d/2}>1/9$.

32 pages, 64 references, 1 table. Theorem 4 added in v2. Minor improvements/corrections in v3

References in corpus (2)

• Note on a double binomial sum relevant to the Hadamard maximal determinant problem
• Small orders of Hadamard matrices and base sequences

Cited by in corpus (6)

• Bounds on determinants of perturbed diagonal matrices
• Discrete analogues of Macdonald-Mehta integrals
• Note on a double binomial sum relevant to the Hadamard maximal determinant problem
• On minors of maximal determinant matrices
• Probabilistic lower bounds on maximal determinants of binary matrices
• Some binomial sums involving absolute values