Hadamard's maximal determinant problem

Hadamard's maximal determinant problem, named after Jacques Hadamard, asks for the largest possible determinant of a matrix with elements restricted to the set {1,−1}. The question for matrices with elements restricted to the set {0,1} is equivalent: 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 first posed by Jacques Hadamard in the 1893 paper in which he presented his famous determinant bound, but the problem 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. Matrices whose determinants attain the bound are now known as Hadamard matrices, although examples had earlier been found by Sylvester. Any two rows of an n×n Hadamard matrix are orthogonal, which is impossible for a {1, −1} matrix when n is an 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 a Hadamard matrix of size 4k exists for every k ≥ 1. The smallest n for which an n×n Hadamard matrix is not known to exist is 668.

Matrix sizes n for which n ≡ 1, 2, or 3 (mod 4) have received less attention. Nevertheless, some results are known, including:

• tighter bounds for n ≡ 1, 2, or 3 (mod 4) (These bounds, due to Barba, Ehlich, and Wojtas, 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 maximal determinant is known up to n = 18. In the following table, D(n) represents the maximal determinant divided by 2ⁿ⁻¹.

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

The design of experiments in statistics makes use of {1, −1} matrices X (not necessarily square) for which the information matrix X^TX has maximal determinant. (The notation X^T denotes the transpose of X.) Such matrices are known as D-optimal designs. If X is a square matrix, it is known as a saturated D-optimal design.