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 :)
 A: 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.
$$
A: 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}.$
A: 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$.
A: Make a $4 \times 4$ matrix $A_0$ of the desired form with determinant $\det A = \alpha > 1$. Then define $A_i = \begin{pmatrix}A_{i-1} & 0 \\ 0 & A_{i-1} \end{pmatrix}$ for $i = 1, 2, 3, \dots$. 
Now $A_i$ is $n \times n$ with $n = 2^{i+2}$ and $\det A_i = \alpha^{2^i} = \alpha^{n/4} = \tilde c^n, \, \tilde c = \alpha^{1/4} > 1$.
This give you matrices with the desired properties for $n = 2^{2+i}$. For general $n$, e.g. $m < n < 2m$ with $m = 2^{2+i}$, use $A_i$ as before, with $\det A_i = c^m$, and set $A = \begin{pmatrix} A_i & 0 \\ 0 & I_{n-m} \end{pmatrix}$, where $I_{n-m}$ is the identidy matrix. 
Edit to fix the lower bound:
Then $A$ is $n \times n$ and 
$$
\det A = \det A_i = \tilde c^m = \sqrt{\tilde c}^{2m}\ge \sqrt{\tilde c}^n \, .
$$
So you'll get the desired estimate with $c = \sqrt{\tilde c} = \alpha^{1/8}, \, d = 1$. 
With 
$$A_0 = \begin{pmatrix}1& 0& 0& 1 \\ 0& 1& 1& 1\\ 1& 1& 0& 0 \\1 & 0& 1& 0 \end{pmatrix}
$$
one gets $\alpha = 3$ which is maximal. Then $c = \alpha^{1/8} =  1.14720\dots$.
