Given a real $n\times n$ matrix $A$, one can find the eigenvalues in $O\left(n^3\right)$ by using say, the $QR$ algorithm.
Now, what if we guess an eigenvalue $\lambda_0$, and we want to know if it's actually an eigenvalue of the matrix $A$? Intuitively, this should be significantly faster than actually finding all of the eigenvalues. We can of course check if $\lambda_0$ is actually an eigenvalue by calculating $\det(A-\lambda_0 I)$, but calculating the determinant is also $O\left(n^3\right)$.
Is there a faster than $O\left(n^3\right)$ method for testing the "eigenvaluedness" of a specific number $\lambda_0$, without solving for the rest of the $\lambda_i$'s? Can one prove there isn't?
Does it help if $A$ is orthogonal, symmetric or has other special (non triangular) form?
Bounty goes to whoever shows either of the following:
- A method of checking a possible eigenvalue in less than $O(n^3)$.
- A proof or sufficiently convincing heuristic argument that no such method exists.