3
$\begingroup$

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.

  • 0
    You should symmetrise $A \mapsto (A+A')/2$ to get adjacency matrices...2012-11-07

1 Answers 1

4

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