Complexity of Matrix Inversion when $n-2$ Eigenvalues are the same Suppose we have a symmetric matrix $A \in \mathbb{R}^{n \times n}$ that has $n-2$ equal eigenvalues and the other two are distinct.  

Question: What would be the complexity of its inversion?

On the one hand, if all eigenvalues are the same, then the matrix is equal to $aI$. Therefore, the inversion is $O(n)$.

On the other hand, if we can't assume anything than the inversion is $n^{2+\epsilon}$ where $\epsilon \approx 0.37$. 

Note: Eigenvalues and eigenvectors are not given.
If the matrix has two distinct eigenvalues, you can find them using power iteration.

Let $\lambda_1,\lambda_2$ be the 2 eigenvalues, where $|\lambda_1| &gt; |\lambda_2|$.  Then you can use power iteration to find $\lambda_1$.  Next, set $A' = A - \lambda_1 \text{Id}$.  $A'$ is a symmetric matrix with eigenvalues $\lambda_2,0$, so power iteration on $A'$ reveals $\lambda_2$.

The running time depends on the exact values of $\lambda_1,\lambda_2$; power iteration converges geometrically with ratio $|\lambda_2|/|\lambda_1$, so if $|\lambda_2$ is sufficiently smaller than $|\lambda_1$, you can obtain a very precise estimate with a fairly small number of iterations; if they are very close, power iteration will be ineffective.

I don't know how to generalize this handle a matrix with three distinct eigenvalues.