8
$\begingroup$

My question is simply the title:

What is the maximum possible value of determinant of a matrix whose entries either 0 or 1 ?

$\endgroup$
  • $\begingroup$ Since the determinant is the sum of $\,n!\,$ products of elements of the matrix chosen in a particular way, I'd say the maximum value is $\,n!\,$ ...but I've no example to offer. $\endgroup$ – DonAntonio Jun 20 '13 at 13:09
  • 2
    $\begingroup$ $n!$ is impossible. $\endgroup$ – Mher Jun 20 '13 at 13:13
  • $\begingroup$ There can't be any example for that $\endgroup$ – Mher Jun 20 '13 at 13:13
  • $\begingroup$ An upper bound that is smaller than $n!$ is $n^{n/2}$. Google Hadamard's inequality. $\endgroup$ – KCd Jun 20 '13 at 13:14
  • $\begingroup$ I can offer an example for $n-1.$ Taking $a_{ii}=0$ and $a_{ij}=1$ if $i\neq j.$ $\endgroup$ – Mher Jun 20 '13 at 13:16
6
$\begingroup$

Quoting my question in another thread:

In fact, I don't even know how large the determinant of a 0-1 matrix can be. The Hadamard's bound for the absolute determinant of an $n\times n$ 0-1 matrix is $\frac{(n+1)^{(n+1)/2}}{2^n}$ (online ref. 1 and ref. 2), and the bound is sharp if and only if there exists a Hadamard matrix of order $n+1$. Yet, to my knowledge, there is no known sharp upper bound for the absolute determinant of a general $n\times n$ 0-1 matrix.

$\endgroup$
  • $\begingroup$ Hm, can someone explain (or direct me to someplace) to understand why this answer is a community wiki? I've not dealt with community wikis before, so just curious. $\endgroup$ – Calvin Lin Jun 20 '13 at 14:44
  • $\begingroup$ @CalvinLin See an explanation here. In the present case I turned my answer into a community wiki one on purpose, because I didn't think simply quoting my own question verbatim deserves any reputation points. $\endgroup$ – user1551 Jun 20 '13 at 15:13
3
$\begingroup$

A few examples of $\{0,1\}$-matrices (with the largest determinants $-$ according to OEIS-A003432):

$n=2$: $\quad\det\left( \begin{array}{cc} \bf{1} & 0 \\ \bf{1} & \bf{1} \\ \end{array} \right) =1;$

$n=3$: $\quad\det\left( \begin{array}{ccc} \bf{1} & 0 & \bf{1} \\ \bf{1} & \bf{1} & 0 \\ 0 & \bf{1} & \bf{1} \\ \end{array} \right) =2;$

$n=4$: $\quad\det\left( \begin{array}{cccc} \bf{1} & 0 & \bf{1} & 0 \\ \bf{1} & \bf{1} & 0 & \bf{1} \\ 0 & \bf{1} & \bf{1} & 0 \\ 0 & 0& \bf{1} & \bf{1} \\ \end{array} \right) =3;$

$n=5$: $\quad\det\left( \begin{array}{ccccc} \bf{1} & 0 & \bf{1} & 0 & 0\\ \bf{1} & \bf{1} & 0 & \bf{1} & 0 \\ 0 & \bf{1} & \bf{1} & 0 &\bf{1}\\ 0 & 0 & \bf{1} & \bf{1} & 0 \\ \bf{1} & 0 & 0 & \bf{1} & \bf{1} \\ \end{array} \right) =5;$

$n=6$: $\quad\det\left( \begin{array}{ccccc} \bf{1} & 0 & \bf{1} & 0 & 0 & 0\\ \bf{1} & \bf{1} & 0 & \bf{1} & 0 & 0 \\ 0 & \bf{1} & \bf{1} & 0 &\bf{1} & 0\\ 0 & 0 & \bf{1} & \bf{1} & 0 & \bf{1}\\ \bf{1} & 0 & 0 & \bf{1} & \bf{1} & 0\\ \bf{1} & \bf{1} & 0 & 0 & \bf{1} & \bf{1} \\ \end{array} \right) =9;$

$n=7$: $\quad\det\left( \begin{array}{ccccc} \bf1 & 0 & \bf1 & 0 & 0 & \bf1 & \bf1 \\ \bf1 & \bf1 & 0 & \bf1 & 0 & 0 & \bf1 \\ \bf1 & \bf1 & \bf1 & 0 & \bf1 & 0 & 0 \\ 0 & \bf1 & \bf1 & \bf1 & 0 & \bf1 & 0 \\ 0 & 0 & \bf1 & \bf1 & \bf1 & 0 & \bf1 \\ \bf1 & 0 & 0 & \bf1 & \bf1 & \bf1 & 0 \\ 0 & \bf1 & 0 & 0 & \bf1 & \bf1 & \bf1 \\ \end{array} \right) =32;$

$n=8$: $\quad\det\left( \begin{array} \bf1 & 0 & \bf1 & 0 & 0 & \bf1 & \bf1 & 0 \\ \bf1 & \bf1 & 0 & \bf1 & 0 & 0 & \bf1 & \bf1 \\ \bf1 & \bf1 & \bf1 & 0 & \bf1 & 0 & 0 & \bf1 \\ 0 & \bf1 & \bf1 & \bf1 & 0 & \bf1 & 0 & 0 \\ 0 & 0 & \bf1 & \bf1 & \bf1 & 0 & \bf1 & 0 \\ \bf1 & 0 & 0 & \bf1 & \bf1 & \bf1 & 0 & \bf1 \\ 0 & \bf1 & 0 & 0 & \bf1 & \bf1 & \bf1 & 0 \\ 0 & 0 & \bf1 & 0 & 0 & \bf1 & \bf1 & \bf1 \\ \end{array} \right) =56;$

$\endgroup$
  • $\begingroup$ Very nice! I was also looking for patterns of symmetry but didn't search too long... (I stopped after having brute-forced $n=4$ with $2^{16}$ variants of the matrix ... ;-)) $\endgroup$ – Gottfried Helms Jun 21 '13 at 9:47
  • $\begingroup$ Yes, we can find first 8 matrices among striped matrices ($\searrow \searrow \searrow$). What about others $n$ ??? $\endgroup$ – Oleg567 Jun 21 '13 at 9:51

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.