We can achieve some clarity about this objective function by rewriting it using linear algebra.
if we define the normalized indicator vectors h k := (h 1k , ..., h Nk ) T where we set then some straightforward computations reveal that: if we collect the vectors h 1 , ..., h K into a matrix H = (h 1 , ..., h K ), then h T k Lh k = (H T LH) kk , and minimizing Equation (3) is equivalent to the following minimization problem on the graph Laplacian: if we could find the optimal H, it would be straightforward to find the cluster memberships from H, since h ik is nonzero if and only if v i is in cluster A k .