<p>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? </p>

CC BY-SA 3.0
2013-03-07T23:14:16.657Z
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
CC BY-SA 3.0
2013-03-08T17:35:45.357Z
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
<cc.complexity-theory><ds.algorithms><linear-algebra><spectral-graph-theory>
Complexity to compute the eigenvalue signs of the adjacency matrix
Dimitris
# Complexity to compute the eigenvalue signs of the adjacency matrix

(Asked by: username_0 on 2013-03-07)

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?

**Tags:** cc.complexity-theory, ds.algorithms, linear-algebra, spectral-graph-theory
> **Comments:**
> **username_1**: 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)  
> **username_0**: 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.  

---

## 0 answers

