Hadamard's maximal determinant problem

<h2 id="hadamard-matrices">Hadamard matrices</h2>
Any two rows of an n×n Hadamard matrix are <a href="/facts/Orthogonal/JVIjYPog">orthogonal</a>. For a {1, −1} matrix, it means any two rows differ in exactly half of the entries, which is impossible when n is an <a href="/facts/Odd_number/7zq2UM4V">odd number</a>. When n ≡ 2 (mod 4), two rows that are both orthogonal to a third row cannot be orthogonal to each other. Together, these statements imply that an n×n Hadamard matrix can exist only if n = 1, 2, or a multiple of 4. Hadamard matrices have been well studied, but it is not known whether an n×n Hadamard matrix exists for every n that is a positive multiple of 4. The smallest n for which an n×n Hadamard matrix is not known to exist is 668.

<h2 id="equivalence-and-normalization-of-11-matrices">Equivalence and normalization of {1, −1} matrices</h2>
Any of the following operations, when performed on a {1, −1} matrix R, changes the determinant of R only by a minus sign: 

<ul><li>Negation of a row.</li>
<li>Negation of a column.</li>
<li>Interchange of two rows.</li>
<li>Interchange of two columns.</li></ul>
Two {1,−1} matrices, R1 and R2, are considered equivalent if R1 can be converted to R2 by some sequence of the above operations. The determinants of equivalent matrices are equal, except possibly for a sign change, and it is often convenient to standardize R by means of negations and permutations of rows and columns. A {1, −1} matrix is normalized if all elements in its first row and column equal 1. When the size of a matrix is odd, it is sometimes useful to use a different normalization in which every row and column contains an even number of elements 1 and an odd number of elements −1. Either of these normalizations can be accomplished using the first two operations.

<h2 id="connection-of-the-maximal-determinant-problems-for-11-and-01-matrices">Connection of the maximal determinant problems for {1, −1} and {0, 1} matrices</h2>
There is a one-to-one map from the set of normalized n×n {1, −1} matrices to the set of (n−1)×(n-1) {0, 1} matrices under which the magnitude of the determinant is reduced by a factor of 21−n. This map consists of the following steps.

<ol><li>Subtract row 1 of the {1, −1} matrix from rows 2 through n. (This does not change the determinant.)</li>
<li>Extract the (n−1)×(n−1) submatrix consisting of rows 2 through n and columns 2 through n. This matrix has elements 0 and −2. (The determinant of this submatrix is the same as that of the original matrix, as can be seen by performing a <a href="/facts/Cofactor_expansion/B4EIjlsp">cofactor expansion</a> on column 1 of the matrix obtained in Step 1.)</li>
<li>Divide the submatrix by −2 to obtain a {0, 1} matrix. (This multiplies the determinant by (−2)1−n.)</li></ol>
Example:

[
            
              
                
                  1
                
                
                  1
                
                
                  1
                
                
                  1
                
              
              
                
                  1
                
                
                  −
                  1
                
                
                  −
                  1
                
                
                  1
                
              
              
                
                  1
                
                
                  1
                
                
                  −
                  1
                
                
                  −
                  1
                
              
              
                
                  1
                
                
                  −
                  1
                
                
                  1
                
                
                  −
                  1
                
              
            
            ]
          
        
        →
        
          [
          
            
              
                
                  1
                
                
                  1
                
                
                  1
                
                
                  1
                
              
              
                
                  0
                
                
                  −
                  2
                
                
                  −
                  2
                
                
                  0
                
              
              
                
                  0
                
                
                  0
                
                
                  −
                  2
                
                
                  −
                  2
                
              
              
                
                  0
                
                
                  −
                  2
                
                
                  0
                
                
                  −
                  2
                
              
            
          
          ]
        
        →
        
          
            [
            
              
                
                  −
                  2
                
                
                  −
                  2
                
                
                  0
                
              
              
                
                  0
                
                
                  −
                  2
                
                
                  −
                  2
                
              
              
                
                  −
                  2
                
                
                  0
                
                
                  −
                  2
                
              
            
            ]
          
        
        →
        
          
            [
            
              
                
                  1
                
                
                  1
                
                
                  0
                
              
              
                
                  0
                
                
                  1
                
                
                  1
                
              
              
                
                  1
                
                
                  0
                
                
                  1
                
              
            
            ]
          
        
      
    
    {\displaystyle {\begin{bmatrix}1&1&1&1\\1&-1&-1&1\\1&1&-1&-1\\1&-1&1&-1\end{bmatrix}}\rightarrow \left[{\begin{array}{c|ccc}1&1&1&1\\\hline 0&-2&-2&0\\0&0&-2&-2\\0&-2&0&-2\end{array}}\right]\rightarrow {\begin{bmatrix}-2&-2&0\\0&-2&-2\\-2&0&-2\end{bmatrix}}\rightarrow {\begin{bmatrix}1&1&0\\0&1&1\\1&0&1\end{bmatrix}}}

