# Eigenvectors of a matrix reduced to tridiagonal

I am implementing an algorithm to calculate eigenvalues and eigenvectors of a symmetric matrix in a GPU. In order to calculate the eigenvalues I first reduced the matrix to the tridiagonal form using Householder transformations. Now I want to use those eigenvalues to calculate the corresponding eigenvectors through inverse iteration.

I was reading about inverse iteration here and I noticed that in step 4 I must invert a matrix or, alternatively, solve a set of linear equations:

As noted here this is much easier to do with tridiagonal matrices. I already have the reduction, but its eigenvectors are not the same of the original matrix. So my question is, what do I have to do to get the eigenvectors of the original matrix?

-

If you first decomposed your matrix $\mathbf A$ as

$$\mathbf A=\mathbf P\mathbf T\mathbf P^\top$$

where $\mathbf P$ is orthogonal and $\mathbf T$ is tridiagonal, and afterwards you managed to find a (partial) eigendecomposition of $\mathbf T$ as

$$\mathbf T=\mathbf Q\mathbf \Lambda\mathbf Q^\top$$

where $\mathbf Q$ is the orthonormal matrix of eigenvectors and $\mathbf \Lambda$ is diagonal, then $\mathbf A$ has the eigendecomposition

$$\mathbf A=(\mathbf P\mathbf Q)\mathbf \Lambda(\mathbf P\mathbf Q)^\top$$

Put another way, if you have a vector $\mathbf v$ and a scalar $\lambda$ satisfying

$$\mathbf T\mathbf v=\lambda\mathbf v$$

then

\begin{align*}(\mathbf P^\top\mathbf A\mathbf P)\mathbf v&=\lambda\mathbf v\\\mathbf P^\top\mathbf A\mathbf P\mathbf v&=\lambda\mathbf v\\\mathbf A\cdot(\mathbf P\mathbf v)&=\lambda(\mathbf P\mathbf v)\end{align*}

In short, you need to multiply the eigenvectors of your tridiagonal matrix $\mathbf T$ with the orthogonal matrix $\mathbf P$ you obtained from the tridiagonal decomposition of $\mathbf A$ to obtain eigenvectors of $\mathbf A$.

If you'll indulge me a tiny aside: at least for getting a few eigenvectors of a symmetric matrix, one can do better than inverse iteration by using a method that is, well, a carefully modified inverse iteration. Try searching for "MRRR algorithm" in your favorite search engine for details.

-
Thank you for the for the suggestion. I'll do some research. – nmat Oct 14 '11 at 22:09