My question is simply the title:
What is the maximum possible value of determinant of a matrix whose entries either 0 or 1 ?
$\begingroup$
$\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$– DonAntonioJun 20, 2013 at 13:09
-
3$\begingroup$ $n!$ is impossible. $\endgroup$– MherJun 20, 2013 at 13:13
-
$\begingroup$ There can't be any example for that $\endgroup$– MherJun 20, 2013 at 13:13
-
1$\begingroup$ An upper bound that is smaller than $n!$ is $n^{n/2}$. Google Hadamard's inequality. $\endgroup$– KCdJun 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$– MherJun 20, 2013 at 13:16
|
Show 6 more comments
2 Answers
$\begingroup$
$\endgroup$
2
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.
-
$\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$ Jun 20, 2013 at 14:44
-
$\begingroup$
$\endgroup$
7
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;$
-
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$– Oleg567Jun 21, 2013 at 9:51
-
$\begingroup$ Impressive! Were you looking only among the striped ones? For $n=9$ you might need $17$ stripes, so you did not reach the largest value from the list? $\endgroup$ Jul 6, 2022 at 18:25
-
1$\begingroup$ @orangeskid: I looked among the striped shapes just to reduce the search area. The striped matrices provide maximum value for determinant only for small $n$ ($n\le 8$): $$n=9: \qquad det_{max}(striped) =125 \textrm{ vs } det_{max}=144; $$ $$n=10: \qquad det_{max}(striped)=312 \textrm{ vs } det_{max} = 320;$$ $$n=11: \qquad det_{max}(striped)=1215 \textrm{ vs } det_{max}=1458;$$ $\endgroup$– Oleg567Jul 7, 2022 at 13:40
-
1