Hadamard determinant problem

Hadamard determinant problem
Name	Hadamard determinant problem
Field	Mathematics
Subfield	Combinatorics; Linear algebra; Matrix theory
Introduced by	Jacques Hadamard
Year	1893
Importance	Extremal problem in determinant bounds for ±1 matrixs

Hadamard determinant problem

Introduction

The Hadamard determinant problem is a classical extremal question in Jacques Hadamard's work connecting determinant inequalities, orthogonal matrices, combinatorics and number theory; it asks for the maximal determinant of an n×n matrix with entries constrained to ±1, linking to results in Hadamard matrix, Sylvester matrix, Williamson construction, Paley construction and investigations by Ryser, Ehlich, Wojtas and Barba. This problem intersects research by scholars affiliated with institutions such as École Normale Supérieure, Cambridge University, Princeton University, University of Göttingen and has influenced work in error-correcting codes, signal processing, design theory and statistics.

Statement of the problem

The statement asks: for a given positive integer n, what is the maximum possible value of the absolute value of the determinant of an n×n matrix whose entries are all either +1 or −1? The question is historically tied to Hadamard’s inequality proven by Jacques Hadamard and to constructions by James Joseph Sylvester and later explicit matrices produced via the Paley construction from quadratic residues over finite fields studied by John Paley and methods by Williamson for use in Hadamard matrix generation. Equivalent formulations relate to maximizing volume of a parallelotope defined by ±1 row vectors, and thus connect to extremal problems considered by Bollobás, Erdős, Turán and Sárközy.

Known results and bounds

The classical upper bound, often called the Hadamard bound, states that for an n×n {±1}-matrix the determinant D satisfies |D| ≤ n^{n/2}; equality can occur only when n = 1 or n is divisible by 4, linking to existence questions for Hadamard matrixs studied in the Hadamard conjecture. Exact maximal values are known for small orders through exhaustive search by researchers at Brown University, MIT, University of Waterloo and computational projects by OEIS contributors; asymptotic results and improvements on constant factors were obtained by Komlós, Gluskin, Tikhomirov and Nguyen. Lower bounds arise from probabilistic methods developed by Erdős, Rényi and later refinements by Sárközy, while deterministic constructions producing large determinants employ results by Paley, Williamson, Conference matrices theory and work by Seberry. For orders not divisible by 4, sharp multiplicative adjustments were provided by Ehlich and Wojtas, yielding tighter upper bounds for n ≡ 1,2,3 (mod 4) and engaging techniques from Hadamard matrices theory, conference matrices, and combinatorial design theory by Bose and Fisher.

Constructions achieving equality

Equality in Hadamard’s bound is achieved exactly when an n×n {±1}-matrix is a Hadamard matrix; classical families include Sylvester’s recursive constructions via tensor products attributed to Sylvester and Paley matrices built using quadratic residues in finite fields following Paley. Williamson arrays produce further infinite families linked to work by Williamson and have been used in constructions catalogued at research centers including Ohio State University and NIST archives. Other notable constructions derive from conference matrices studied by J. H. van Lint and Wilson, and from combinatorial block designs by Bose and Kirkman; computational searches by groups at University of Manitoba and University of Waterloo have filled specific orders and produced counterexamples or confirmations for constructions proposed by Seberry and McKay.

Connections and applications

The problem connects to diverse topics: coding theorists like Claude Shannon and Richard Hamming exploit maximal-determinant matrices in error-correcting codes and communication theory; statisticians such as Ronald Fisher use orthogonal arrays related to Hadamard matrices in experimental design; signal processing practitioners trace links to Fourier transform implementations and Walsh functions studied by Joseph Walsh; cryptographers reference combinatorial constructions from Paley and Williamson in pseudorandom design; and theoretical computer scientists including Jeff Kahn and Noga Alon apply probabilistic and combinatorial bounds to randomized algorithms and derandomization. Connections also appear in sphere packing problems investigated by John Conway and Neil Sloane, and in operator theory where links to determinantal point processes and matrix concentration inequalities involve contributions by Joel Tropp and Roman Vershynin.

Open problems and conjectures

The central open conjecture is the Hadamard conjecture asserting that a Hadamard matrix exists for every order n divisible by 4; this conjecture has resisted proof despite partial progress by Paley, Scarpis, Kharaghani and computational confirmations up to large orders by collaborative projects at University of Cambridge and University of Waterloo. Related open problems include determining maximal determinants for orders not divisible by 4, improving asymptotic lower bounds on maximal determinants advanced by Komlós and Tikhomirov, and classifying equivalence classes of maximal-determinant matrices studied by Cohn and Seberry. Advances likely require techniques from finite field theory, algebraic geometry as used in Weil-type estimates, probabilistic combinatorics from Erdős-style methods, and computational algebra contributed by groups at Mathematics Research Institute of Oberwolfach and DIMACS.

Category:Matrix theory