Eigenvalue test faster than $O\left(n^3\right)$?

Solution 1:

The first algorithm computing the determinant faster than in $O(n^{3})$ time (his algorithm worked in $O(n^{\ln 7/\ln 2})$ time) was given by Volker Strassen in this classical paper. Therefore, $O(n^{\ln 7/\ln 2})$ time suffices to check whether a given number is an eigenvalue or not. In fact, the problem of computing the determinant has asymptotically the same complexity as the problem of multiplying two $n\times n$ matrices, for which $O(n^{2+\varepsilon})$ compleixty is conjectured. Some information and references on this are contained in the link provided by xavierm02 in his comment.

Solution 2:

Of course, the Strassen algorithm computes the determinant in $O(n^{2.807})$ ; moreover it is the sole algorithm that, in practice, does the job faster than in $O(n^3)$ - when $n\geq 2048$ - (to fix ideas) (then, let $\omega=2.807$ if $n\geq 2048$, otherwise $\omega=3$.). Yet, that is not really the question here. Indeed the calculation of $spectrum(A)$ and the calculation of $\det(A)$ (or of the square $A^2$) are all in $O(n^{\omega})$, under the condition that we seek some approximation of the true values. So the good question would be:

We consider the following problem : Let $A\in M_n(\mathbb{C}),\lambda_0\in \mathbb{C},r\in \mathbb{N}$ ; does there exist an eigenvalue $\lambda$ of $A$ s.t. $|\lambda-\lambda_0|<10^{-r}$ ? Its complexity is $\sim kn^{\omega}$. What is the value of $k$ ?

We consider the following experiment (with Maple): $A\in M_{10}(\mathbb{Z})$ is randomly chosen ($a_{i,j}\in[-99,99])$. $A$ admits an eigenvalue $\lambda\approx -166-15i$ and $\lambda_0$ is constructed with the first $15$ significant digits of $Re(\lambda)$ and $Im(\lambda)$. If $r=12$, then the answer to our problem is YES. Unfortunately $\det(A-\lambda_0 I))\approx 1.7\times 10^7-3.7\times10^7i$. Finally, it does not suffice to calculate the previous determinant. We must also consider the derivative in $\lambda_0$ of the function $\phi:t\rightarrow \det(A-tI)$.

EDIT: More precisely, $\phi(\lambda_0)\approx(\lambda_0-\lambda)\phi'(\lambda_0)$ and, consequently, $|\lambda-\lambda_0|\approx\rho=\dfrac{|\det(A-\lambda_0I)|}{|trace(adj(A-\lambda_0I))|}=\dfrac{1}{|trace((A-\lambda_0I)^{-1})|}$ (if $\lambda_0\not=\lambda$). For the previous instance, we find $|\lambda-\lambda_0|\approx 6\times 10^{-13}$. The complexity of the calculation of $\rho$ , by $LU$ method, is $\sim n^3$ (that is $k=1$). Note that the complexity of one decomposition QR is $\sim\dfrac{4}{3}n^3$.

Solution 3:

It is not necessary to actually calculate the determinant, only to confirm whether it's zero.

As such, it suffices to attempt a matrix inversion for $\mathbf{A}-\lambda\mathbf{I}$... if it fails, then the determinant is zero, and therefore we have confirmed $\lambda$ to be an eigenvalue.

It can be shown that, through a divide-and-conquer approach, matrix inversion has the same complexity as matrix multiplication. And because Williams algorithm exists with $O(n^{2.3727})$, this is also an achievable complexity for confirmation of an eigenvalue (up to a certain numerical accuracy, of course).