Eigenvalues of graph laplacian question

96 Views Asked by At

I need some guidance on solving the following question I am stuck on:

Let L be a graph Laplacian matrix of a graph G = (V, E) with n vertices. Denote the eigenpairs of L by {λi,ψi} for every i=1..n, where the eigenvalues are sorted from the smallest to the largest. Let y1,y2,...,yk be orthonormal vectors that are all orthogonal to 1, where k<n. Show that \begin{equation} \sum_{i=1}^{k}y^\top_{i} L y_{i} \geq \sum_{i=2}^{k+1}\lambda_{i} \end{equation} and find the condition when will be the inequality tight.

I tried using the facts that L = D - A and \begin{equation} \sum_{i}d_{i}= \sum_{i}\lambda_{i} \end{equation} where $ \lambda $ are the eigenvalues, and $ d $ are the the diagonal elements of $ \mathbf{L} $.

I am currently stuck here and I don't know how to move on from here. I tried searching online and reading for some time now but didn't get any more ideas.

Thanks :)