I am currently stuyding spectral graph theory and in my slides I stumbled on the following solution to obtain the Fiedler vector: \begin{align} \min_x x^T L_G x \\ \text{s.t. } x^T x = 1 \\ x^T \vec{1} = 0 \end{align} $L_G$ is the graph Laplacian of an undirected graph and the Fiedler vector is the eigenvector corresponding to the second smallest eigenvalue $\lambda_2 $. This is obviosly related to the Rayleigh-Ritz Theorem that states that we can compute the second smallest eigenvalue as: \begin{align} \lambda_2=\min_{x\perp {v_1}}\frac{x^TL_Gx}{x^Tx} \end{align} I have the following questions:
- Why do we use $x^Tx=1$ as a constraint and how is it connected to the Rayleigh-Ritz Theorem ?
- Do we use $x^T \vec{1}=0$ as a constraint to guarantee that we are minimizing over the vectors that are orthogonal to the vectors corresponding to the smallest eigenvalue ? ($\vec{1}$ is in the graph Laplacian always an eigenvector corresponding to the smallest eigenvalue)