[Math] Are bounds known for the maximum determinant of a (0,1)-matrix of specified size and with a specifed number of 1s

determinantsmatrices

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

Best Answer

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.

Related Question