# Complexity to compute the eigenvalue signs of the adjacency matrix

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?

• 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) – arnab Mar 7 '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 8 '13 at 17:35