Hadamard's maximal determinant problem

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

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[4] 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).

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,

${\displaystyle G={\begin{bmatrix}A&B\\B^{\mathrm {T} }&D\end{bmatrix}},}$

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[5] and Wojtas[6] 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

${\displaystyle R={\begin{bmatrix}W&X\\Y&Z\end{bmatrix}}}$

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.

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[7] 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 ${\displaystyle r=\lfloor n/s\rfloor .}$

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

${\displaystyle \det R\leq (n-3)^{(n-s)/2}(n-3+4r)^{u/2}(n+1+4r)^{v/2}\left[1-{\frac {ur}{n-3+4r}}-{\frac {v(r+1)}{n+1+4r}}\right]^{1/2},}$

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[8] 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[9] 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.