Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Hadamard's maximal determinant problem
open-in-new
<p>Hadamard's maximal determinant problem, named after <a href="/facts/Jacques_Hadamard/TgCkP3AE">Jacques Hadamard</a>, asks for the largest <a href="/facts/Determinant/eGYqJ2TF">determinant</a> of a <a href="/facts/Matrix_(mathematics)/qa8FI4ko">matrix</a> with elements equal to 1 or −1. The analogous question for matrices with elements equal to 0 or 1 is equivalent since, as will be shown below, the maximal determinant of a {1,−1} matrix of size <i>n</i> is 2<i>n</i>−1 times the maximal determinant of a {0,1} matrix of size <i>n</i>−1. The problem was posed by Hadamard in the 1893 paper in which he presented his famous <a href="/facts/Hadamard%27s_inequality/TaW6IePT">determinant bound</a> and remains unsolved for matrices of general size. Hadamard's bound implies that {1, −1}-matrices of size <i>n</i> have determinant at most <i>n</i><i>n</i>/2. Hadamard observed that a construction of <a href="/facts/James_Joseph_Sylvester/6NNurKJH">Sylvester</a> produces examples of matrices that attain the bound when <i>n</i> is a power of 2, and produced examples of his own of sizes 12 and 20. He also showed that the bound is only attainable when <i>n</i> is equal to 1, 2, or a multiple of 4. Additional examples were later constructed by Scarpis and Paley and subsequently by many other authors. Such matrices are now known as <a href="/facts/Hadamard_matrices/q56o9lgM">Hadamard matrices</a>. They have received intensive study. </p><p>Matrix sizes <i>n</i> for which <i>n</i> ≡ 1, 2, or 3 (mod 4) have received less attention. The earliest results are due to Barba, who tightened Hadamard's bound for <i>n</i> odd, and Williamson, who found the largest determinants for <i>n</i>=3, 5, 6, and 7. Some important results include </p> <ul><li>tighter bounds, due to Barba, Ehlich, and Wojtas, for <i>n</i> ≡ 1, 2, or 3 (mod 4), which, however, are known not to be always attainable,</li> <li>a few infinite sequences of matrices attaining the bounds for <i>n</i> ≡ 1 or 2 (mod 4),</li> <li>a number of matrices attaining the bounds for specific <i>n</i> ≡ 1 or 2 (mod 4),</li> <li>a number of matrices not attaining the bounds for specific <i>n</i> ≡ 1 or 3 (mod 4), but that have been proved by exhaustive computation to have maximal determinant.</li></ul> <p>The <a href="/facts/Design_of_experiments/VMrNftbr">design of experiments</a> in <a href="/facts/Statistics/DNPsKGYU">statistics</a> makes use of {1, −1} matrices <i>X</i> (not necessarily square) for which the <a href="/facts/Information_matrix/Q2JLexN9">information matrix</a> <i>X</i>T<i>X</i> has maximal determinant. (The notation <i>X</i>T denotes the <a href="/facts/Transpose/8wmsagGS">transpose</a> of <i>X</i>.) Such matrices are known as <a href="/facts/Optimal_design/qCH9pPt5">D-optimal designs</a>. If <i>X</i> is a <a href="/facts/Square_matrix/5TP9mNNn">square matrix</a>, it is known as a saturated D-optimal design. </p>