Average polynomial time for eigenvector computations

Diego Armentano, Carlos Beltrán, Michael Shub

We describe two algorithms for the eigenvalue, eigenvector problem which, on input a Gaussian matrix with complex entries, finish with probability 1 and in average polynomial time.