Hadamard's maximal determinant problem

Hadamard matrices

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 k for which a 4k×4k Hadamard matrix is not known to exist is 167.

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:

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:

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

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

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 = RR^T and G′ = R^TR 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²+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 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 r = ⌊ n / s ⌋ .

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²±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 21

The maximal determinants of {1, −1} matrices up to size n = 21 are given in the following table. 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.