Hadamard's maximal determinant problem
Encyclopedia
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 2n−1 times the maximal determinant of a {0,1} matrix of size n−1. The problem was first posed by 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 nn/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 greater than 1. 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:
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.
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.
Example:
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.
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 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.
, 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.
This allows a sharper upper bound 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 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)(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
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.
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 = 112t2±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.
Jacques Hadamard
Jacques Salomon Hadamard FRS was a French mathematician who made major contributions in number theory, complex function theory, differential geometry and partial differential equations.-Biography:...
, asks for the largest possible determinant
Determinant
In linear algebra, the determinant is a value associated with a square matrix. It can be computed from the entries of the matrix by a specific arithmetic expression, while other ways to determine its value exist as well...
of a matrix
Matrix (mathematics)
In mathematics, a matrix is a rectangular array of numbers, symbols, or expressions. The individual items in a matrix are called its elements or entries. An example of a matrix with six elements isMatrices of the same size can be added or subtracted element by element...
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 2n−1 times the maximal determinant of a {0,1} matrix of size n−1. The problem was first posed by Hadamard in the 1893 paper in which he presented his famous determinant bound
Hadamard's inequality
In mathematics, Hadamard's inequality, first published by Jacques Hadamard in 1893, is a bound on the determinant of a matrix whose entries are complex numbers in terms of the lengths of its column vectors...
, 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 nn/2. Matrices whose determinants attain the bound are now known as Hadamard matrices, although examples had earlier been found by Sylvester
James Joseph Sylvester
James Joseph Sylvester was an English mathematician. He made fundamental contributions to matrix theory, invariant theory, number theory, partition theory and combinatorics...
. 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 greater than 1. 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 design of experiments
Design of experiments
In general usage, design of experiments or experimental design is the design of any information-gathering exercises where variation is present, whether under the full control of the experimenter or not. However, in statistics, these terms are usually used for controlled experiments...
in statistics
Statistics
Statistics is the study of the collection, organization, analysis, and interpretation of data. It deals with all aspects of this, including the planning of data collection in terms of the design of surveys and experiments....
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
Transpose
In linear algebra, the transpose of a matrix A is another matrix AT created by any one of the following equivalent actions:...
of X.) Such matrices are known as D-optimal designs
Optimal design
Optimal designs are a class of experimental designs that are optimal with respect to some statistical criterion.In the design of experiments for estimating statistical models, optimal designs allow parameters to be estimated without bias and with minimum-variance...
. If X is a square matrix, it is known as a saturated D-optimal design.
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, 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.
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 21−n. This map consists of the following steps.- Subtract row 1 of the {1, −1} matrix from rows 2 through n. (This does not change the determinant.)
- 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.)
- Divide the submatrix by −2 to obtain a {0, 1} matrix. (This multiplies the determinant by (−2)1-n.)
Example:
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.
Gram matrix
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- is an integer matrix,
- is symmetric,
- is positive-semidefinitePositive-definite matrixIn linear algebra, a positive-definite matrix is a matrix that in many ways is analogous to a positive real number. The notion is closely related to a positive-definite symmetric bilinear form ....
, - 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′=RTR. 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
Normal matrix
A complex square matrix A is a normal matrix ifA^*A=AA^* \ where A* is the conjugate transpose of A. That is, a matrix is normal if it commutes with its conjugate transpose.If A is a real matrix, then A*=AT...
. 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 = nn/2, which is a consequence of the observation that nI, where I is the n by n identity matrixIdentity matrix
In linear algebra, the identity matrix or unit matrix of size n is the n×n square matrix with ones on the main diagonal and zeros elsewhere. It is denoted by In, or simply by I if the size is immaterial or can be trivially determined by the context...
, 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.
Barba's bound for n odd
When n is odd, property 1 for Gram matrices can be strengthened to- G is an odd-integer matrix.
This allows a sharper upper bound 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,
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)(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
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.
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- 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 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
| 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
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 = 112t2±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.
Maximal determinants up to size 18
The maximal determinants of {1, −1} matrices up to size n = 18 are given in the following table. Size 19 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.| 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 Projective plane In mathematics, a projective plane is a geometric structure that extends the concept of a plane. In the ordinary Euclidean plane, two lines typically intersect in a single point, but there are some pairs of lines that do not intersect... 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 |