1

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.

Thanks.

Ahmed Ali
  • 11
  • 1
  • another place that might have the specifics on the number of operations is scicomp.stackexchange.com – Suresh Venkat Mar 29 '12 at 23:07
  • 1
    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. – Jeffε Mar 30 '12 at 08:10
  • 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. – Joshua Grochow Mar 30 '12 at 15:44
  • Adding to the previous comments: the sparsity of the matrix another important factor. – Dimitris Mar 30 '12 at 21:51
  • 1
    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. – Nick Alger Apr 11 '12 at 08:05

0 Answers0