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 2n−1 times the maximal determinant of a {0,1} matrix of size n−1. The problem was posed by Hadamard in the 1893 paper 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 nn/2. Hadamard observed that a construction of Sylvesterproduces 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 Hadamard matrices. They have received intensive study. 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 2n−1 times the maximal determinant of a {0,1} matrix of size n−1. The problem was posed by Hadamard in the 1893 paper 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 nn/2. Hadamard observed that a construction of Sylvesterproduces 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 Hadamard matrices. 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 The design of experiments in statistics makes use of {1, −1} matrices X (not necessarily square) for which the information matrix XTX has maximal determinant. (The notation XT 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. Any two rows of an n×n Hadamard matrix are orthogonal. For a {1, −1} matrix, it means any two rows differ in exactly half of the entries, which is impossible 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 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. Any of the following operations, when performed on a {1, −1} matrix R, changes the determinant of R only by a minus sign: 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. 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. Example: In this example, the original matrix has determinant −16 and its image has determinant 2 = −16·(−2)−3.