Does anyone know what the eigenvalue decomposition of a general n x n complex matrix is? By complexity I mean the number of multiplication operations. I know from another question posted on this site that it is in the "order" of n^3 but I need to know how much is it exactly or at least the coefficient of this n^3.

Also I'd appreciate it if this complexity is for the fastest known algorithm as well if possible.


  • $\begingroup$ another place that might have the specifics on the number of operations is scicomp.stackexchange.com $\endgroup$ Mar 29, 2012 at 23:07
  • 1
    $\begingroup$ First, the coefficient isn't even well-defined unless you specify a precise model of computation. (Arithmetic operations? Bit operations? Memory accesses? Something else?) Second, $O(n^3)$ is only an upper bound; there may be faster algorithms based on fast matrix multiplication. $\endgroup$
    – Jeffε
    Mar 30, 2012 at 8:10
  • $\begingroup$ To add to JeffE's comment: if you want arithmetic or bit operations you also should specify the precision with which you want to find the eigenvalues and/or to assume that the eigenvalues lie in the subfield of $\mathbb{C}$ generated over $\mathbb{Q}$ by the entries of the matrix, since in general the eigenvalues will not be exactly computable from the entries of the matrix, even in arithmetic models that allow exact complex arithmetic. $\endgroup$ Mar 30, 2012 at 15:44
  • $\begingroup$ Adding to the previous comments: the sparsity of the matrix another important factor. $\endgroup$
    – Dimitris
    Mar 30, 2012 at 21:51
  • 1
    $\begingroup$ Eigenvalues can be non-algebraic even for matrices of integers that are sparse. This shouldn't be surprising in light of Galois theory for polynomial roots - the eigenvalues of a matrix are the zeros of it's characteristic polynomial, and the zeros of any polynomial are the eigenvalues of it's companion matrix. So, it is not even possible to compute exact eigenvalues. You will have to talk about convergence rates of iterative methods. Even there, the rate will usually depend on the condition number of the matrix which can be arbitrarily large. $\endgroup$
    – Nick Alger
    Apr 11, 2012 at 8:05


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.