12
$\begingroup$

The problems of determining the maximum determinant of an $n \times n$ $(0,1)$-matrix and the spectral problem of determining exactly which other determinants can possibly occur are both reasonably well studied.

What I'd like to know is whether there are bounds known if the number of 1s in the matrix is specified.

In other words, if we let $f(n,k)$ denote the maximum determinant of an $n \times n$ $(0,1)$-matrix with exactly $k$ ones (in total, not per row), then are there any known bounds on the values for $f(n,k)$?

I've searched Math Reviews and Googled it, but all the papers that I have found refer to the maximum over the entire set of $n \times n$ matrices.

Edit: Here is a plot of the maximum determinant of a binary $6 \times 6$ matrix with $k$ 1s, where $0 \leq k \leq 36$ (as long as I haven't messed up the computation).

Maximum determinant

Edit 2: Here is the analogous plot for $7 \times 7$ matrices.

Maximum determinants for n=7

Edit 3: Here is a plot of the bound given by Peter Mueller's post, together with the actual values for n=7.

enter image description here

$\endgroup$
  • 1
    $\begingroup$ No literature I know addresses your precise question. Zivkovic in his 2005 arxiv classification paper comes closest; by using certain similarities in his paper you can transform matrices to different 1 counts while preserving determinant. Also Will Orrick might know of recent work. $\endgroup$ – The Masked Avenger Sep 11 '14 at 11:29
  • $\begingroup$ Also, using block matrices and certain constructions (cf Zivkovic, Schmidt, Paseman), one can give an exponential lower bound on your curve up to n^2/4 roughly. $\endgroup$ – The Masked Avenger Sep 11 '14 at 11:37
  • $\begingroup$ For $n=6,7$, are the maximums achieved for matrices with constant row and column sums? $\endgroup$ – Brendan McKay Sep 12 '14 at 2:33
  • $\begingroup$ For $n=7$, the maximum of 32 is achieved (uniquely) by the incidence matrix of the $2-(7,4,2)$ design (complement of the Fano) so row and column sums are all 4. For n=6 there are 7 extremal ones, some regular some not. $\endgroup$ – Gordon Royle Sep 12 '14 at 3:20
  • $\begingroup$ Let me mention some recent progress here. If $d$ is small (by which I mean $d\leqslant n$), then the maximal determinant of a $0$-$1$ matrix $A$ with at most size(A)+d ones is at least $2^{d/3}\approx 1.26^d$ and at most $1.29^d$. (See Conjecture 4 in bit.ly/2LeXqSW and the note bit.ly/2swpF7O.) $\endgroup$ – Yaroslav Shitov Jun 1 '18 at 20:21
7
$\begingroup$

In this paper Gasper, Pfoertner and Sigg prove an interesting upper bound for a real $n\times n$ matrix $M$: Let $n\alpha$ and $n\beta$ be the sum of the entries or the squares of the entries of $M$, respectively. Set $\delta=(\alpha^2-\beta)/(n-1)$. If $\delta\ge0$, then $\lvert\det M\rvert\le \alpha(\beta-\delta)^{(n-1)/2}$.

So $\alpha=\beta=k/n$ for a $(0,1)$-matrix. In contrast to the Hadamard bound, this bound is attained quite often for $(0,1)$-matrices, namely for the incidence matrices of symmetric block designs. Looking at their (somewhat involved) proof, this result is not surprising, for they show that upon fixing $\alpha$, $\beta$ and $n$, the maximum of the determinant is attained if $MM^t$ is a linear combination of the identity matrix and the all $1$ matrix.

$\endgroup$
  • $\begingroup$ Do they give a bound when delta is negative? $\endgroup$ – The Masked Avenger Sep 13 '14 at 0:25
  • $\begingroup$ Yes, in this case $\lvert\det M\rvert\le\beta^{n/2}$. $\endgroup$ – Peter Mueller Sep 13 '14 at 6:51
9
$\begingroup$

The argument used in Hadamard's inequality works here too: If $A$ is the matrix, then ${\rm tr}(A^{t}A) = k,$ so if $\lambda_{1},\lambda_{2}, \ldots, \lambda_{n}$ are the (real, non-negative) eigenvalues of $A^{t}A$, then $\sum_{i=1}^{n}\lambda_{i} =k.$ Hence $|{\rm det}(A)| = \prod_{i=1}^{n} \lambda_{i}^{\frac{1}{2}} \leq \left(\sqrt{\frac{k}{n}} \right)^{n}.$ The determinant is obviously $0$ if $k < n.$

( Later edit: I don't know whether this might be useful, but if we let $J$ be the all $1$'s matrix, note that if the $\alpha$-eigenspace of $A$ has dimension greater than $1,$ it non-trivially intersects the $0$ eigenspace of $J,$ which has dimension $n-1.$ Hence $-\alpha$ is an eigenvalue of $J-A,$ which is also a $\{0,1\}$-matrix, but with $n^{2}-k$ non-zero entries. Even later edit, somewhat related (indirectly, I think) to Peter Mueller's comment: in particular, if ${\rm rank}(J-A) <n-1,$ then $J$ and $J-A$ have a common non-zero eigenvector with eigenvalue $0,$ so also ${\rm det}(A) = 0).$

$\endgroup$
  • 4
    $\begingroup$ The determinant is $0$ too if $k>n^2-n+1$, because then there are two rows filled with $1$'s only. $\endgroup$ – Peter Mueller Sep 11 '14 at 8:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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