23
$\begingroup$

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 .

$\endgroup$
4
  • $\begingroup$ I may be confusing myself, but for nonsingular matrices, I think Smith Normal Form gives that 1 is the smallest value. For singular matrices, I think the value can run the gamut from 2 to n (verification needed). $\endgroup$ Feb 13, 2014 at 15:31
  • $\begingroup$ Indeed, it is tricky, and I did confuse myself. For the 2 by 2 case, I get the golden ratio and its conjugate for eigenvalues (and also 0,1, and 2), so SNF does not seem to help here. $\endgroup$ Feb 13, 2014 at 16:29
  • $\begingroup$ Maybe this reference could help you, at least in the symmetric case: files.ele-math.com/articles/jmi-04-36.pdf $\endgroup$
    – Paglia
    Feb 13, 2014 at 17:20
  • 3
    $\begingroup$ @TheMaskedAvenger The elementary divisors of a matrix are determined only upto units. Thus, over a field, they offer no new information that determinant does not give. $\endgroup$
    – knsam
    Feb 13, 2014 at 23:37

5 Answers 5

21
$\begingroup$

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))))))
$\endgroup$
1
  • $\begingroup$ There is nothing better than an explicit construction. Thank you. Although it would be great if I could accept the upper and lower bounds answers together. $\endgroup$
    – Simd
    Feb 15, 2014 at 9:23
22
$\begingroup$

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.

$\endgroup$
9
$\begingroup$

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

$\endgroup$
1
  • 3
    $\begingroup$ This bound can be improved slightly if we assume that $A$ is normal. In this case $\text{tr}(A^T A) \le n^2$, and using Lagrange multipliers on this condition together with trying to maximize the product of all but one of the eigenvalues shows that we should take the non-smallest eigenvalues all about equal, so $\lambda_i \approx \sqrt{n}$, which gives us a lower bound of about $\frac{1}{n^{n/2 + O(1)}}$. $\endgroup$ Feb 14, 2014 at 3:10
7
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ So if $n = 2k$ is even we can get small eigenvalue $1 + e^{2 \pi i (k+1)/2k} = 1 - e^{\pi i / k}$ which has absolute value $O \left( \frac{1}{k} \right)$. By comparison, Denis Serre's argument in the linked answer gives $O \left( \frac{1}{k^{O(1) \log k + O(1)}} \right)$, I think. (Really not a fan of constants today.) $\endgroup$ Feb 14, 2014 at 2:33
2
$\begingroup$

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.

$\endgroup$
2
  • 2
    $\begingroup$ $\lambda_{\text{min}}(A)$ is the most negative eigenvalue, not the smallest eigenvalue in absolute value. Note that this bound grows linearly in $n$ but we can clearly get eigenvalues of absolute value $1$ for all $n$ without much difficulty. $\endgroup$ Feb 14, 2014 at 2:03
  • $\begingroup$ Thanks Qiaochu! Yes, it is the algebraically the smallest eigenvalue, not in absolute value. Chasing that paper shows that characterizing the other eigenvalues (even for symmetric matrices) in an open problem. So I should add this caveat in the above answer and reword to correct. $\endgroup$
    – Suvrit
    Feb 14, 2014 at 2:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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