In this example, the original matrix has determinant −16 and its image has determinant 2 = −16·(−2)−3.
Since the determinant of a {0, 1} matrix is an integer, the determinant of an n×n {1, −1} matrix is an integer multiple of 2n−1.

<h2 id="upper-bounds-on-the-maximal-determinant">Upper bounds on the maximal determinant</h2>
<h3>Gram matrix</h3>
Let R be an n by n {1, −1} matrix. The Gram matrix of R is defined to be the matrix G = RRT. From this definition it follows that G

<ol><li>is an integer matrix,</li>
<li>is <a href="/facts/Symmetric_matrix/08CGwjNl">symmetric</a>,</li>
<li>is <a href="/facts/Positive-definite_matrix/Hbr6AuPS">positive-semidefinite</a>,</li>
<li>has constant diagonal whose value equals n.</li></ol>
Negating rows of R or applying a permutation to them results in the same negations and permutation being applied both to the rows, and to the corresponding columns, of G. We may also define the matrix G′=RTR. The matrix G is the usual <a href="/facts/Gram_matrix/SGb2VGTU">Gram matrix</a> of a set of vectors, derived from the set of rows of R, while G′ is the Gram matrix derived from the set of columns of R. A matrix R for which G = G′ is a <a href="/facts/Normal_matrix/WVKxrEK9">normal matrix</a>. Every known maximal-determinant matrix is equivalent to a normal matrix, but it is not known whether this is always the case.

<h3>Hadamard's bound (for all n)</h3>
Hadamard's bound can be derived by noting that |det R| = (det G)1/2 ≤ (det nI)1/2 = nn/2, which is a consequence of the observation that nI, where I is the n by n <a href="/facts/Identity_matrix/Glbcf6ol">identity matrix</a>, is the unique matrix of maximal determinant among matrices satisfying properties 1–4. That det R must be an integer multiple of 2n−1 can be used to provide another demonstration that Hadamard's bound is not always attainable. When n is odd, the bound nn/2 is either non-integer or odd, and is therefore unattainable except when n = 1. When n = 2k with k odd, the highest power of 2 dividing Hadamard's bound is 2k which is less than 2n−1 unless n = 2. Therefore, Hadamard's bound is unattainable unless n = 1, 2, or a multiple of 4.

<h3>Barba's bound for n odd</h3>
When n is odd, property 1 for Gram matrices can be strengthened to

<ol><li>G is an odd-integer matrix.</li></ol>
This allows a sharper upper bound<a class="footnote-ref" id="fnref:4" href="#fn:4">4</a> to be derived: |det R| = (det G)1/2 ≤ (det (n-1)I+J)1/2 = (2n−1)1/2(n−1)(n−1)/2, where J is the all-one matrix. Here (n-1)I+J is the maximal-determinant matrix satisfying the modified property 1 and properties 2–4. It is unique up to multiplication of any set of rows and the corresponding set of columns by −1. The bound is not attainable unless 2n−1 is a perfect square, and is therefore never attainable when n ≡ 3 (mod 4).

