# Eigenvalue decomposition of the sum: $AA^T$ + diag($u$)

Suppose $A\in\mathbb{R}^{n\times c}$,$u\in\mathbb{R}^n$,$n\gg c$. The time complexity of eigenvalue decomposing directly for matrix $AA^T+\text{diag}(u)$ is $O(n^3)$. And it is easy to avoid $O(n^3)$ for matrix $AA^T+I$. So can we avoid $O(n^3)$ for matrix $AA^T+\text{diag}(u)$? Thanks.

Regards.

Jay.

• There are a few earlier related questions here (see linked): scicomp.stackexchange.com/q/503/713 – Kirill Jul 20 '16 at 8:27
• Thanks, it seems that the answer is no. And $AA^T+\text{diag}(u)$ is not diagonally dominant. – Echo Jul 22 '16 at 9:26