# 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 maximal determinants are give in oeis.org/A003432 with some references. – Ross Millikan Feb 15 '15 at 15:35
• Such a fast growth property actually holds (in expectation) for random $0-1$ matrices. See this mathoverflow post: mathoverflow.net/a/13040/24119 – Nick Alger Feb 15 '15 at 20:33

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$.

• I think an even simpler proof/series is possible using the continuant and the fact that the Fibonacci number is growing exponentially, but I don't have time to work out the detail tonight. – Fizz Feb 16 '15 at 0:42
• Ah, never mind, that won't work because in order to get the Fibonacci recurrence as the continuant you need a negative number (e.g. -1) on a sub-diagonal, but that's not allowed with a (0,1)-matrix. – Fizz Feb 16 '15 at 3:07
• This is probably as easy as it gets and simple because one just wants exponential growth but not the optimal growth. Getting a maximal determinant at each $n$ is probably very complicated. – mvw Feb 16 '15 at 3:22
• Computing the determinant of pentadiagonal matrix (in general) is apparently a rather obscure topic. I found a paper giving a recurrence for it though: hdl.handle.net/1813/5871 – Fizz Feb 16 '15 at 3:29
• It is however relatively simple to get the permanent of a (0,1) super diagonal matrix expressed in terms of the generalized Fibonacci numbers: fq.math.ca/Scanned/33-3/lee.pdf That's because with the permanent you don't have to deal with changes in sign (as in the case of the determinant). – Fizz Feb 16 '15 at 4:01

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}.$

• How does this exhibit a sequence of matrices with exponentially growing determinants? – Kimball Feb 15 '15 at 16:02
• It does not! Simply, Atvin seemed not to have any idea about how to deal with the question. At first, I thought that this majoration will prevent any exponential growth, but it only gives a maximum growth rate. Anyway, Ross Millikan gave us an answer. – Nicolas Feb 15 '15 at 16:08
• Ah, okay. I wasn't sure if you were trying to assert this somehow answered the question. (Maybe it's helpful when you just give a related comment as an answer to say so to minimize confusion.) – Kimball Feb 15 '15 at 16:28
• Sorry if it was confusing ! – Nicolas Feb 15 '15 at 16:35

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.$$

• I think this construction can be used to provide a sequence $A(n)$ of $n \times n$ matrices such that $\liminf \left( \det A_n \right)^{1/n} = \infty$. For $n = 2^m$ your argument already constructs it and for the remaining $n$ one can use some kind of padding argument. – Hans Engler Feb 16 '15 at 23:09
• IF someone needs a more "for dummies" version of the construction of the (0,1)-matrix, there's one in a Wikipedia sub-article of the one linked in answer. – Fizz Feb 17 '15 at 4:56

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$.

• I'm not sure I understand how $A_2$ is defined in terms of $A_0$. – user84413 Feb 15 '15 at 18:30
• Is the $A_{i=1}$ entry supposed to be $A_{i+1}$, or is that some notation with which I'm not familiar? – wchargin Feb 15 '15 at 18:33
• @WChargin: It's supposed to be $A_{i-1}$. It's a diagonal block construction, like mvw's solution, but this one uses a larger initial matrix... I can't tell who of them posted first, but they probably had the same idea simultaneously more or less. – Fizz Feb 16 '15 at 0:35
• @RespawnedFluff This post is 21 minutes and 4 seconds newer :) – wchargin Feb 16 '15 at 0:42
• Doubling is natural, otherwise it is hard to relate the new determinant value to the old one, and it is a way to not decrease the determinant. On the bad side it wastes bits and growth of the determinant values comes from newly added bits. What to do with the in between instances took me a while during this I saw that Hans added an identity matrix, but I still do not get his estimations. I was able to come up with my own estimations, when I tried to degrade a larger instance to the smaller, until I realized that doing nothing, keeping the old value might suffice. – mvw Feb 16 '15 at 3:18