# What is the space complexity of computing the eigenvectors of a matrix?

By the answer to this question, computing the eigenvalues of a matrix to within $2^{-n}$ precision can be done in polylogarithmic space. Is it also possible to compute the eigenvectors of a matrix to within precision $2^{-n}$ in polylogarithmic space?

We can try to find the eigenvectors from the eigenvalues, but since we only have the eigenvalues up to precision $2^{-n}$, this seems to lead to a host of numerical stability issues (in particular, if there are two nearby eigenvalues, small perturbations in the matrix can lead to large perturbations in the eigenvectors).

Any references are appreciated!

• I guess, analogously to the answer you are referring to, you assume a write-only, one-way tape for the output? – Sasho Nikolov May 14 '15 at 23:40
• Yes (along with a read-only input tape and a read-write work tape of polylog(n) size). – jschnei May 15 '15 at 0:08