14
$\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

Improve this question
$\endgroup$
7
  • 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, 2014 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, 2014 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, 2014 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, 2014 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, 2018 at 20:21

2 Answers 2

Reset to default
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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Do they give a bound when delta is negative? $\endgroup$
    – The Masked Avenger
    Sep 13, 2014 at 0:25
  • $\begingroup$ Yes, in this case $\lvert\det M\rvert\le\beta^{n/2}$. $\endgroup$
    – Peter Mueller
    Sep 13, 2014 at 6:51
  • $\begingroup$ Markus Sigg has written a follow up of our cited paper, fixing an error in the proof of the cited theorem and showing some new examples related to (0,1) matrices. $\endgroup$
    – Hugo Pfoertner
    Nov 4, 2020 at 16:43
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).$

Improve this answer
$\endgroup$
1
  • 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, 2014 at 8:27

Your Answer

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

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