# Complexity of Finding the Eigendecomposition of a *Symmetric* Matrix

This is a specialized version of a previous question: Complexity of Finding the Eigendecomposition of a Matrix .

For NxN symmetric matrices, it is known that O(N^3) time suffices to compute the eigen decomposition. The question is: can we achieve sub-cubic complexity? Thanks.

• Does this really need a separate question? Surely if someone knew the answer to this special case they would have said so in the other question. – Warren Schudy Nov 18 '10 at 17:11
• I stressed worst-case in my question, so I think this is fair... – Lev Reyzin Nov 18 '10 at 17:55
• Are you sure about that O(N^3) time bound? See my related question about Gaussian elimination. – Jeffε Dec 29 '10 at 21:45
• It seems from mathoverflow.net/questions/24287/… you can get $O(n^3)$ for an approximate solution. – Lev Reyzin Dec 30 '10 at 20:54