Let $A$ be a positive-definite matrix with eigenvalues $e_1, ..., e_n$. I want to compute $\sum\limits_{i=1}^{n} \sqrt{e_i}$ without calculating all eigenvalues first (or rather: with a method faster than calculating all eigenvalues which takes a time of $\mathcal{O}(n^3)$.

The sum of the eigenvalues of a matrix is equal to its trace, i.e. $\sum\limits_{i=1}^{n} e_i = tr(A)$. I could use the Cholesky decomposition of $A = L^T L$. The eigenvalues of $L$ would be $\sqrt{e_i}$, thus $tr(L)$ is the quantity I am looking for, but the cholesky decomposition also has a runtime of $\mathcal{O}(n^3)$.

Is there a faster way to calculate this?

  • $\begingroup$ Do you need absolute accuracy or just reasonably accurate numerical approximation? $\endgroup$
    – Radost
    May 23, 2019 at 10:36
  • $\begingroup$ I would take an approximation, although I was hoping for something absolutely accurate (in theory), so that the only comes from computing. $\endgroup$
    – fxm
    May 23, 2019 at 10:55

1 Answer 1


Observe that $$\sum\limits_{i=1}^{n} \sqrt{e_i} = tr(\sqrt{A})$$ The matrix square root$\sqrt{A}$ can be computed using iterative methods (for example see this), which also require $O(n^3)$ operations. However this can be faster than full eigenvalue decomposition if low accuracy suffices.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .