Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

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

2 Answers 2

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

share|improve this answer
    
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 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 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 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 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$.

share|improve this answer
    
Why doesn't your formula and my empirical result agree? –  John Habert Feb 6 at 22:03
    
Our matrices are different. Yours has one zero value, mine has $n-1$. –  Michael Grant Feb 6 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 at 22:08
    
Your matrix is $\vec{1}\vec{1}-e_1e_1^T$. Simpler than mine, to be sure. –  Michael Grant Feb 6 at 22:09
    
If it can be shown that the smallest absolute value is $1/n$ that would be great. –  Anush Feb 6 at 22:12

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.