# What is the largest possible operator norm of a sparse (0,1)-matrix?

Inspired by this question, I was wondering about the following problem:

Consider all $n\times n$ $(0,1)$-matrices with $k$ ones. Which of these matrices has the largest operator norm? And how does this largest possible operator norm behave with $n$ and $k$?

If any progress has already been made on this problem, I assume it's in the guise of directed graphs. For the case of symmetric matrices with zero diagonal, which graphs give the largest possible largest eigenvalue? $(k/n)$-regular graphs?

-
Sure, Survit. That is the Hilbert-Schmidt, which dominates the operator norm, and the norms are the same for rank one operators. More generally, $k^{1/2}$ is the right answer for all $k \le n$ for the same reason--put all the ones in one column. I guess when $n^2 \ge k > n$ you get the max when you fill up as many columns as possible with ones and put the left over ones into one column. –  Bill Johnson Jun 3 '13 at 18:42
@Bill: Yes, I realized that my question was obvious, which is why I deleted my comment a few seconds after posting it :-) -- suVRit –  Suvrit Jun 3 '13 at 21:03

If $k=ab$ with $a\leq n$ and $b\leq n$, then an $a \times b$ rectangle of $1$s surrounded by $0$s hits the optimal matrix norm of $\sqrt{k}$. Otherwise, $\sqrt{k}$ is not achievable, but it's clear that one can get very close to $\sqrt{k}$ with very close to a rectangle.
A $k/n$-regular graph has a largest eigenvalue of $k/n$ which is not that great. A better thing to do is a complete graph on about $\sqrt{k}$ vertices plus $n-\sqrt{k}$ isolated vertices, which gives a largest eigenvalue of about $\sqrt{k}$.