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 .
The smallest nonzero eigenvalue can decrease at least exponentially, even for matrices that are sparse, symmetric, and invertible.
Explicitly, let $M_n$ have $1$'s on the anti-diagonal, and also on the first and third off-diagonals above it. For example, here's the matrix for $n=13$:
0 0 0 0 0 0 0 0 0 1 0 1 1
0 0 0 0 0 0 0 0 1 0 1 1 0
0 0 0 0 0 0 0 1 0 1 1 0 0
0 0 0 0 0 0 1 0 1 1 0 0 0
0 0 0 0 0 1 0 1 1 0 0 0 0
0 0 0 0 1 0 1 1 0 0 0 0 0
0 0 0 1 0 1 1 0 0 0 0 0 0
0 0 1 0 1 1 0 0 0 0 0 0 0
0 1 0 1 1 0 0 0 0 0 0 0 0
1 0 1 1 0 0 0 0 0 0 0 0 0
0 1 1 0 0 0 0 0 0 0 0 0 0
1 1 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0 0 0 0
Then (much as in this answer) the inverse matrix $M_n^{-1}$ is anti-triangular with constant antidiagonals; thus it is determined by its bottom row, and this bottom row is $1, -1, 1, -2, 3, -4, 6, -9, 13, -19, 28, -41, \ldots$, with alternating signs and absolute values satisfying the recurrence $t_m = t_{m-1} + t_{m-3}$. Thus $t_m$ grows like a multiple of $C^m$ where $C = 1.46557\ldots$ is the real root of $C^3 = C^2 + 1$, and the main diagonal of $M_n^{-1}$ has constant sign. Here is $M_{13}^{-1}$:
0 0 0 0 0 0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 0 0 0 0 1 -1
0 0 0 0 0 0 0 0 0 0 1 -1 1
0 0 0 0 0 0 0 0 0 1 -1 1 -2
0 0 0 0 0 0 0 0 1 -1 1 -2 3
0 0 0 0 0 0 0 1 -1 1 -2 3 -4
0 0 0 0 0 0 1 -1 1 -2 3 -4 6
0 0 0 0 0 1 -1 1 -2 3 -4 6 -9
0 0 0 0 1 -1 1 -2 3 -4 6 -9 13
0 0 0 1 -1 1 -2 3 -4 6 -9 13 -19
0 0 1 -1 1 -2 3 -4 6 -9 13 -19 28
0 1 -1 1 -2 3 -4 6 -9 13 -19 28 -41
1 -1 1 -2 3 -4 6 -9 13 -19 28 -41 60
Hence the trace of $M_n^{-1}$ grows as $\pm C^n$, so its largest eigenvalue grows at least as $\pm C^n/n$. Therefore the smallest eigenvalue of $M_n$ is $O(n/C^n)$.
(Numerical computation suggests that in fact there's only one really small eigenvalue, which is thus $O(C^{-n})$; for example, $M_{13}$ has an eigenvalue $0.008902\ldots$, and the next-smallest eigenvalues are about $-.78$ and $.82$.)
Here's some gp code to generate the matrix $M_n$ and the absolute value m(n) of its least eigenvalue:
M(n) = matrix(n,n,i,j, (i+j == n+1) + (i+j == n) + (i+j == n-2))
m(n) = vecmin(abs(real(polroots(charpoly(M(n))))))
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.
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).
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.
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.
