Maximum determinant of $\{0,1\}$-valued $n\times n$-matrices

Question

What's the maximum determinant of $\{0,1\}$ matrices in $M(n,\mathbb{R})$?

If there's no exact formula what are the nearest upper and lower bounds do you know?

Answer 1

I shouldn't expect there to be exact results; compare the similar problem with matrices with entries $\pm1$. For an $n$-by-$n$ matrix with entries $\pm1$ one gets an upper bound for the determinant of $n^{n/2}$ with equality iff the matrix is a Hadamard matrix. The determination for which $n$ Hadamard matrices exist still resists proof.

If there is an $n$-by-$n$ Hadamard matrix $H$, one can make its top row all ones, and then add it to the other rows and divide them by $2$. This gives a zero-one matrix $A$ with determinant $2^{-n+1}n^{n/2}$. Taking some extra care one can ensure the first column of $A$ has a $1$ atop a column of zeros so that deleting the first row and column gives a smaller matrix with the same determinant. It's not clear to me whether this is the biggest possible....

Answer 2

As pointed out in Robin Chapman's answer and Frederio Poloni's comment thereto, there is a one-to-one map between normalized $n$-by-$n$ $(-1,1)$ matrices and $(n-1)$-by-$(n-1)$ $(0,1)$ matrices under which the determinant gets multiplied by $2^{-n+1}$ and possibly a minus sign. Since normalizing a $(-1,1)$ matrix changes the determinant by at most a sign, the maximal determinant problem for $(-1,1)$ matrices of size $n$ is equivalent to the maximal determinant problem for $(0,1)$ matrices of size $n-1$.

An advantage to working with $(-1,1)$ matrices is that their rows are all vectors of the same magnitude, $\sqrt{n}$. If the rows are orthogonal, the matrix is Hadamard and the magnitude of the determinant is $n^{n/2}$ which is the best possible. It is not hard to show that if a Hadamard matrix of size $n$ exists, than $n$ is 1, 2, or a multiple of 4, but it is not known whether a Hadamard matrix exists for every multiple of 4.

If $n$ is not a multiple of 4, better upper bounds on the determinant of an $n$-by-$n$ $(-1,1)$ matrix $R$ can be obtained by analyzing the properties that the matrix $G=RR^{T}$ must have. An upper bound on the determinant for the class of matrices $\tilde G$ with these properties leads to an upper bound on $\det R$ by taking the square root. This idea was developed by Barba, Ehlich, and Wojtas, leading to the following bounds:

$n\equiv1\pmod{4}$: The optimal $\tilde G$ is $J+(n-1)I$ where $J$ is the all-ones matrix. Therefore $\det R\le\sqrt{2n-1}(n-1)^{(n-1)/2}$. Clearly this bound is attainable only if $2n-1$ is a perfect square. It is not known whether this is if-and-only-if, but that is conjectured to be the case.

$n\equiv2\pmod{4}$: The optimal $\tilde G$ is $2\binom{J \ \ 0\ }{0 \ \ J}+(n-2)I$ where $J$ and $0$ are $n/2$-by-$n/2$ matrices. This provides the bound $\det R \le (2n-2)(n-2)^{(n-2)/2}$. It can be shown that an $R$ such that $RR^T$ equals this optimal form exists only if $n-1$ is the sum of two squares. Once again, this is conjectured to be if-and-only-if.

$n\equiv3\pmod{4}$: The optimal $\tilde G$ is $-J+4B+(n-3)I$ where $B$ is a block-diagonal matrix with all-ones blocks along the diagonal. These all-ones blocks should be as nearly equal in size as possible and their number should be five if $n=7$, five or six if $n=11$, six if $15 \le n \le 59$, and seven if $n \ge 63$. The bound on $\det \tilde G$ one gets from this is seldom a perfect square, and even when it is, Tamura showed that the existence of an $R$ such that $RR^T$ equals the optimal $\tilde G$ is ruled out by the Hasse-Minkowski theorem in many cases. The smallest $n$ for which the bound might be attainable is 511. Nevertheless, there exist matrices with determinant quite close to the bound. For example, when $n=19$, a matrix whose determinant attains 97.5% of the bound is known. Using a lot of computer time, this particular determinant was recently shown to be best possible by Brent, Osborn, Zimmermann and myself.

Answer 3

( I assume the R in the title is the real numbers. For arbitrary rings R an order needs to be specified before remarks like those below should be made. )

Using the method suggested by Robin Chapman, the maximum determinant problem for nxn matrices with entries from {0,1} is equivalent to a similar problem involving (n+1)x(n+1) matrices with entries from the set {-1,1}. In this latter form, the determinant is maximal when n+1 = 4k (for large enough n) and the matrix H satisifies H*H^t = (n+1)I, ie. the {-1,1} matrix H has det(H) at its biggest when H times its transpose is the identity matrix times its order.

This form ( H*H^t = (n+1)I ) is convenient: for some orders n+1 not a multiple of 4, we still have that the {-1,1} matrix H has det(H) maximal when H*H^t = B + J, where B is a block diagonal matrix and J is a matrix with all ones. This implies a slightly sharper upper bound discovered by Ehlich for these orders.

The links provided by others will lead to Will Orrick's site (among others) on Hadamard's maximum determinant problem. He cites recent constructions ( with Neugebauer, Dowdeswell and others, if memory serves ) for many orders which are not a multiple of 4, for {-1,1} matrices with large determinant, such determinant being within a constant multiplicative factor (something like 1/3) of the upper bound.

To repeat a point of Robin's post, there are still many k for which it is not known if the maximum determinant of (4k)^(2k) is achieved for {-1,1} matrices of order 4k.

Gerhard "Ask Me About System Design" Paseman, 2010.09.23

Answer 4

This site lists many of those extremal matrices (for the equivalent $\pm1$ case) and other useful information.