TY - JOUR

T1 - Probabilistic lower bounds on maximal determinants of binary matrices

AU - Brent, Richard P.

AU - Osborn, Judy Anne H.

AU - Smith, Warren D.

N1 - Publisher Copyright:
© 2016, University of Queensland. All rights reserved.

PY - 2016

Y1 - 2016

N2 - Let D(n) be the maximal determinant for n × n {±1}-matrices, and R(n) = D(n)/nn/2 be the ratio of D(n) to the Hadamard upper bound. Using the probabilistic method, we prove new lower bounds on D(n) and R(n) in terms of d = n − h, where h is the order of a Hadamard matrix and h is maximal subject to h ≤ n. For example, (Formula Presented) By a recent result of Livinskyi, d2/h1/2 → 0 as n → ∞, so the second bound is close to (πe/2)−d/2 for large n. Previous lower bounds tended to zero as n→∞with d fixed, except in the cases d ∈ {0, 1}. For d ≥ 2, our bounds are better for all sufficiently large n. If the Hadamard conjecture is true, then d ≤ 3, so the first bound above shows that R(n) is bounded below by a positive constant (πe/2)−3/2 > 0.1133.

AB - Let D(n) be the maximal determinant for n × n {±1}-matrices, and R(n) = D(n)/nn/2 be the ratio of D(n) to the Hadamard upper bound. Using the probabilistic method, we prove new lower bounds on D(n) and R(n) in terms of d = n − h, where h is the order of a Hadamard matrix and h is maximal subject to h ≤ n. For example, (Formula Presented) By a recent result of Livinskyi, d2/h1/2 → 0 as n → ∞, so the second bound is close to (πe/2)−d/2 for large n. Previous lower bounds tended to zero as n→∞with d fixed, except in the cases d ∈ {0, 1}. For d ≥ 2, our bounds are better for all sufficiently large n. If the Hadamard conjecture is true, then d ≤ 3, so the first bound above shows that R(n) is bounded below by a positive constant (πe/2)−3/2 > 0.1133.

UR - http://www.scopus.com/inward/record.url?scp=84994593550&partnerID=8YFLogxK

M3 - Article

SN - 1034-4942

VL - 66

SP - 350

EP - 364

JO - Australasian Journal of Combinatorics

JF - Australasian Journal of Combinatorics

IS - 3

ER -