# is there a way to find or upper bound the largest eigenvalue of the following matrix?

I have a matrix $A \in \{0,1\}^{n \times n}$ -- i.e. a matrix with 1s and 0s only.

Is there a way to find or upper bound its largest eigenvalue?

I have a feeling it is related to connectivity of directed graphs, if $A$ is thought of as adjacency matrix.

Also, when trying

      A = rand(10,10); A = A <= p; [x,S] = eig(A+0.00); S(1,1)


in Matlab for various values of p (0.1,0.2,...) (many times) it seems like S(1,1), the largest eigenvalue, is around 1/p.

Any help is appreciated.

-
You may find this blog post relevant: qchu.wordpress.com/2009/04/30/… – Brad Sep 29 '12 at 16:06
Also try link – Patrick Li Sep 29 '12 at 16:07
@PatrickLi thanks, that's useful. Brad: couldn't find exactly an answer there. – kloop Sep 29 '12 at 16:39
You should symmetrise $A \mapsto (A+A')/2$ to get adjacency matrices... – draks ... Nov 7 '12 at 21:14

The largest eigenvalue of the adjacency matrix of a graph is bound by $$\delta(A)\le\mu_{\text{max}}(A)\le\Delta(A),$$ with $\delta$($\Delta$) being the smallest(largest) vertex degree in your graph. A proof can be found here(Lemma 3). In your case $\delta$($\Delta$) lie around $\frac1p$.