Take the 2-minute tour ×
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.

I am reading a paper on spectral graph theory. Let us say we have an adjacency matrix W and a degree matrix D. We construct a Laplacian matrix, L defined as:

L = D - W

The paper claims that L is positive semi-definite and that the smallest eigenvalue of L is 0.

I can prove that L is positive semi-definite. But I am having trouble with understanding how the lowest eigenvalue is 0. Is this a general property of positive semi-definite matrices?

share|improve this question

2 Answers 2

up vote 3 down vote accepted

For positive semidefinite matrix $L$, it has the property that any $x$, $x^TLx\geq0$. (1)

If L has a eigendecomposition like $LV=V\Lambda$, columns in $V$ are eigenvectors, and $\Lambda$ is a diagonal matrix each element is the eigenvalue. We can easily rewrite the eigen decomposition as $V^TLV=\Lambda$, each element of $\Lambda$: $\lambda_i=v_i^TLv_i$, because $L$ is positive semidefinite, according to (1) $\lambda_i=v_i^TLv_i\geq0$

Because the sum of all rows of the L matrix is 0 (adjacent vertex number is equal to degree), thus the rows are linearly dependent, thus it is not full rank. So there should be at least one eigenvalue be zero.

share|improve this answer
    
The inequality does not enforce at least one of the eigenvalues to be 0. The claim is that AT LEAST 1 eigenvalue MUST be 0. The inequality only tells us that all eigenvalues are non-negative but it tells us nothing about whether or not the lowest eigenvalue is definitely 0. –  Kishore Nov 27 '12 at 5:30
    
Because the sum of all rows of the L matrix is 0, thus the rows are linearly dependent, thus it is not full rank. So there should be at least one eigenvalue be zero. –  Min Lin Nov 27 '12 at 5:52
    
Yeah. I see it now. Thanks. You can edit your answer above with the answer you provided in the last comment and I will accept it as the answer. Thanks again! –  Kishore Nov 27 '12 at 6:03

If you can prove $L$ is positive-semi definite, it means (by definition) its lowest eigenvalue should be zero. One standard definition of positive semi definiteness is that all its eigenvalues should be non-negative (greater than or equal to zero). If all eigenvalues are greater than zero, then it is positive definite. If at least one of them is zero, then it is positive semidefinite. For a symmetric matrix, the following are some equivalent definitions of positive semi-definiteness

  • Eigenvalues are all non-negative
  • $x^TAx\geq 0$ for all non-zero $x$
  • All principal subminors should have positive determinant.

I don't know if there are any more equivalent definitions

EDIT: From courant-fischer minmax theorem, it follows that for a symmetric matrix, the lowest eigenvalue is given by \begin{align} \lambda_{min}=\min_{x\neq 0}~\frac{x^{T}Ax}{x^Tx} \end{align} Now by definition of positive semi-definiteness, $x^{T}Ax\geq 0$ and that there exist some $x$ for which $x^{T}Ax=0$, hence the lowest eigenvalue should be zero.

share|improve this answer
    
A matrix is positive semi-definite according to the definition shown here. One of its eigenvalues being 0 is a property(not a definition) of semi-definite matrices but that needs proof. –  Kishore Nov 27 '12 at 5:33
    
Actually, you can make the statement (nonnegative eigenvalues) as a definition and state the other one as a property. They are both equivalent. Yes, $x^{T}Ax\geq 0$ is the dominant one. –  dineshdileep Nov 27 '12 at 6:17
    
@Kishore I have included a proof. –  dineshdileep Nov 27 '12 at 6:18
    
Thanks. I tried reading about it but it seems way tougher than what I was already handling. lol. –  Kishore Nov 27 '12 at 6:57
    
@Kishore :):) If you know about eigendecomposition of symmetric matrices, it is actually quite straight forward. If you are interested in learning it , I would really recommend "matrix analysis" by Carl D Meyer (ebook is freely available). But I guess the answer given by the other user is enough for your purpose –  dineshdileep Nov 27 '12 at 7:01

Your Answer

 
discard

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

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