Hadamard's maximal determinant problem

Hadamard's maximal determinant problem, named after Jacques Hadamard, asks for the largest determinant of a matrix 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 n is 2ⁿ⁻¹ times the maximal determinant of a {0,1} matrix of size n−1. The problem was posed by Hadamard in the 1893 paper^[1] in which he presented his famous determinant bound and remains unsolved for matrices of general size. Hadamard's bound implies that {1, −1}-matrices of size n have determinant at most n^n/2. Hadamard observed that a construction of Sylvester^[2] produces examples of matrices that attain the bound when n 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 n 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

. They have received intensive study.

Matrix sizes n for which n ≡ 1, 2, or 3 (mod 4) have received less attention. The earliest results are due to Barba, who tightened Hadamard's bound for n odd, and Williamson, who found the largest determinants for n=3, 5, 6, and 7. Some important results include

• tighter bounds, due to Barba, Ehlich, and Wojtas, for n ≡ 1, 2, or 3 (mod 4), which, however, are known not to be always attainable,
• a few infinite sequences of matrices attaining the bounds for n ≡ 1 or 2 (mod 4),
• a number of matrices attaining the bounds for specific n ≡ 1 or 2 (mod 4),
• a number of matrices not attaining the bounds for specific n ≡ 1 or 3 (mod 4), but that have been proved by exhaustive computation to have maximal determinant.

The

, it is known as a saturated D-optimal design.

Hadamard matrices

Any two rows of an n×n Hadamard matrix are

odd number

. 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.

Equivalence and normalization of {1, −1} matrices

Any of the following operations, when performed on a {1, −1} matrix R, changes the determinant of R only by a minus sign:

• Negation of a row.
• Negation of a column.
• Interchange of two rows.
• Interchange of two columns.

Two {1,−1} matrices, R₁ and R₂, are considered equivalent if R₁ can be converted to R₂ 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.

Connection of the maximal determinant problems for {1, −1} and {0, 1} matrices

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 2¹⁻ⁿ. This map consists of the following steps.

1. Subtract row 1 of the {1, −1} matrix from rows 2 through n. (This does not change the determinant.)
2. 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
   cofactor expansion
   on column 1 of the matrix obtained in Step 1.)
3. Divide the submatrix by −2 to obtain a {0, 1} matrix. (This multiplies the determinant by (−2)¹⁻ⁿ.)

Example:

${\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)⁻³.

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 2ⁿ⁻¹.

Upper bounds on the maximal determinant

Gram matrix

Let R be an n by n {1, −1} matrix. The Gram matrix of R is defined to be the matrix G = RR^T. From this definition it follows that G

1. is an integer matrix,
2. is symmetric,
3. is
   positive-semidefinite
   ,
4. has constant diagonal whose value equals n.

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′=R^TR. The matrix G is the usual Gram matrix 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 normal matrix. Every known maximal-determinant matrix is equivalent to a normal matrix, but it is not known whether this is always the case.

Hadamard's bound (for all n)

Hadamard's bound can be derived by noting that |det R| = (det G)^1/2 ≤ (det nI)^1/2 = n^n/2, which is a consequence of the observation that nI, where I is the n by n identity matrix, is the unique matrix of maximal determinant among matrices satisfying properties 1–4. That det R must be an integer multiple of 2ⁿ⁻¹ can be used to provide another demonstration that Hadamard's bound is not always attainable. When n is odd, the bound n^n/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 2^k which is less than 2ⁿ⁻¹ unless n = 2. Therefore, Hadamard's bound is unattainable unless n = 1, 2, or a multiple of 4.

Barba's bound for n odd

When n is odd, property 1 for Gram matrices can be strengthened to

1. G is an odd-integer matrix.

This allows a sharper upper bound^[4] 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).

The Ehlich–Wojtas bound for n ≡ 2 (mod 4)

When n is even, the set of rows of R can be partitioned into two subsets.

• Rows of even type contain an even number of elements 1 and an even number of elements −1.
• Rows of odd type contain an odd number of elements 1 and an odd number of elements −1.

The dot product 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,

${\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^[5] and Wojtas^[6] 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 = RR^T and G′ = R^TR have the standard form and are suitably normalized, then we may write

${\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 w²+x² = 2n−2. Hence the Ehlich–Wojtas bound is not attainable unless 2n−2 is expressible as the sum of two squares.

Ehlich's bound for n ≡ 3 (mod 4)

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

1. G is a matrix with integer elements congruent to n (mod 4).

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

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 ${\displaystyle r=\lfloor n/s\rfloor .}$

n	s
3	3
7	5
11	5 or 6
15 − 59	6
≥ 63	7

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

${\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^[8] analyzed the bound and determined that, apart from n = 3, it is an integer only for n = 112t²±28t+7 for some positive integer t. Tamura^[9] derived additional restrictions on the attainability of the bound using the Hasse–Minkowski theorem on the rational equivalence of quadratic forms, and showed that the smallest n > 3 for which Ehlich's bound is conceivably attainable is 511.

Maximal determinants up to size 21

The maximal determinants of {1, −1} matrices up to size n = 21 are given in the following table.^[10] Size 22 is the smallest open case. In the table, D(n) represents the maximal determinant divided by 2ⁿ⁻¹. Equivalently, D(n) represents the maximal determinant of a {0, 1} matrix of size n−1.

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

References