Complexity of eigenvalue problem

Many matrix diagonalization algorithms have time complexity $\mathcal{O}(n^3)$ where $n$ is the number of columns/raws (consider only square matrices).

What is the best time lower bound it is known?

Another question is whether the decision version of this eigenvalue problem is known to be in $L$.

• Yes, because of the adversary argument (you need to read the whole input), so it is $\Omega(n)$. I would suggest changing the question so it asks for the best time lower bound that is known. – Kaveh Jun 27 '15 at 9:24