Maximize the spectral norm of a correlation matrix by scrambling its off-diagonal elements I want to construct an $n\times n$ correlation matrix with exactly $m(m+1)$ off-diagonal elements equal to some $r>0$ and all other off-diagonal elements are zero. How to arrange those $r$s such that the spectral norm is maximized?
Based on my hunch and the intuition conveyed from experiments, in the maximizing arrangement probably all $r$s reside in a principal $(m+1)\times(m+1)$ submatrix.
 A: An upper bound on the spectral norm, based on Schur's inequality:  
Given a symmetric $n\times n$ matrix $M$ with 1's on the diagonal and $m(m+1)$ entries equal to $r$, define $M' = M - I_n$, where $I_n$ is the $n \times n$ identity matrix.  $M'$ has $m(m+1)$ entries that are equal to $r$, with the rest equal to zero.  Moreover, the eigenvectors of $M'$ are the same as those of $M$, and the corresponding eigenvalues of $M'$ are the eigenvalues of $M$ minus 1:  $\lambda'_i = \lambda_i - 1$.
Now, Schur's inequality states that the sum of the absolute squares of the eigenvalues is bounded by
$$
\sum_{i = 1}^n |\lambda'_i|^2 \leq \sum_{i,j=1}^n |M'_{ij}|^2 = m(m+1)r^2.
$$
But since all the absolute squares of the eigenvalues are non-negative, it follows that any one eigenvalue must satisfy
$$
|\lambda'_i| = |\lambda_i - 1| \leq \sqrt{m(m+1)} r,
$$
and thus all the eigenvalues of $M$ are less than $1 + \sqrt{m(m+1)} r$.  
This is not significantly larger than the eigenvalue of $1 + mr$ which is obtained by the block-diagonal prescription described in your question;  for large value of $m$, the upper bound and the lower bound both grow approximately linearly in $m$. 

[Note:  I first posted this answer to the same question when it was posted on another (non-SE) message board, but figured I'd port it over here to see if anyone could improve on it.]
