Smallest non-zero eigenvalue of a (0,1) matrix What's the smallest absolute value possible of a non-zero eigenvalue of an $n$ by $n$ square matrix whose entries are either $0$ or $1$ (all operations are over $\mathbb{R}$)?  I would be interested in estimates or bounds as I imagine an exact answer is tricky.
I asked this question previously at https://math.stackexchange.com/questions/666493/smallest-non-zero-eigenvalue-of-a-0-1-matrix .
 A: There is a pretty crude lower bound, namely $1/n^{n-1}$. This is obtained by observing that the product of the nonzero eigenvalues is one of the symmetric functions, hence here must have absolute value at least one. The largest possible absolute eigenvalue of a size $n$ $0-1$ matrix is $n$, so we have $s\cdot n^{n-1} \geq 1$ where $s$ is the smallest absolute value of a nonzero eigenvalue. 
This is really crude, since if one of the eigenvalues is $n$, then the matrix is rank one, so it won't yield anything interesting, and along these lines, I suspect that if the largest eigenvalue is close to the maximum ($n$), then the other eigenvalues will be much much smaller (possibly less than one in absolute value), so the product argument will not give anything close ...
Since for small values of $n$, there are really not that many $0-1$ matrices (and many, e.g., determinant zero, can probably be discarded anyway), it is possible to calculate the minimal absolute eigenvalue. A table of these would be helpful.
One I can do by hand; if $n=2$, then $s = 1/\gamma$ (reciprocal of the golden ratio). 
A: The circulant matrix with first row $c_0,c_{n-1},\dots,c_2,c_1$ has eigenvalues $$\lambda_j=c_0+c_{n-1}\omega_j+\cdots+c_2\omega_j^{n-2}+c_1\omega_j^{n-1}$$ where $\omega_j=e^{2\pi ij/n}$, so if you can find a small sum of $n$th roots of unity, you can find a 0-1 matrix with a small eigenvalue. There is some discussion of the question of small sums of roots of unity here. 
I'm not suggesting that circulant matrices will give the smallest possible eigenvalues, only that what you get from them will give you some sort of bound. 
A: The correct asymptotic behavour is $n^{-n/2(1+o(1))}$. This is proved in:
N. Alon and V. H. Vu, Anti-Hadamard matrices, coin weighing,
threshold gates and indecomposable hypergraphs, J. Combinatorial
Theory, Ser. A 79 (1997), 133-160.
A: This is not an answer, but some remarks that the OP might find interesting. For symmetric matrices, a related question has been studied previously, namely that of bounding the largest and smallest eigenvalues, for more general matrices.
In particular, let $S_n[a,b]$ denote the set of $n\times n$ symmetric real matrices with entries in the interval $[a,b]$ ($a < b$ is assumed). Then, for $n \ge 2$, X. Zhan (2005) proves that for $A \in S_n[a,b]$, 
\begin{equation*}
 \lambda_{\min}(A) \ge 
       \begin{cases} n(a-b)/2, & n\ \text{odd}\\
       (na-\sqrt{a^2+(n^2-1)b^2})/2, & n\ \text{even}.\end{cases}
\end{equation*}
He goes on to provide an iff characterizing when equality occurs in the above inequality.
Following the ideas in the linked paper (combined with some Perron-Frobenius theory) it might be possible to derive results for $|\lambda(A)|$, but right now I don't have time to think about that.
Edit. I must add the caveat that characterising $\lambda_j(A)$ for $A \in S_n[a,b]$ is still an open problem, which means that it might be tricky to get something for $|\lambda_j(A)|$ even for symmetric matrices.
