12
$\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$
11
  • $\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, 2013 at 13:09
  • 2
    $\begingroup$ $n!$ is impossible. $\endgroup$
    – Mher
    Jun 20, 2013 at 13:13
  • $\begingroup$ There can't be any example for that $\endgroup$
    – Mher
    Jun 20, 2013 at 13:13
  • 1
    $\begingroup$ An upper bound that is smaller than $n!$ is $n^{n/2}$. Google Hadamard's inequality. $\endgroup$
    – KCd
    Jun 20, 2013 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, 2013 at 13:16

2 Answers 2

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$
2
  • $\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, 2013 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, 2013 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$
2
  • 1
    $\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$ Jun 21, 2013 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, 2013 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.