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.

  • 1
    You may find this blog post relevant: http://qchu.wordpress.com/2009/04/30/the-spectral-radius-of-a-simple-graph/2012-09-29
  • 0
    Also try [link](http://mathoverflow.net/questions/104072/upper-bound-for-largest-eigenvalue-of-0-1-matrix)2012-09-29
  • 0
    @PatrickLi thanks, that's useful. Brad: couldn't find exactly an answer there.2012-09-29
  • 0
    You should symmetrise $A \mapsto (A+A')/2$ to get adjacency matrices...2012-11-07

1 Answers 1