<p>Reducing to a tridiagonal matrix takes <span class="math-container">$O(n^3)$</span> independent of <span class="math-container">$\epsilon$</span>.  I believe the fastest algorithm after that is <a href="https://en.m.wikipedia.org/wiki/Divide-and-conquer_eigenvalue_algorithm" rel="nofollow noreferrer">divide and conquer</a>, which I believe is <span class="math-container">$O(n^2 \log(1/\epsilon))$</span>, for a total complexity of <span class="math-container">$O(n^3 + n^2 \log(1/\epsilon))$</span>.  However, it’s possible I have the dependence on <span class="math-container">$\epsilon$</span> wrong here.</p>

CC BY-SA 4.0
2022-05-07T11:57:41.733Z
2022-05-07T11:57:41.733Z
Geoffrey Irving
<p>I'm probably missing a trivial answer, but somehow I can't find it.</p>
<p>Given symmetric matrix <span class="math-container">$A \in \mathbb R^{n \times n}$</span>, what's the complexity of diagonalizing the matrix, i.e. finding diagonal <span class="math-container">$\Lambda = diag(\lambda_1, \ldots, \lambda_n)$</span> and orthogonal <span class="math-container">$Q \in \mathbb R^{n \times n}$</span> such that
<span class="math-container">$$\|A - Q^{-1} \Lambda Q\| &lt; \epsilon \|A\|?$$</span>
Here I use the operator norm.
You can assume that the largest eigenvalue of <span class="math-container">$A$</span> is bounded by constants from both above and below.
You can assume that all eigenvalues are different (it can also be achieved by perturbing <span class="math-container">$A$</span>).</p>
<p>Basically, I have <span class="math-container">$f(x) = x^\top A x$</span>, and I need to guarantee that the function doesn't excessively change after diagonalization.</p>
<p>Eigenvalues can be approximated efficiently using e.g. shifted QR algorithm.
For the eigenspaces, <a href="https://dl.acm.org/doi/pdf/10.1145/301250.301389" rel="nofollow noreferrer">The complexity of the matrix eigenproblem</a> 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 &quot;associated eigenspaces&quot; 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).</p>

<linear-algebra><algebraic-complexity>
Complexity of matrix diagonalization
Dmitry
# Complexity of matrix diagonalization

(Asked by: username_0 on 2022-05-05)

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](https://dl.acm.org/doi/pdf/10.1145/301250.301389) 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).

**Tags:** linear-algebra, algebraic-complexity


---

## 1 answers

### Answer by username_1 on 2022-05-07. Score: 1 | Accepted answer

Reducing to a tridiagonal matrix takes $O(n^3)$ independent of $\epsilon$. I believe the fastest algorithm after that is [divide and conquer](https://en.m.wikipedia.org/wiki/Divide-and-conquer_eigenvalue_algorithm), 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.


---

