Skip to main content
added 188 characters in body
Source Link
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$ and $n$ is large enough, then you can get a matrix with $r=k$$r(A)\ge k$ by putting a $k\times k$ block of $1$'s somewhere (and decoupling the rest ofkeeping the matrix fromsymmetric, 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$).

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$ and $n$ is large enough, then you can get $r=k$ by putting a $k\times k$ block of $1$'s somewhere (and decoupling the rest of the matrix from this).

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

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

Source Link
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$ and $n$ is large enough, then you can get $r=k$ by putting a $k\times k$ block of $1$'s somewhere (and decoupling the rest of the matrix from this).

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