Under the simple constant-kernel condition, LLE trace minimizers are bottom positive eigenvectors

Put $A=I_n-W$. Then $A{\mathbf{1}}_n=0$ by [F1], and $M=A^{T}A$ is symmetric with $M{\mathbf{1}}_n=0$. For every $v$, $v^{T}Mv=(Av{)}^T(Av)={\sum }_r(Av{)}_r^2\ge 0$ by [F2]. Also $Mv=0$ implies $0=v^{T}Mv={\sum }_r(Av{)}_r^2$, hence $Av=0$; conversely $Av=0$ implies $Mv=0$. Therefore $\ker M=\ker A=\mathrm{span}\{{\mathbf{1}}_n\}$.

By [F4], ${\mathbb{R}}^n=\mathrm{span}\{{\mathbf{1}}_n\}\oplus S$ for $S={\mathbf{1}}_n^{\perp }$, and [F3] gives an orthonormal basis matrix $E\in {\mathbb{R}}^{n\times (n-1)}$ for $S$. Symmetry and $M{\mathbf{1}}_n=0$ imply $M(S)\subseteq S$, because ${\mathbf{1}}_n^{T}Mv=(M{\mathbf{1}}_n{)}^{T}v=0$ for $v\in S$. The restriction is self-adjoint and has matrix $R=E^{T}ME$, which is symmetric and positive definite: if $c\mathrm{\ne }0$, then $Ec\in S\setminus \{0\}$, so $Ec\mathrm{\notin }\ker M$ by step 1.1 and $c^{T}Rc=(Ec{)}^{T}M(Ec)={\sum }_r(AEc{)}_r^2>0$. By [F7], the restriction has an orthonormal eigenbasis; for each unit eigenvector with eigenvalue $\mu$, positive definiteness gives $\mu >0$. List its eigenvalues as $0<{\mu }_1\le \cdots \le {\mu }_{n-1}$.

For every feasible $Y$, its columns lie in $S$, so $Y=EQ$ with $Q=E^{T}Y$ and $Q^{T}Q=I_q$. Substitution gives $Y^{T}MY=Q^{T}RQ$, hence $\mathrm{tr}(Y^{T}MY)=\mathrm{tr}(Q^{T}RQ)$ by [F6]. Apply [F5] to $-R$, whose eigenvalues in descending order are $-{\mu }_1\ge \cdots \ge -{\mu }_{n-1}$. It follows that $\mathrm{tr}(Q^{T}RQ)\ge {\sum }_{j=1}^q{\mu }_j$, with equality exactly for the q-dimensional bottom eigenspaces, including arbitrary choices inside a tie.

Taking $Q$ to have orthonormal columns spanning q bottom eigendirections of $R$ and setting $Y=EQ$ satisfies both constraints and attains the bound in step 3.1. This proves the minimum and its equality cases.