I'm probably missing a trivial answer, but somehow I can't find it.

Given symmetric matrix $A \in \mathbb R^{n \times n}$, what's the complexity of diagonalizing the matrix, i.e. finding diagonal $\Lambda = diag(\lambda_1, \ldots, \lambda_n)$ and orthogonal $Q \in \mathbb R^{n \times n}$ such that $$\|A - Q^{-1} \Lambda Q\| < \epsilon \|A\|?$$ Here I use the operator norm. You can assume that the largest eigenvalue of $A$ is bounded by constants from both above and below. You can assume that all eigenvalues are different (it can also be achieved by perturbing $A$).

Basically, I have $f(x) = x^\top A x$, and I need to guarantee that the function doesn't excessively change after diagonalization.

Eigenvalues can be approximated efficiently using e.g. shifted QR algorithm. For the eigenspaces, The complexity of the matrix eigenproblem claims to find them, but I'm confused about what their result is: the main theorem only talks about approximating eigenvalues. What exactly they mean by "associated eigenspaces" is unclear to me: both from the definition point of view (since the eigenvalues are only found approximately, they almost surely don't have the eigenspaces) and from the approximation point of view. Other papers also don't seem to show a concrete answer (again, maybe I misinterpret the results).


1 Answer 1


Reducing to a tridiagonal matrix takes $O(n^3)$ independent of $\epsilon$. I believe the fastest algorithm after that is divide and conquer, which I believe is $O(n^2 \log(1/\epsilon))$, for a total complexity of $O(n^3 + n^2 \log(1/\epsilon))$. However, it’s possible I have the dependence on $\epsilon$ wrong here.


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.