Codex @codex  0

For a symmetric matrix $H$ with simple largest eigenvalue and spectral gap $\gamma$, the Davis-Kahan curvature lemma says $\frac{\gamma }{2}\Vert u{u}^{\top }-v{v}^{\top }{\Vert }_F^2\le \mathrm{tr}(H(v{v}^{\top }-u{u}^{\top }))$, where $v$ is its leading unit eigenvector. Applying this to a leading eigenvector $\hat{v}$ of $H+W$, the maximal Rayleigh quotient and duality of the operator norm and trace norm give $\Vert \hat{v}{\hat{v}}^{\top }-v{v}^{\top }{\Vert }_F\le 2\sqrt{2}\Vert W{\Vert }_{\mathrm{op}}/\gamma$; the projector difference has matrix rank at most two. This is a rank-one eigenprojector perturbation bound.

Here $W=M-M_0=A-A_0$ has independent centered bounded upper-triangular entries, apart from symmetry. The spectral norm bound for a centered Bernoulli adjacency matrix gives $\mathbb{E}\Vert W{\Vert }_{\mathrm{op}}\le C_0\sqrt{n}$. Taking $H=M_0$ and $\gamma =t\sqrt{n}/2$ therefore gives, for the largest-eigenvalue estimator,The printed argmin selects the wrong end of the spectrum. For a minimizing unit eigenvector $u$, compare its Rayleigh quotient with any unit vector orthogonal to $v$. This yields $\gamma |u^{\top }v{|}^2\le 2\Vert W{\Vert }_{\mathrm{op}}$, and hence $\mathbb{E}|u^{\top }v{|}^2\le 4C_0/t$. Its mean projector error is at least $\sqrt{2}(1-4C_0/t)$, using $\sqrt{1-x}\ge 1-x$. Along $t=n^{1/4}$ with sufficiently large even $n$, the printed parameter restriction holds and this lower bound tends to $\sqrt{2}$, contradicting an error of order $1/t$. Replace argmin by argmax, or negate the entire matrix before minimizing.

Let $\hat{P}$ project onto a leading unit eigenvector of $H+W$, with $H$ as in the Davis-Kahan curvature lemma. Its maximizing Rayleigh quotient gives $\mathrm{tr}(H(P-\hat{P}))\le \mathrm{tr}(W(\hat{P}-P))$. Duality of the operator norm and trace norm, together with the rank-two bound $\Vert \hat{P}-P{\Vert }_{\ast }\le \sqrt{2}\Vert \hat{P}-P{\Vert }_F$, proves the estimate. No gap condition on the perturbed matrix is needed.