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



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](https://mathoverflow.net/questions/81496/bounding-the-absolute-sum-of-entries-of-the-inverse-of-a-0-1-matrix/81514#81514))
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))))))

```

