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<sup>nâÂÂ1</sup> 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 n<sup>n/2</sup>. Hadamard observed that a construction of Sylvester 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 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 X<sup>T</sup>X has maximal determinant. (The notation X<sup>T</sup> 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, R<sub>1</sub> and R<sub>2</sub>, are considered equivalent if R<sub>1</sub> can be converted to R<sub>2</sub> 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 2<sup>1âÂÂn</sup>. 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)<sup>âÂÂ3</sup>.
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<sup>nâÂÂ1</sup>.
Let R be an n by n {1, âÂÂ1} matrix. The Gram matrix of R is defined to be the matrix G = RR<sup>T</sup>. From this definition it follows that G
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<sup>T</sup>R. 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 can be derived by noting that |det R| = (det G)<sup>1/2</sup> ⤠(det nI)<sup>1/2</sup> = n<sup>n/2</sup>, 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<sup>nâÂÂ1</sup> can be used to provide another demonstration that Hadamard's bound is not always attainable. When n is odd, the bound n<sup>n/2</sup> 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<sup>k</sup> which is less than 2<sup>nâÂÂ1</sup> unless n = 2. Therefore, Hadamard's bound is unattainable unless n = 1, 2, or a multiple of 4.
When n is odd, property 1 for Gram matrices can be strengthened to
This allows a sharper upper bound to be derived: |det R| = (det G)<sup>1/2</sup> ⤠(det (nâÂÂ1)I+J)<sup>1/2</sup> = (2nâÂÂ1)<sup>1/2</sup>(nâÂÂ1)<sup>(nâÂÂ1)/2</sup>, 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).
When n is even, the set of rows of R can be partitioned into two subsets.
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,
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 and Wojtas 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)<sup>(nâÂÂ2)/2</sup>. Ehlich showed that if R attains the bound, and if the rows and columns of R are permuted so that both G = RR<sup>T</sup> and Gâ² = R<sup>T</sup>R have the standard form and are suitably normalized, then we may write
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<sup>2</sup>+x<sup>2</sup> = 2nâÂÂ2. Hence the EhlichâÂÂWojtas bound is not attainable unless 2nâÂÂ2 is expressible as the sum of two squares.
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
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 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 block-diagonal matrix 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
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
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 analyzed the bound and determined that, apart from n = 3, it is an integer only for n = 112t<sup>2</sup>ñ28t+7 for some positive integer t. Tamura 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.
The maximal determinants of {1, âÂÂ1} matrices up to size n = 22 are given in the following table. Size 23 is the smallest open case. In the table, D(n) represents the maximal determinant divided by 2<sup>nâÂÂ1</sup>. Equivalently, D(n) represents the maximal determinant of a {0, 1} matrix of size nâÂÂ1.
The maximal determinant problem has been extended to matrices with entries in the fourth roots of unity and more generally to roots of unity of a fixed order.
The maximal determinant problem over the third roots of unity , where , shares many similarities to the problem over . The Hadamard bound holds true for all , and for a matrix with entries in the third roots if and only if is a Butson-type Hadamard matrix . Therefore the Hadamard bound is sharp at order only if is a multiple 3. There is a generalization of the Barba bound for matrices with entries in of order stating:
.
Equality above is achieved if and only if can be transformed, via row/column permutations and multiplication of rows and columns by a third root, to a matrix satisfying , where is the conjugate-transpose of . The generalized Barba bound is sharp only if .
Size 14 is the smallest open case. In the table, D(n,3) represents the maximal absolute value squared of determinant divided by .