<h3>The Ehlich–Wojtas bound for n ≡ 2 (mod 4)</h3>
When n is even, the set of rows of R can be partitioned into two subsets.

<ul><li>Rows of even type contain an even number of elements 1 and an even number of elements −1.</li>
<li>Rows of odd type contain an odd number of elements 1 and an odd number of elements −1.</li></ul>
The <a href="/facts/Dot_product/tNz8MLjT">dot product</a> of two rows of the same type is congruent to n (mod 4); the dot product of two rows of opposite type is congruent to n+2 (mod 4). When n ≡ 2 (mod 4), this implies that, by permuting rows of R, we may assume the standard form,

G
        =
        
          
            [
            
              
                
                  A
                
                
                  B
                
              
              
                
                  
                    B
                    
                      
                        T
                      
                    
                  
                
                
                  D
                
              
            
            ]
          
        
        ,
      
    
    {\displaystyle G={\begin{bmatrix}A&B\\B^{\mathrm {T} }&D\end{bmatrix}},}

where A and D are symmetric integer matrices whose elements are congruent to 2 (mod 4) and B is a matrix whose elements are congruent to 0 (mod 4). In 1964, Ehlich<a class="footnote-ref" id="fnref:5" href="#fn:5">5</a> and Wojtas<a class="footnote-ref" id="fnref:6" href="#fn:6">6</a> independently showed that in the maximal determinant matrix of this form, A and D are both of size n/2 and equal to (n−2)I+2J while B is the zero matrix. This optimal form is unique up to multiplication of any set of rows and the corresponding set of columns by −1 and to simultaneous application of a permutation to rows and columns. This implies the bound det R ≤ (2n−2)(n−2)(n−2)/2. Ehlich showed that if R attains the bound, and if the rows and columns of R are permuted so that both G = RRT and G′ = RTR have the standard form and are suitably normalized, then we may write

R
        =
        
          
            [
            
              
                
                  W
                
                
                  X
                
              
              
                
                  Y
                
                
                  Z
                
              
            
            ]
          
        
      
    
    {\displaystyle R={\begin{bmatrix}W&X\\Y&Z\end{bmatrix}}}

where W, X, Y, and Z are (n/2)×(n/2) matrices with constant row and column sums w, x, y, and z that satisfy z = −w, y = x, and w2+x2 = 2n−2. Hence the Ehlich–Wojtas bound is not attainable unless 2n−2 is expressible as the sum of two squares.

<h3>Ehlich's bound for n ≡ 3 (mod 4)</h3>
When n is odd, then by using the freedom to multiply rows by −1, one may impose the condition that each row of R contain an even number of elements 1 and an odd number of elements −1. It can be shown that, if this normalization is assumed, then property 1 of G may be strengthened to

<ol><li>G is a matrix with integer elements congruent to n (mod 4).</li></ol>
When n ≡ 1 (mod 4), the optimal form of Barba satisfies this stronger property, but when n ≡ 3 (mod 4), it does not. This means that the bound can be sharpened in the latter case. Ehlich<a class="footnote-ref" id="fnref:7" href="#fn:7">7</a> showed that when n ≡ 3 (mod 4), the strengthened property 1 implies that the maximal-determinant form of G can be written as B−J where J is the all-one matrix and B is a <a href="/facts/Block-diagonal_matrix/fPI8HX9f">block-diagonal matrix</a> whose diagonal blocks are of the form (n-3)I+4J. Moreover, he showed that in the optimal form, the number of blocks, s, depends on n as shown in the table below, and that each block either has size r or size r+1 where 
 
 
 
 r
 =
 ⌊
 n
 
 /
 
 s
 ⌋
 .
 
 
 {\displaystyle r=\lfloor n/s\rfloor .}

