# 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}$)?

-
A square matrix whose values are either $0$ or $1$. – Anush Feb 6 '14 at 20:10
Yes, please elaborate – David Simmons Feb 6 '14 at 20:11
Please edit your question to make this clear. Regards – David Simmons Feb 6 '14 at 20:12
@Dror: John Habert just showed in his answer that this is wrong. – Andreas H. Feb 6 '14 at 21:14
Cross-posted to mathoverflow.net/questions/157472/… now. – Anush Feb 13 '14 at 11:17

For a $2\times 2$ matrix, the smallest is $\left| \dfrac{1-\sqrt{5}}{2}\right|$ from $\begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}$ or $\begin{pmatrix} 0 & 1 \\ 1 & 1 \end{pmatrix}$.

For a $3\times 3$ matrix, the smallest is $\left|\frac{1}{2}(3-\sqrt{5})\right|$ from $\begin{pmatrix} 1 & 0 & 1 \\ 1 & 1 & 1 \\ 1 & 1 & 1 \end{pmatrix}$ or any other matrix with all entries $1$ except for a single off (main) diagonal $0$.

Best so far - have more calculations to run and check

For a $4\times 4$ matrix, the smallest is $\left|2-\sqrt{3}\right|$ from $\begin{pmatrix} 1 & 0 & 1 & 1 \\ 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 \end{pmatrix}$

-
OK, I think your eigenvalues are $\tfrac{1}{2}\left(n\pm\sqrt{n^2-4}\right)$, which is bounded below by $1/n$. Note that this doesn't work for 2x2; my derivation starts with at least a 3x3. – Michael Grant Feb 7 '14 at 3:38
@MichaelC.Grant Added best so far for $n=4$ case. I think I've found a smaller but need to double check things. Even with the smaller one, bound of $\frac{1}{n+1}$ seems to be holding so far. – John Habert Feb 7 '14 at 3:42
I verified the correctness of my formula in the previous comment up to $n=1000$, for a matrix with all ones except a single zero in the $(1,2)$ position. That's not to say better matrices do not exist; but for a single off-diagonal nonzero, that's it. – Michael Grant Feb 7 '14 at 4:22
@MichaelC.Grant Nice work. I'm going to finish rechecking $n=4$ to see if the better case still exists. Discovered my code wasn't giving correct output. – John Habert Feb 7 '14 at 4:32

Consider the $n\times n$ matrix $$E_n = \vec{1} \vec{1}^T + e_1 e_1^T - I$$ where $\vec{1}$ is the vector of all ones, $e_1$ is the vector with a $1$ in the first element and zeros elsewhere, and $I$ is the identity matrix. In other words, $E_n$ has ones everywhere except the latter $n-1$ elements of the diagonal.

Empirically, I'm finding that the smallest nonzero eigenvalue in absolute value is approximately $-1/n$. I suspect that could be bounded rigorously, and if I can do so, I'll edit this answer. But it would seem clear to me that the smallest non-zero eigenvalue cannot be bounded away from zero.

EDIT: The eigenvalues of $E_n$ for $n>2$ are $-1$ and $$\frac{n-1\pm\sqrt{(n-1)^2+4}}{2}=\frac{n-1}{2}\pm\sqrt{\left(\frac{n-1}{2}\right)^2+1}.$$ The smallest absolute value is therefore $$\sqrt{\left(\frac{n-1}{2}\right)^2+1}-\frac{n-1}{2}\geq \frac{1}{n-1}.$$ Of course, this is not a bound for all $\{0,1\}$ matrices, just for this one.

EDIT: John Habert's 3x3 matrices and 4x4 matrices do better than this. For a matrix will all ones except a single off-diagonal zero, the eigenvalues are 0 (with $n-2$ multiplicty) and $$\frac{n}{2} \pm \sqrt{ \frac{n^2}{4} - 1 } \geq \frac{1}{n}.$$ I verified this numerically up to $n=1000$.

-
Why doesn't your formula and my empirical result agree? – John Habert Feb 6 '14 at 22:03
Our matrices are different. Yours has one zero value, mine has $n-1$. – Michael Grant Feb 6 '14 at 22:06
Plus it appears I've miscalculated something. Double-checking on my own side shows my 3 by 3 answer is off. Will figure out why. – John Habert Feb 6 '14 at 22:08
Your matrix is $\vec{1}\vec{1}-e_1e_1^T$. Simpler than mine, to be sure. – Michael Grant Feb 6 '14 at 22:09
If it can be shown that the smallest absolute value is $1/n$ that would be great. – Anush Feb 6 '14 at 22:12