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

Question

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.

Answer 1

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