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?
Best Answer
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.