1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Wesley Burr Mar 19 '14 at 19:50
  • $\begingroup$ (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.) $\endgroup$ – Wesley Burr Mar 20 '14 at 3:13
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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)$). $\endgroup$ – Wesley Burr Mar 20 '14 at 17:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.