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.

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

2 Answers 2


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.


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.