There is a proof in a paper (Link) that shows that the dirichlet energy of any matrix X gets reduced when the adjacency matrix $\tilde{A}=\tilde{D}^{-0.5}(A + I_n)\tilde{D}^{-0.5}$ is applied: $$E(\tilde{A}X) \leq (1-\lambda_0)^2E(X)$$
where the dirchlet energy is defined as $$E(X) = tr(X^T\tilde{\Delta} X) = \frac{1}{2}\sum_{ij}\tilde{a}_{ij}||\frac{x_i}{\sqrt{1+d_i}} - \frac{x_j}{\sqrt{1+d_j}}||_2^2$$
and $\lambda_0$ is the non-zero eigenvalue of $\tilde{\Delta}=I_n - \tilde{A}$ closest to $0$.
I wonder about two things about their proof:
- Why has $\lambda_0$ to be non-zero?
- Why must $\lambda_0$ be the closest to $0$, when all $\lambda_i \in [0,2)$ and the $\lambda_i$ closest to $2$ could result in a larger $(1-\lambda_i)^2$?
Here is my detailed version of the proof:
$$\begin{align}E(\tilde{A}X) &= tr((\tilde{A}X)^T\tilde{\Delta}\tilde{A}X) \\ &= tr(X^T(I_n - \tilde{\Delta})\tilde{\Delta}(I_n - \tilde{\Delta})X)\ (\because \tilde{A}^T=\tilde{A})\\ &= tr(X^T\tilde{\Delta}(I_n - \tilde{\Delta})^2X) \\ &= tr(U^T(XX^T\tilde{\Delta})U\Sigma^2)\ (\because \textrm{eigendecomposition})\\ &= diag(U^T(XX^T\tilde{\Delta})U)\cdot diag(\Sigma^2)\ (\because \Sigma^2 \textrm{is diagonal})\\ &\leq diag(U^T(XX^T\tilde{\Delta})U) \cdot \max(\Sigma^2) \\ &= (1-\lambda_i)^2 tr(X^T\tilde{\Delta}X) \end{align}$$
My problem is that $\max_i((1-\lambda_i)^2)$ may be different from $\lambda_0$.
Towards 1.: My idea is that the dirichlet energy for the eigenvector corresponding to eigenvalue $\lambda_i=0$ is $0$. Therefore only other eigenvalues are considered.
I would be very happy if someone has any ideas!