Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question
    
How sure are you that 0 isn't a (numerically) defective eigenvalue for your matrices? – J. M. 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. – J. M. 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
1  
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
2  
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$. – J. M. Apr 27 '11 at 18:41

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.