In Mining Massive Datasets, page 365, the following theorem is stated without proof:

Let A be a symmetric matrix. then the second-smallest eigenvalue of A is equal to $\displaystyle \min_{x} {x^TAx}$, when the minimum is taken over all unit vectors x that are orthogonal to the eigenvector $v_1$ associated with the smallest eigenvalue.

This phrasing seems somewhat sloppy, because let's look at the case where the smallest eigenvalue has an eigenspace of dimension $>1$. I think we will not really get the second-smallest eigenvalue $\lambda _2$ but the smallest eigenvalue $\lambda _1$ itself, because we can take another unit eigenvector of $\lambda _1$ that is orthogonal to $v_1$, and it will satisfy the minimization problem. ($x^TAx=x^T \lambda x =\lambda$)

So probably the right two theorems are:

  1. The $k^{th}$ smallest (distinct) eigenvalue of L is equal to $\displaystyle \min_{x} {x^TAx}$, when the minimum is taken over all unit vectors x that are orthogonal to all of the eigenvectors associated with the smallest $k-1$ eigenvalues.

  2. The second smallest eigenvalue of L counted with multiplicities according to the dimensions of the eigenspaces is equal to $\displaystyle \min_{x} {x^TAx}$, when the minimum is taken over all unit vectors x that are orthogonal to an eigenvector associated with the smallest eigenvalue.

For the $k^{th}$ smallest in the second proposition, we ask for orthogonality to all eigenvectors of the smaller eigenvalues.

Is it right? And how do I prove in both cases that $\displaystyle \min_{x} {x^TAx} \leq \lambda _k$?

This answer shows that without the second constraint we get the smallest eigenvalue, because the $x$ that gives the minimum is an eigenvector of $\frac{A+A^T}{2}=A$, and hence gives as the value of the quadratic form its associated eigenvalue. The answer there also seems to hint at the necessity of an assumption on the positive semi-definiteness of $A$; is it needed? The book does not require it.

  • $\begingroup$ It seems that the smallest eigenvalue of Laplacian is always zero and always simple. I've found that this fact is mentioned for example here, cs.elte.hu/~lovasz/eigenvals-x.pdf , at page 7. And since this eigenspace is one-dimensional, their method for finding second smallest eigenvalue seems to work. $\endgroup$ – Evgeny Aug 20 '15 at 14:42
  • $\begingroup$ what is the relationship between $L$ and $A$? $\endgroup$ – Chester Aug 20 '15 at 14:45
  • $\begingroup$ They're the same :) The fact that the laplacian has smallest eigenvalue 0 is simply because it is semidefinite (symmetric and diagonally semi-dominant) and 1,...,1 is an eigenvector of 0. That it is simple is interesting, but the theorem in the book relates to all symmetric matrices, not only laplacians. $\endgroup$ – Emolga Aug 20 '15 at 14:48
  • 3
    $\begingroup$ See the min-max theorem. We are using the fact that $L$ is symmetric. $\endgroup$ – Omnomnomnom Aug 20 '15 at 14:50
  • 1
    $\begingroup$ @Leullame Sorry, my bad, I was inaccurate. About multiiplicity of zero eigenvalue. If graph has multiple connected components, you can rearrange vertices such way that Laplacian will become block-diagonal. And instead of one eigenvector $\mathbb{1}$ you can construct multiple eigenvectors that have ones at entries which correspond to particular connected component and zeros at other entries. $\endgroup$ – Evgeny Aug 20 '15 at 15:08

The name "min-max theorem" given in the comments lead to the following very elegant proof.

To repeat in our context: given a symmetric matrix A, we construct an orthonormal basis $\{ v_1,b_2,...,b_n \}$ to $\mathbb{R}^n$ using the eigenvectors of A (which is possible due to the symmetry of A), using the eigenvector $v_1$ from the theorem. As we only look at the space orthogonal to $v_1$ in the minimization, $\{ b_2,...,b_n \}$ is an orthonormal basis.

We note that the dot product can be done coordinate-wise in any orthonormal basis, and hence for all unit vectors $x=(x_2,...,x_n)$ in this orthogonal space: $${x^TAx}=(\sum_{j=2}^n x_j b_j^T)A(\sum_{i=2}^n x_ib_i)=\sum _{i,j}x_i x_j b_j^T A b_i=\sum _{i,j}x_i x_j b_j^T \lambda _i b_i$$ As $Ab_i=\lambda_i b_i$. Now we use $b_j^T b_j=\delta_{ij}$, as they compose an orthonormal basis, to get: $$=\sum _{i}\lambda_i x_i^2 \geq \sum _{i}\lambda_2 x_i^2=\lambda_2$$

Since $x$ is of unit length. we proved that for all $x$ on which we minimize, ${x^TAx} \geq \lambda_2$, and hence $\min{x^TAx} \geq \lambda_2$. The other direction is easy and in written in the question itself. $\square$

The proof assumed indeed that we count the eigenvalues according to their algebraic multiplicity, $\lambda_1 \leq ... \leq \lambda _n$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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