# 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. Nov 18 '10 at 17:11
• I stressed worst-case in my question, so I think this is fair... Nov 18 '10 at 17:55
• Are you sure about that O(N^3) time bound? See my related question about Gaussian elimination. Dec 29 '10 at 21:45
• It seems from mathoverflow.net/questions/24287/… you can get $O(n^3)$ for an approximate solution. Dec 30 '10 at 20:54

## 2 Answers

I know this is a really old question, but it seems like this recent paper https://arxiv.org/abs/1912.08805 improves the runtime to $$O(n^\omega)$$, down from $$O(n^3)$$.

As I see it, this special case is not easier than the general case. Purely symbolically, you can reduce the problem of finding the singular-value decomposition (SVD) to the problem of diagonalizing a symmetric matrix. One can read off the SVD of M from the eigenvectors and eigenvalues of M* M. Note that the reduction involves only a matrix multiplication to compute M* M. It does not seem that there should be any serious numerical issues.