7
$\begingroup$

Consider questions of the form (or the "most probable value of" version of these questions rather than the "largest possible"),

  • What is the largest possible spectral radius of a $n \times n$ matrix with entries in $\{0,1,-1 \}$ ?

  • What is the largest possible spectral radius of a $n \times n$ matrix with entries in $\{0,1,-1 \}$ and has $d$ non-zero entries ? (or an "at most d" version of this)

  • What is the largest possible spectral radius of a $n \times n$ matrix with entries in $\{0,1,-1 \}$ and which has $d$ non-zero entries in every row and/or column? (or an "at most d" version of this)


What methods or techniques we have to answer such things? Any reference would be helpful.


One can restrict the matrices to be symmetric if necessary or to have $0$s along the diagonals if necessary. Or feel free to replace the set $\{0,1,-1\}$ by some other finite set if that makes things better.

$\endgroup$
2
  • 1
    $\begingroup$ The matrix with all $1$'s has spectral radius $r=n$, and this is obviously largest possible (normalize the eigenvector so that its largest entry is $1$). $\endgroup$ May 21, 2015 at 23:00
  • $\begingroup$ Yeah. The first question is trivial. Should have noticed that. Though even in the first question the "most probable value of" version is not obvious to me. $\endgroup$
    – user6818
    May 21, 2015 at 23:02

2 Answers 2

3
$\begingroup$

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

$\endgroup$
0
2
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ This applies only when the entries are restricted to be from the set $\{ 0,1,-1\}$? (And is there a column version of this? Or restriction to symmetric ? Or with 0 on the diagonal version of this?) $\endgroup$
    – user6818
    May 21, 2015 at 23:51
  • $\begingroup$ Yes, this is with entries from $\{0,1,-1\}$. Since $M$ and $M^T$ have the same spectrum, it's true for columns as well. $\endgroup$ May 21, 2015 at 23:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.