<table><tbody><tr><th>n</th><th>s</th></tr><tr><td>3</td><td>3</td></tr><tr><td>7</td><td>5</td></tr><tr><td>11</td><td>5 or 6</td></tr><tr><td>15 − 59</td><td>6</td></tr><tr><td>≥ 63</td><td>7</td></tr></tbody></table>
Except for n=11 where there are two possibilities, the optimal form is unique up to multiplication of any set of rows and the corresponding set of columns by −1 and to simultaneous application of a permutation to rows and columns. This optimal form leads to the bound

det
        R
        ≤
        (
        n
        −
        3
        
          )
          
            (
            n
            −
            s
            )
            
              /
            
            2
          
        
        (
        n
        −
        3
        +
        4
        r
        
          )
          
            u
            
              /
            
            2
          
        
        (
        n
        +
        1
        +
        4
        r
        
          )
          
            v
            
              /
            
            2
          
        
        
          
            [
            
              1
              −
              
                
                  
                    u
                    r
                  
                  
                    n
                    −
                    3
                    +
                    4
                    r
                  
                
              
              −
              
                
                  
                    v
                    (
                    r
                    +
                    1
                    )
                  
                  
                    n
                    +
                    1
                    +
                    4
                    r
                  
                
              
            
            ]
          
          
            1
            
              /
            
            2
          
        
        ,
      
    
    {\displaystyle \det R\leq (n-3)^{(n-s)/2}(n-3+4r)^{u/2}(n+1+4r)^{v/2}\left[1-{\frac {ur}{n-3+4r}}-{\frac {v(r+1)}{n+1+4r}}\right]^{1/2},}

where v = n−rs is the number of blocks of size r+1 and u =s−v is the number of blocks of size r. 
Cohn<a class="footnote-ref" id="fnref:8" href="#fn:8">8</a> analyzed the bound and determined that, apart from n = 3, it is an integer only for n = 112t2±28t+7 for some positive integer t. Tamura<a class="footnote-ref" id="fnref:9" href="#fn:9">9</a> derived additional restrictions on the attainability of the bound using the <a href="/facts/Hasse%E2%80%93Minkowski_theorem/5gL6dEWo">Hasse–Minkowski theorem</a> on the rational equivalence of quadratic forms, and showed that the smallest n > 3 for which Ehlich's bound is conceivably attainable is 511.

<h2 id="maximal-determinants-up-to-size-21">Maximal determinants up to size 21</h2>
The maximal determinants of {1, −1} matrices up to size n = 21 are given in the following table.<a class="footnote-ref" id="fnref:10" href="#fn:10">10</a> Size 22 is the smallest open case. In the table, D(n) represents the maximal determinant divided by 2n−1. Equivalently, D(n) represents the maximal determinant of a {0, 1} matrix of size n−1.

