Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
2  
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

1 Answer 1

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

share|improve this answer

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.