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.
$\begingroup$
$\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. CostelloOct 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. CostelloOct 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_thesardOct 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_thesardOct 9, 2017 at 19:33
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
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.
answered Oct 7, 2017 at 10:39
-
2$\begingroup$ Some is proved at sciencedirect.com/science/article/pii/0024379585900680 and probably more is proved in articles citing that one. $\endgroup$ Oct 7, 2017 at 11:14