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

MaRDI QIDQ6237141zbMATH OpenFDO

Authors Richard P. Brent, Judy-Anne H. Osborn, Warren D. Smith

Publication date 14 November 2012

Mathematics Subject Classification ID

Combinatorial aspects of matrices (incidence, Hadamard, etc.) (05B20) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40) Boolean and Hadamard matrices (15B34)

Abstract: We show that the maximal determinant D(n) for $nimesn$ $pm1$-matrices satisfies $R(n):=D(n)/n^{n/2}gekapp{a}_d>0$. Here $n^{n/2}$ is the Hadamard upper bound, and $kapp{a}_d$ depends only on $d:=n-h$, where $h$ is the maximal order of a Hadamard matrix with $hlen$. 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)ge0.07(0.352{)}^d>3^{-(d+3)}$. For any fixed $dge0$ we have $R(n)ge(2/(pie){)}^{d/2}$ for all sufficiently large $n$ (and conjecturally for all positive $n$). If the Hadamard conjecture is true, then $dle3$ and $kapp{a}_{d}ge(2/(pie){)}^{d/2}>1/9$.

This page was built for publication: Lower bounds on maximal determinants of +-1 matrices via the probabilistic method

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6237141)