13
$\begingroup$

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?

Improve this question
$\endgroup$
2
  • 5
    $\begingroup$ Nice question! For comparison, the best known running time for computing the eigenvalues themselves (upto additive error 1/4) is $O(n^3)$ (cstheory.stackexchange.com/a/2810/15) $\endgroup$
    – arnab
    Commented Mar 7, 2013 at 23:14
  • $\begingroup$ 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. $\endgroup$
    – Dimitris
    Commented Mar 8, 2013 at 17:35

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.