13

Let $A$ be the $n\times n$ adjacency matrix of a (non-bipartite) graph. Assume that we are given the amplitudes of its eigenvalues, i.e., $|\lambda_1|=a_1,\ldots, |\lambda_n|=a_n$, and we would like to calculate their signs. Is there a faster way of computing the signs of these eigenvalues, other than recomputing the eigenvalues themselves?

Community
  • 1
Dimitris
  • 1,356
  • 6
  • 16
  • 5
    Nice question! For comparison, the best known running time for computing the eigenvalues themselves (upto additive error 1/4) is $O(n^3)$ (http://cstheory.stackexchange.com/a/2810/15) – arnab Mar 07 '13 at 23:14
  • Thanks, that's exactly the point. I was wondering if the knowledge of the amplitudes made the problem any simpler. I think that this could have interesting implications in problems where eigenvalues are well approximated by the squared degrees of the graph, etc. – Dimitris Mar 08 '13 at 17:35

0 Answers0