Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
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}.$
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$.
:)
$\endgroup$