Probabilistic lower bounds on maximal determinants of binary matrices

Title: Probabilistic lower bounds on maximal determinants of binary matrices
Creator: Brent, Richard P.; Osborn, Judy-Anne H.; Smith, Warren D.
Relation: ARC.DP140101417
Relation: Australasian Journal of Combinatorics Vol. 66, Issue 3, p. 350-364
Relation: https://ajc.maths.uq.edu.au/?page=get_volumes&volume=66
Publisher: Centre for Discrete Mathematics & Computing
Resource Type: journal article
Date: 2016
Description: Let D(n) be the maximal determinant for n × n {±1}-matrices, and R(n) = D(n)/n^n/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, [forumal cannot be replicated]. By a recent result of Livinskyi, d²/h^1/2 → 0 as n → 8, 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.
Subject: mathmatics; binary matrices; lower bounds
Identifier: http://hdl.handle.net/1959.13/1331882
Identifier: uon:26737
Identifier: ISSN:1034-4942
Language: eng
Full Text
Reviewed

		Thumbnail	File	Description	Size	Format
View Details Download			ATTACHMENT02	Publisher version (open access)	176 KB	Adobe Acrobat PDF	View Details Download