1
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ Are the eigenvalues and/or eigenvectors given as part of the input? $\endgroup$
    – D.W.
    May 5 '20 at 5:32
  • $\begingroup$ @D.W. Good point. No, these are not given. $\endgroup$
    – Boby
    May 5 '20 at 13:50
  • 1
    $\begingroup$ I would think that the natural first question would be what if there are $n-1$ equal eigenvalues and one more that's different. What's the motivation for your question? What's the context in which you encountered it? $\endgroup$
    – D.W.
    May 5 '20 at 17:28
  • $\begingroup$ What can we assume about the three eigenvalues $\lambda_1,\lambda_2,\lambda_3$? Can we assume that $|\lambda_1/\lambda_2|$ and $|\lambda_2/\lambda_3$ are not too small? Perhaps your particular application domain will imply some additional properties that can be useful here. $\endgroup$
    – D.W.
    May 5 '20 at 17:51
  • $\begingroup$ @D.W. I don't have any applications. I was thinking about the complexity of inversion and started thinking about matrices with equal eigenvalues. I was thinking for $n-1$ but then I decided to it for $n-2$. I forget why now. Feel free to answer it for $n-1$. I would prefer to assume nonthing about eigenvalues. But if you have to make some minimal assumptions, please go ahead. My main goal is just to get some intuition of this restriction reduced computation. $\endgroup$
    – Boby
    May 5 '20 at 19:23
1
$\begingroup$

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| > |\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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.