Eigenvalues of n x n 0-1 matrix with at most k ones

I have a $n \times n$ real-valued symmetric matrix $A$ with only zeros and ones as its entries ($A$ can be thought of as the adjacency matrix of a graph), such that the diagonal entries are zeros and there are at most $k$ ones ($k$ even) among the non-diagonal entries (i.e., the graph has at most $k/2$ edges). Are there results about the eigenvalues (or lower and upper bounds on them) of such a matrix? I am especially interested in bounds on the largest and second largest eigenvalues.

-
If there are k/2 ones in a single row, then the operator norm is going to be as large as $\sqrt{k/2}$ (and one can check that the largest eigenvalue will also be of this magnitude). Similarly, if the matrix has a block with k/4 ones and another block with k/4 ones, one should get two large eigenvalues of order at least $\sqrt{k/4}$. On the other hand, the Frobenius norm (the root mean square of the eigenvalues) is $k$, suggesting that such bounds are basically optimal without some additional hypotheses on the matrix. –  Terry Tao Feb 6 at 17:05
add comment