# Square Idempotent matrix: efficient algorithms for finding eigenvectors

Given a square idempotent $N \times N$ matrix $A$ with large $N$, and a priori knowledge of the rank $K$, what is the most efficient way to compute the $K$ eigenvectors corresponding to the $K$ non-zero eigenvalues?

Information:

1. Matrix is idempotent, therefore all eigenvalues are $1$ or $0$.
2. Matrix is not symmetric.
3. $K \ll N$.
4. I'd like to avoid numerical computation of the eigenvalues, as I already know them, i.e., there are $K$ eigenvalues of magnitude $1$ and $N-K$ eigenvalues of magnitude $0$.

If the matrix was symmetric, an eigendecomposition would give $A = Q\Lambda Q^T$, and $Q$ would be $K$ orthonormal columns and $N-K$ zero columns. Since it's not symmetric, I believe this will not be the case, so I'd settle for the closest such matrix.

Context: essentially think of my matrix $A$ as a small perturbation around a symmetric idempotent matrix of the same size. I need the $N \times K$ matrix $B$ which is closest to giving $BB^T = A$. This must be done numerically, so really, the advice that would be ideal is "use LAPACK routine XYZ with parameter ABC to avoid computing the eigenvalues". Unfortunately, I can't seem to find any such routines which don't compute the eigenvalues as part of the process.

As far as I can tell, this has nothing to do with eigenvalues. What you want is the vectors $x$ such that $Ax=x$. That is, you want to solve the system $(A-I)x=0$.
What is the best method for this? That depends on data you are not giving, like $N$ and the kind of entries in the matrix. For small $N$ (maybe a few thousands) one can try row-reduction (Gauss-Jordan) if there are sufficiently many entries removed from zero to keep the size of the pivots bounded. For a bigger matrix the best bet is likely an iterative method, like succesive over-relaxation.
• The reason I talked about eigenvalues is that the majority of decomposition routines that are efficient (LAPACK, etc.) begin by computing the eigenvalues and proceeding from there. You have a good point about stepping back from the problem and just solving $(A-I)x=0$. $N$ can range from $\approx 300$ to $10000$; the entries are not really sparse (by the sparse equals 0s thought process). One thing I'm not sure of: won't the method you mentioned fail, since there are typically $K = 30+$ solutions to $(A-I)x = 0$? I need an orthogonal basis to the eigenspace, not a single vector. – Wesley Burr Mar 19 '14 at 19:50
• (I realized that I should be more clear about "fail" above: by fail I mean that it might end up being more work to run a solver on $(A-I)x = 0$ and then orthogonalize the resulting vectors. I don't have a good sense of how slow or fast such a set of operations will be -- hence the original question.) – Wesley Burr Mar 20 '14 at 3:13
Since the matrix is idempotent $A^2=A$ the eigenvectors corresponding to the eigenvalue $1$ are exactly the elements of the image of the linear transformation described by $A$. Hence you could choose a basis of the column space of $A$ (or row space if you are thinking of rows...) and be done. Alas I do not know if your matrix is small enough for this to be a feasible solution.
• Unfortunately, no. For small $N$ I have a solution which works, but for large $N$ the solution does not scale (finding a SVD is $\mathcal{O}(N^3)$). – Wesley Burr Mar 20 '14 at 17:05