Known bounds on maximal determinants

N=4j

The general bound on the determinant of {-1, +1} matrices, given by Hadamard [Had], is N^N/2, where N is the order of the matrix. When N is divisible by 4, this bound is sharp by which we mean that there are arbitrarily high values of N that achieve it (Sylvester matrices are one infinite family). The Hadamard bound is achieved only for Hadamard matrices. Paley has conjectured that a Hadamard matrix exists for every order divisible by 4, and thus that the bound is achievable for every such order. The lowest order for which a Hadamard matrix is not yet known to exist is N = 668 [SY]. (On 21 June 2004 Hadi Kharaghani and Behruz Tayfeh-Rezaie announced the discovery of a Hadamard matrix of order 428. Since 1985, this had been the lowest outstanding order [Sa].)

Except for N=1, 2, the Hadamard bound is never achievable when N is not a multiple of 4. Better bounds have been given according to whether N is congruent to 1, 2 or 3 modulo 4, as set out below.

N=4j+1

Barba gave the bound (2N-1)^(1/2) (N-1)^(N-1)/2 [Ba]. It was rederived by Ehlich [E1] and Wojtas [Wo]. (It actually holds for all odd cases, but a better one was found by Ehlich for N=4j+3 [E2].) Clearly the bound can only be achievable when 2N-1 is a perfect square. The bound is sharp, in the sense defined above, due to a construction of Brouwer [Br]. Writing N=2q²+2q+1, his construction gives a matrix of maximal determinant whenever q is a power of an odd prime. The bound is also known to be achievable when N=5 [M], 13 [R] or 41 [BHH, vT].

N=4j+2

Ehlich [E1] and Wojtas [Wo] independently derived the bound 2(N-1) (N-2)^(N-2)/2. The bound is achievable only if N-1 is the sum of two squares. By applying the Sylvester construction to a matrix that achieves the bound of the previous paragraph, a matrix is obtained which achieves the Ehlich/Wojtas bound. In particular, the bound is achieved whenever N=2(2q²+2q+1) for q a power of an odd prime. Therefore the bound is sharp. A second infinite family of constructions, due to Koukouvinos, Kounias, Seberry, Singer and Spence [Sp1, KKS] is known for N=2(q²+q+1) where q is a power of a prime (even or odd).

The bound has also been achieved for certain low orders which do not fall into either of the infinite families. Constructions were given by Ehlich [E1] for N up to 38. Yang [Y1-Y5] added constructions up to N=66, and Cohn [C1, C2] extended this as far as N=102. The case N=86 had previously been handled by Chadjipantelis and Kounias [CK]. Furthermore, maximal matrices were found for N=110 by Fletcher and Seberry [FS], for N=118 by Fletcher, Koukouvinos and Seberry [FKS], for N=126, 186 and N=158, 194, 290 by Djokovic [D1, D2], for N=170 by Gysin [Gys], and for N=150 by Holzmann and Kharaghani [HK]. The lowest outstanding order is 138.

N=4j+3

Ehlich [E2] derived the bound
(n-3)^(n-s)/2 (n-3+4r)^u/2 (n+1+4r)^v/2 {1 - ur / (n-3+4r) - v(r+1) / (n+1+4r)}^1/2
where s=3 for n=3, s=5 for n=7, s=5 or 6 for n=11, s=6 for n=15, 19, ..., 59, and s=7 for n ≥ 63, r = [n/s], n = rs + v and u = s - v. Here [n/s] represents the floor of n/s. Cohn [C4] showed that the bound is an integer only when n=112t² ± 28t + 7 for some positive integer t. It is not known if the bound is sharp with the meaning used above, or even if it is achievable beyond n=3.

Back to maximal determinant main page.
Page created 2 March 2002.
Last modified 3 May 2007.
Comments: maxdet@indiana.edu