What methods do we have to understand the spectrum of matrices with restricted entries?

Question

Consider questions of the form (or the "most probable value of" version of these questions rather than the "largest possible"),

• What is the largest possible spectral radius of a $n \times n$ matrix with entries in $\{0,1,-1 \}$ ?

• What is the largest possible spectral radius of a $n \times n$ matrix with entries in $\{0,1,-1 \}$ and has $d$ non-zero entries ? (or an "at most d" version of this)

• What is the largest possible spectral radius of a $n \times n$ matrix with entries in $\{0,1,-1 \}$ and which has $d$ non-zero entries in every row and/or column? (or an "at most d" version of this)

---

What methods or techniques we have to answer such things? Any reference would be helpful.

---

One can restrict the matrices to be symmetric if necessary or to have $0$s along the diagonals if necessary. Or feel free to replace the set $\{0,1,-1\}$ by some other finite set if that makes things better.

Answer 1

An easy argument that gives at least asymptotically the correct answer to the second question is obtained by considering the Hilbert-Schmidt norm: $\| A\|_2^2=\sum |a_{jk}|^2 = d$ and also $\|A\|_2^2 = \sum s_j(A)^2$ and $s_1(A)=\|A\|\ge r(A)$. So this shows that $r(A)\le\sqrt{d}$ for a matrix with $d$ non-zero $\pm 1$ entries.

Moreover, if $k^2\le d < (k+1)^2$, then you can get a matrix with $r(A)\ge k$ by putting a $k\times k$ block of $1$'s somewhere (and keeping the matrix symmetric, so that min-max can be used to see that the largest eigenvalue of this matrix is $\ge$ the largest eigenvalue $\lambda=k$ of the block of $1$'s); in fact, a more careful version of this argument produces slightly better bounds.

In general, $r(A)=\sqrt{d}$ is not always possible, though, as you can see from small examples ($d=n=2$).

Answer 2

By Gerschgorin's Circle Theorem, if the number of nonzero entries in each row is at most $d$, the spectral radius is at most $d$. This bound is attained e.g. in a case where there are $d$ $1$'s in each row and no $-1$'s, with eigenvector $(1,\ldots,1)^T$ for eigenvalue $d$.

EDIT: If the matrix has at most $d$ nonzero entries, the spectral radius is at most $ (d+1)/2$. This follows from the following facts:

1. The spectrum is contained in the numerical range, so the spectral radius is at most the numerical radius.
2. The numerical radius is a norm.
3. The numerical radius of a diagonal matrix with entries of $\pm 1$ and $0$ on the diagonal is $1$.
4. The numerical radius of a matrix with a single off-diagonal entry of $\pm 1$ and all else $0$ is $1/2$.

This estimate does not seem to be sharp (except of course if $d=1$).