<p>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.</p>

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

<p>Thanks.</p>

CC BY-SA 3.0
2012-03-29T23:07:07.287Z
another place that might have the specifics on the number of operations is scicomp.stackexchange.com
Suresh Venkat
CC BY-SA 3.0
2012-03-30T08:10:43.577Z
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](http://mathoverflow.net/questions/24287/what-is-the-best-algorithm-to-find-the-smallest-nonzero-eigenvalue-of-a-symmetric/24294#24294) [algorithms](http://cstheory.stackexchange.com/a/2810/111) based on fast matrix multiplication.
Jeffε
CC BY-SA 3.0
2012-03-30T15:44:59.787Z
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
CC BY-SA 3.0
2012-03-30T21:51:25.817Z
Adding to the previous comments: the sparsity of the matrix another important factor.
Dimitris
CC BY-SA 3.0
2012-04-11T08:05:42.100Z
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
<cc.complexity-theory><complexity-classes><time-complexity>
"Exact" (not just the order) computational complexity of eigenvalue decomposition
Ahmed Ali
# "Exact" (not just the order) computational complexity of eigenvalue decomposition

(Asked by: username_0 on 2012-03-29)

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.

**Tags:** cc.complexity-theory, complexity-classes, time-complexity
> **Comments:**
> **username_1**: another place that might have the specifics on the number of operations is scicomp.stackexchange.com  
> **username_2**: 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](http://mathoverflow.net/questions/24287/what-is-the-best-algorithm-to-find-the-smallest-nonzero-eigenvalue-of-a-symmetric/24294#24294) [algorithms](http://cstheory.stackexchange.com/a/2810/111) based on fast matrix multiplication.  
> **username_3**: 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.  
> **username_4**: Adding to the previous comments: the sparsity of the matrix another important factor.  
> **username_5**: 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.  

---

## 0 answers

