3
$\begingroup$

I would like to find the largest eigenvalue of an $n \times n$ binary matrix of density $p$, i.e., with $p n^{2}$ ones and $(1-p) n^{2}$ zeros. Any idea or reference is welcome.

Improve this question
$\endgroup$
4
  • $\begingroup$ If you're interested in the regime where $p$ is fixed and $n$ goes to infinity, you may want to look at Silverstein's "The spectral radii and norms of large dimensional non-central random matrices". It's not quite the same as your model (he looks at matrices where each entry is independently $1$ with some probability $p$), but there should be some sort of coupling argument relating the two. $\endgroup$
    – Kevin P. Costello
    Commented Oct 6, 2017 at 19:22
  • 1
    $\begingroup$ It's a $0-1$ matrix, so Perron-Frobenius applies -- the spectral radius is attained by a positive real eigenvalue. $\endgroup$
    – Kevin P. Costello
    Commented Oct 8, 2017 at 4:08
  • 1
    $\begingroup$ Hi, the matrix is not given. my question was about the largest possible spectral radius of binary matrix. i am in fact also interested in the expectation and distribution of spectral radius where the density of binary matrix is given and the size n tends to infinity. $\endgroup$
    – SC_thesard
    Commented Oct 9, 2017 at 19:31
  • $\begingroup$ Silverstein's article looks in deed helpful. while i did not find a direct conclusion of my question. i may need time to study it as i am not specialized in mathematics or linear algebra. Thanks $\endgroup$
    – SC_thesard
    Commented Oct 9, 2017 at 19:33

1 Answer 1

Reset to default
1
$\begingroup$

Suppose the desired number of $1$'s is $m^2+r<(m+1)^2.$ So $m=\lfloor n\sqrt{p}\rfloor.$ Then an eigenvalue of $m$ is achieved by putting $1$'s in the leftmost $m$ positions of the top $m$ rows and the rest wherever. The eigen-vector is the transpose of the first row (which is the same as the following $m-1$ rows. This seems optimal or close to it.

Here is an argument which is not rigorous, but perhaps could be made so:

Let $m$ be the most $1$'s in any row of the matrix $A$ (which we can assume is row $1$) and $u_1=1$ the largest entry (in magnitude) of some eigenvector $\mathbf{u}$ with $A\mathbf{u}=\lambda \mathbf{u}.$ We see that $\lambda u_1=\lambda$ is the sum of some $u_i,$ at most $m$ of them, and none of larger magnitude than $1.$ This means that $|\lambda| \leq m$ and to get $\lambda=m$ would require that the entries summed are all also $1.$ But, for an eigenvector, that would require that the corresponding $m$ rows of the matrix also each had $m$ $1$'s.

Improve this answer
$\endgroup$
1

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .