4
$\begingroup$

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

4

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.

  • 0
    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!2012-11-27
0

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.

  • 0
    :) yeah. Actually, I have that book and its awesome! but I have not really read it completely...2012-11-27