Skip to main content
2 of 2
added 188 characters in body
Christian Remling
  • 24.2k
  • 2
  • 48
  • 83

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

Christian Remling
  • 24.2k
  • 2
  • 48
  • 83