Exponential lower bound for the determiant of a (0,1)-matrix

Give matrices, which only contain 0 and 1, and their determinant grows exponentially. In other words, show an $n \times n$ matrix for all n, which only contains 0 and 1, and $$\det A(n)>d \cdot c^n,$$ where c>1 and d>0.

Can't really begin, any ideas? Thanks :)

The inequality in question is obviously intimately related to Hadamard’s maximum determinant problem. So, I believe that the most natural construction of $A(n)$ is to make use of Hadamard matrices.

Given any $n\times n$ $\{-1,1\}$ matrix $H$, there is a well-known trick to obtain a $\{0,1\}$ matrix $A$ such that $\det(A)=\frac1{2^{n-1}}|\det(H)|$. First, turn the first row of $H$ into a rows of ones by multiplying columns of $H$ by $-1$ if necessary. Second, for every row $i>1$, add the first row to it and then divide it by $2$. As a result, we get a $\{0,1\}$ matrix. Finally, if the matrix has a negative determinant, interchange some two rows to negate the determinant.

It is also well-known that when $n$ is a power of $2$, Hadamard matrices of size $n$ can be constructed recursively (e.g. Sylvester's construction). Since the determinant of a Hadamard matrix is $\pm n^{n/2}$, it follows that whenever $n=2^m$, there exists a $\{0,1\}$ matrix $A(n)$ whose determinant is $\frac1{2^{n-1}}n^{n/2} = 2(\sqrt{n}/2)^n$.

Now, consider any natural number $n$. Let $n=\sum_{i=1}^k 2^{m_i}+r$, where $m_1>m_2>\cdots>m_k\ge3$ and $0\le r<8$ (convention: $\sum_{i=1}^k 2^{m_i}$ is an empty sum if $n<8$). Therefore, if we define $A(n)=A(2^{m_1})\oplus A(2^{m_2})\oplus\cdots\oplus A(2^{m_k})\oplus I_r$, then $$ \det A(n) = 2^k\prod_{i=1}^k (\sqrt{2^{m_i}}/2)^{2^{m_i}} \ge \prod_{i=1}^k (\sqrt{2^3}/2)^{2^{m_i}} \ge \sqrt{2}^{n-r} > \frac1{16}\sqrt{2}^n. $$

Starting with $$ A_3 = \left( \begin{matrix} 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \end{matrix} \right) \quad |A_3| = 2 $$

using this as blocks on the main diagonal, we get a $A_6$ with $|A_6| = |A_3|^2 = 4$. Continuing doubling the matrix this way we get $$ \left\lvert A_{3\,2^k}\right\rvert= 2^{(2^k)} $$ So if $n = 3\,2^k$ we get $$ |A_n| = 2^{n/3} = (\sqrt[3]{2})^n > (1.25)^n $$ Having the matrix for $n$ this leaves the task of finding the matrices for $n=3\,2^{k}+1$ to $n=3\,2^{k+1}-1$.

Filling up the main diagonal with $1$ elements with increasing $n$ will not change the value of the determinant. So we need to be happy with that determinant not for that one index $n$, but for the next $n-1$ values as well until $n$ arrives at $3\,2^{k+1}$.

$$ 2^{n/3}>c^{2n}>c^{n+(n-1)}>\cdots >c^{n} \iff 1< c < \sqrt[6]{2} = 1.1224\ldots $$ Thus the above construction will beat the exponential with $c=1.12 > 1$, $d=1>0$.

The graph shows that the value for $n=3$ is good enough to dominate until $n=6$ and in turn until $n=12$.

Note: This is just a band matrix of width $5$.

Let be $A$ a $n\times n$ -matrix with only $0$ and $1$ as coefficients. Let us denote by $C_{1},\ldots,C_{n}$ its columns. Then, the Hadamard formula gives us the majoration$$\left|\det\left(C_{1},\ldots,C_{n}\right)\right|\leq\left\Vert C_{1}\right\Vert _{2}\ldots\left\Vert C_{n}\right\Vert _{2}$$ where $\left\Vert .\right\Vert _{2}$ denotes the euclidian norm : for all $v=\left(v_{1},\ldots,v_{n}\right)$ ,$$\left\Vert v\right\Vert _{2}=\sqrt{\left|v_{1}\right|^{2}+\ldots+\left|v_{n}\right|^{2}}.$$ But here, one has $\left\Vert C_{i}\right\Vert _{2}\leq\sqrt{n}$ for all $1\leq i\leq n$ because of the constraint on the coefficients of $A$ . Then$$\left|\det A\right|\leq\left(\sqrt{n}\right)^{n}$$ and this the best majoration one can expect, since $\left\Vert C_{i}\right\Vert _{2}=\sqrt{n}$ iff $C_{i}=\left(1,\ldots,1\right)$ and $\det A=0$ as soon as there are two different $i,j$ such that $C_{i}=\left(1,\ldots,1\right)=C_{j}.$