Take the 2-minute tour ×

I'm curious if there's any numerical way of directly finding the eigenvectors with eigenvalue 0.

If I didn't have to do it directly, I would probably do it like this in pseudocode:

A // a rank deficient n*n square matrix

A := [A' I] //augment transpose of A with identity matrix of same size so A is n*2n

Q R := qr(A) //QR factorization on A returns Q and R matrix

return Q(n+1) ... Q(2n) // where Q(i) is the i-th column

And the Q(i) column vectors that exceed a certain numerical threshold would be taken to be in the nullspace of $A$ which would be equivalent to the eigenvectors with eigenvalue 0.

I've thought of the inverse power method but it won't work as far as I can tell.

So, is there a way to find such eigenvalues "directly"? (directly in the numerical sense that I don't have to find vectors not in the space spanned by those eigenvalues to get there)

ETA: My original question is more general, but I was mostly thinking of graph Laplacian matrices when I asked this. So given a symmetrix adjacency matrix $W$ and a degree matrix $D = \textrm{diag}(W \mathbf{1})$ where $\mathbf{1}$ is a column vector of ones, the graph Laplacian is defined as $$ \mathcal{L} = D - W $$ It doesn't take much effort to show that $\mathbf{1}$ is in the nullspace of this matrix. Furthermore, any other vectors that are in its nullspace (or are eigenvectors that have zero eigenvalue) will reveal the components in the corresponding graph. So I was wondering what would be a decent numerical way of finding these eigenvectors.

share|improve this question
How sure are you that 0 isn't a (numerically) defective eigenvalue for your matrices? –  Guess who it is. Apr 27 '11 at 17:51
Inverse iteration can be made to work in the nondefective case; just make sure that the Gaussian elimination routine you use replaces 0 diagonal entries with "tiny" (usually of size machine epsilon times matrix norm) quantities. You might want to perform a preliminary similarity transformation to Hessenberg form since they're cheaper to decompose. –  Guess who it is. Apr 27 '11 at 17:54
@J.M. I'm quite sure that "0 isn't a (numerically) defective eigenvalue" because I'm making up a hypothetical (i.e. I know my matrix doesn't have full rank). I'm not trying to solve an actual problem I have in front of me. As for your second comment, thanks, and I'll look into my copy of Bau and Trefethen to see how it might work. –  JasonMond Apr 27 '11 at 18:10
The eigenvectors for the $0$ eigenvalue form the kernel of the matrix. You can use Gaussian elimination to find the kernel. What am I missing? –  lhf Apr 27 '11 at 18:37
Oh, it's symmetric! That's a very important piece of knowledge to have, since symmetric matrices cannot be defective. You could replace the "Gaussian elimination" in my previous comment with "$\mathbf L\mathbf D\mathbf L^T$ decomposition" and "Hessenberg" with "tridiagonal" for getting the eigenvectors of $\mathcal L$. –  Guess who it is. Apr 27 '11 at 18:41

Your Answer



Browse other questions tagged or ask your own question.