<table><tbody><tr><th>n</th><th>D(n)</th><th>Notes</th></tr><tr><td>1</td><td>1</td><td>Hadamard matrix</td></tr><tr><td>2</td><td>1</td><td>Hadamard matrix</td></tr><tr><td>3</td><td>1</td><td>Attains Ehlich bound</td></tr><tr><td>4</td><td>2</td><td>Hadamard matrix</td></tr><tr><td>5</td><td>3</td><td>Attains Barba bound; circulant matrix</td></tr><tr><td>6</td><td>5</td><td>Attains Ehlich–Wojtas bound</td></tr><tr><td>7</td><td>9</td><td>98.20% of Ehlich bound</td></tr><tr><td>8</td><td>32</td><td>Hadamard matrix</td></tr><tr><td>9</td><td>56</td><td>84.89% of Barba bound</td></tr><tr><td>10</td><td>144</td><td>Attains Ehlich–Wojtas bound</td></tr><tr><td>11</td><td>320</td><td>94.49% of Ehlich bound; three non-equivalent matrices</td></tr><tr><td>12</td><td>1458</td><td>Hadamard matrix</td></tr><tr><td>13</td><td>3645</td><td>Attains Barba bound; maximal-determinant matrix is {1,−1} incidence matrix of <a href="/facts/Projective_plane/p6ot8oNv">projective plane</a> of order 3</td></tr><tr><td>14</td><td>9477</td><td>Attains Ehlich–Wojtas bound</td></tr><tr><td>15</td><td>25515</td><td>97.07% of Ehlich bound</td></tr><tr><td>16</td><td>131072</td><td>Hadamard matrix; five non-equivalent matrices</td></tr><tr><td>17</td><td>327680</td><td>87.04% of Barba bound; three non-equivalent matrices</td></tr><tr><td>18</td><td>1114112</td><td>Attains Ehlich–Wojtas bound; three non-equivalent matrices</td></tr><tr><td>19</td><td>3411968</td><td>Attains 97.50% of Ehlich bound; three non-equivalent matrices</td></tr><tr><td>20</td><td>19531250</td><td>Hadamard matrix; three non-equivalent matrices</td></tr><tr><td>21</td><td>56640625</td><td>90.58% of Barba bound; seven non-equivalent matrices</td></tr></tbody></table>

<h2 id="references">References</h2>

<ol>
<li id="fn:1">Hadamard, J. (1893), "Résolution d'une question relative aux déterminants", Bulletin des Sciences Mathématiques, 17: 240–246 <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn:2">Sylvester, J. J. (1867), "Thoughts on inverse orthogonal matrices, simultaneous sign successions, and tessellated pavements in two or more colours, with applications to Newton's rule, ornamental tile-work, and the theory of numbers", London Edinburgh Dublin Phil. Mag. J. Sci., 34 (232): 461–475, doi:10.1080/14786446708639914 <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
<li id="fn:3">Galil, Z.; Kiefer, J. (1980), "D-optimum weighing designs", Ann. Stat., 8 (6): 1293–1306, doi:10.1214/aos/1176345202 <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></li>
<li id="fn:4">Barba, Guido (1933), "Intorno al teorema di Hadamard sui determinanti a valore massimo", Giorn. Mat. Battaglini, 71: 70–86. <a href="#fnref:4" class="footnote-back-ref">↩</a></li>
<li id="fn:5">Ehlich, Hartmut (1964), "Determinantenabschätzungen für binäre Matrizen", Math. Z., 83 (2): 123–132, doi:10.1007/BF01111249, S2CID 120916607. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></li>
<li id="fn:6">Wojtas, M. (1964), "On Hadamard's inequality for the determinants of order non-divisible by 4", Colloq. Math., 12: 73–83, doi:10.4064/cm-12-1-73-83. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></li>
<li id="fn:7">Ehlich, Hartmut (1964), "Determinantenabschätzungen für binäre Matrizen mit n ≡ 3 mod 4", Math. Z., 84: 438–447, doi:10.1007/BF01109911, S2CID 116683967. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></li>
<li id="fn:8">Cohn, J. H. E. (2000), "Almost D-optimal designs", Utilitas Math., 57: 121–128. <a href="#fnref:8" class="footnote-back-ref">↩</a></li>
<li id="fn:9">Tamura, Hiroki (2006), "D-optimal designs and group divisible designs", Journal of Combinatorial Designs, 14 (6): 451–462, doi:10.1002/jcd.20103. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:9" class="footnote-back-ref">↩</a></li>
<li id="fn:10">Sloane, N. J. A. (ed.). "Sequence A003432 (Hadamard maximal determinant problem: largest determinant of a (real) {0,1}-matrix of order n.)". The On-Line Encyclopedia of Integer Sequences. OEIS Foundation. <a href="/wiki/Neil_Sloane" target="_blank">/wiki/Neil_Sloane</a> <a href="#fnref:10" class="footnote-back-ref">↩</a></li>
</ol>

Hadamard's maximal determinant problem open-in-new

Hadamard's maximal determinant problem