Skip to main content
added 629 characters in body
Source Link
Robert Israel
  • 54.2k
  • 1
  • 76
  • 152

By Gerschgorin's Circle Theorem, if the number of nonzero entries in each row is at most $d$, the spectral radius is at most $d$. This bound is attained e.g. in a case where there are $d$ $1$'s in each row and no $-1$'s, with eigenvector $(1,\ldots,1)^T$ for eigenvalue $d$.

EDIT: If the matrix has at most $d$ nonzero entries, the spectral radius is at most $ (d+1)/2$. This follows from the following facts:

  1. The spectrum is contained in the numerical range, so the spectral radius is at most the numerical radius.
  2. The numerical radius is a norm.
  3. The numerical radius of a diagonal matrix with entries of $\pm 1$ and $0$ on the diagonal is $1$.
  4. The numerical radius of a matrix with a single off-diagonal entry of $\pm 1$ and all else $0$ is $1/2$.

This estimate does not seem to be sharp (except of course if $d=1$).

By Gerschgorin's Circle Theorem, if the number of nonzero entries in each row is at most $d$, the spectral radius is at most $d$. This bound is attained e.g. in a case where there are $d$ $1$'s in each row and no $-1$'s, with eigenvector $(1,\ldots,1)^T$ for eigenvalue $d$.

By Gerschgorin's Circle Theorem, if the number of nonzero entries in each row is at most $d$, the spectral radius is at most $d$. This bound is attained e.g. in a case where there are $d$ $1$'s in each row and no $-1$'s, with eigenvector $(1,\ldots,1)^T$ for eigenvalue $d$.

EDIT: If the matrix has at most $d$ nonzero entries, the spectral radius is at most $ (d+1)/2$. This follows from the following facts:

  1. The spectrum is contained in the numerical range, so the spectral radius is at most the numerical radius.
  2. The numerical radius is a norm.
  3. The numerical radius of a diagonal matrix with entries of $\pm 1$ and $0$ on the diagonal is $1$.
  4. The numerical radius of a matrix with a single off-diagonal entry of $\pm 1$ and all else $0$ is $1/2$.

This estimate does not seem to be sharp (except of course if $d=1$).

added 25 characters in body
Source Link
Robert Israel
  • 54.2k
  • 1
  • 76
  • 152

By Gerschgorin's theoremGerschgorin's Circle Theorem, if the number of nonzero entries in each row is at most $d$, the spectral radius is at most $d$. This bound is attained e.g. in a case where there are $d$ $1$'s in each row and no $-1$'s, with eigenvector $(1,\ldots,1)^T$ for eigenvalue $d$.

By Gerschgorin's theorem, if the number of nonzero entries in each row is at most $d$, the spectral radius is at most $d$. This bound is attained e.g. in a case where there are $d$ $1$'s in each row and no $-1$'s, with eigenvector $(1,\ldots,1)^T$ for eigenvalue $d$.

By Gerschgorin's Circle Theorem, if the number of nonzero entries in each row is at most $d$, the spectral radius is at most $d$. This bound is attained e.g. in a case where there are $d$ $1$'s in each row and no $-1$'s, with eigenvector $(1,\ldots,1)^T$ for eigenvalue $d$.

Source Link
Robert Israel
  • 54.2k
  • 1
  • 76
  • 152

By Gerschgorin's theorem, if the number of nonzero entries in each row is at most $d$, the spectral radius is at most $d$. This bound is attained e.g. in a case where there are $d$ $1$'s in each row and no $-1$'s, with eigenvector $(1,\ldots,1)^T$ for eigenvalue $d$.