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?


2 Answers 2


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.

  • $\begingroup$ 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. $\endgroup$
    – Spectre
    Nov 27, 2012 at 5:30
  • $\begingroup$ 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. $\endgroup$
    – Min Lin
    Nov 27, 2012 at 5:52
  • $\begingroup$ 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! $\endgroup$
    – Spectre
    Nov 27, 2012 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.

  • 1
    $\begingroup$ 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. $\endgroup$
    – Spectre
    Nov 27, 2012 at 5:33
  • $\begingroup$ 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. $\endgroup$ Nov 27, 2012 at 6:17
  • $\begingroup$ @Kishore I have included a proof. $\endgroup$ Nov 27, 2012 at 6:18
  • $\begingroup$ Thanks. I tried reading about it but it seems way tougher than what I was already handling. lol. $\endgroup$
    – Spectre
    Nov 27, 2012 at 6:57
  • $\begingroup$ @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 $\endgroup$ Nov 27, 2012 at 7:01

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .