10
$\begingroup$

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?

$\endgroup$
3

4 Answers 4

12
$\begingroup$

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

$\endgroup$
2
  • 3
    $\begingroup$ The argument can be reversed to build a (-1,1) matrix of size $n+1$ out of any (0,1) matrix of size $n$, so this should be the biggest determinant possible. $\endgroup$ Sep 23, 2010 at 19:47
  • 1
    $\begingroup$ Perhaps it is worth mentioning that there are infinitely many $n$ for which Hadamard matrices exist, since $\binom{H \, \, H}{ H \, -H}$ is Hadamard if $H$ is. $\endgroup$
    – S. Carnahan
    Sep 24, 2010 at 3:21
8
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

( 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

$\endgroup$
3
  • $\begingroup$ Gerhard: Thanks for mentioning my website with Bruce Solomon. Andries Brouwer has a construction that attains Barba's n=1 (mod 4) bound infinitely often. Forming the tensor product with the 2 by 2 Hadamard matrix yields a construction that attains the Ehlich/Wojtas n=2 (mod 4) bound infinitely often. Neubauer and Radcliffe have a construction based on Brouwer's that attains about 1/3 of Ehlich's n=3 (mod 4) bound infinitely often. The matrices on Bruce's and my website were obtained by many people, mostly using computational methods, and reach 70-100% of the bound, but only up to n=120. $\endgroup$ Sep 24, 2010 at 15:35
  • $\begingroup$ The original poster asked about lower bounds as well. As far as I know, there is no lower bound for all n that gets within a constant factor of the upper bound (although I am quite convinced that there should be one). Is this still true? I remember from one of your presentations that you knew of some improvements on Clements and Lindstroem's lower bound. $\endgroup$ Sep 24, 2010 at 15:41
  • 1
    $\begingroup$ Within a constant to all orders, no. C and L have a nicely uniform construction, and I have one that gets refined as more and more Hadamard matrices are found. Using an observation published by Seberry et. al., one can use minors to get close to the upper bound, but even assuming the Hadamard matrix conjecture, one only gets within sqrt(n) multiplicatively using the observation or using my diagonal construction. The nice thing about my construction is that applies to all sufficiently large orders, even though it is nonoptimal. Gerhard "Ask Me About System Design" Paseman, 2010.09.24 $\endgroup$ Sep 24, 2010 at 16:30
1
$\begingroup$

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

$\endgroup$
1

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.