近似幂等的对称随机矩阵是否维数无关地接近分块平均？

问题：近似幂等能否稳定地恢复一个分块结构？

这是一个定量稳定性问题。我不知道下面的维数无关结论是否成立，也不将它声称为已知的开放猜想。我感兴趣的是：一个马尔可夫平均算子“再平均一次几乎不变”，是否就意味着它几乎是在若干互不相交的簇内取均匀平均？

设 $n\ge 1$ ， $P\in\mathbb R^{n\times n}$ 满足
$P=P^\top,\qquad P_{ij}\ge 0,\qquad \sum_{j=1}^nP_{ij}=1.$
下文 $\|\cdot\|_{2\to2}$ 是欧氏空间上的算子范数。

对集合 $\{1,\ldots,n\}$ 的任意分划 $\mathcal B$ ，定义分块平均矩阵
$(Q_{\mathcal B})_{ij}= \begin{cases} 1/|B|,&i,j\in B\text{，其中 }B\in\mathcal B,\\ 0,&i,j\text{ 属于不同块}. \end{cases}$

是否存在与 $n$ 无关的函数 $f:(0,1/4)\to[0,\infty)$ ，满足 $\lim_{\varepsilon\downarrow0}f(\varepsilon)=0$ ，且对所有上述 $P$ ，都有
$\|P^2-P\|_{2\to2}\le\varepsilon \quad\Longrightarrow\quad \min_{\mathcal B}\|P-Q_{\mathcal B}\|_{2\to2}\le f(\varepsilon)?$

若成立，希望进一步确定最优量级，例如是否可取 $C\sqrt{\varepsilon}$ 或 $C\varepsilon$ ，其中 $C$ 为绝对常数。若不成立，希望构造 $n_k\to\infty$ 和对称随机矩阵 $P_k$ ，使幂等缺陷趋于零，但到所有分块平均矩阵的距离一致大于某个正数。

可以直接核查的起点

精确情形有分块结构。 当 $P^2=P$ 时，由对称性，按正权边的连通分量重排后得到不可约的随机矩阵块。每块的特征值只能是 0 或 1，而不可约性使特征值 1 为单重。因此每块秩为 1；结合对称性与行和为 1，即得到 $J_m/m$ 。所以 $P=Q_{\mathcal B}$ 。
谱投影容易，保持逐项非负是困难所在。 对称随机矩阵的特征值属于 $[-1,1]$ 。令 $R$ 为将 $P$ 中大于 $1/2$ 的特征值替换为 1、其余替换为 0 得到的正交投影。由 $|\lambda(\lambda-1)|\le\varepsilon$ ，分别在 $\lambda\le1/2$ 和 $\lambda>1/2$ 上估计，可得
$\|P-R\|_{2\to2}\le2\varepsilon,\qquad R\mathbf1=\mathbf1.$
但 $R$ 未必逐项非负，因此这一步并未得到所需的 $Q_{\mathcal B}$ 。
固定维数有定性的稳定性。 对固定 $n$ ，对称随机矩阵集合紧致，结合精确情形的分类，可用子列极限证明相应距离随幂等缺陷趋于零。这里真正的问题是能否对所有维数统一控制。

期待的贡献

一个维数无关的证明及显式误差界；
或一个可核查的反例族；
或指出已有定理及它所使用的范数、是否有维数或最小块大小等额外依赖；
特殊情形、数值线索也欢迎，但请区分数值证据与证明。

本帖没有附上 Lean 文件，也没有声称上述内容已经过形式化验证。

局部进展：任何统一稳定性界都不能优于平方根量级

我还没有解决原问题中“是否存在趋于零的维数无关上界”这一点。但下面的显式矩阵族说明：如果这样的界存在，就不可能取 $C\varepsilon$ ，甚至不可能是 $o(\sqrt{\varepsilon})$ 。

这不是原问题的反例，因为本构造到分块平均矩阵的距离仍然趋于零。因此我将回答标为“进展”。

1. 构造与幂等缺陷

令 $n=2m+1$ ，其中 $m\ge1$ 。把指标分成两个各有 $m$ 个元素的集合 $A,B$ ，以及一个特殊点 $z$ 。定义
$(P_m)_{ij}= \begin{cases} 2/n,& i,j\in A\text{ 或 }i,j\in B,\\ 0,& (i,j)\in A\times B\text{ 或 }B\times A,\\ 1/n,& i=z\text{ 或 }j=z. \end{cases}$
这里最后一行包含 $(z,z)$ 。

矩阵显然对称、逐项非负。普通行的和为 $2m/n+1/n=1$ ，特殊行的和为 $n/n=1$ ，所以它满足原问题的全部假设。

记
$u=\frac{\mathbf1}{\sqrt n},\qquad v=\frac{\mathbf1_A-\mathbf1_B}{\sqrt{n-1}},\qquad \lambda=\frac{n-1}{n}.$
则 $u,v$ 是正交单位向量，并且
$P_m=uu^\top+\lambda vv^\top.$
因此其特征值为 $1,\lambda,0,\ldots,0$ ，从而
$\varepsilon_m:=\|P_m^2-P_m\|_{2\to2} =\lambda(1-\lambda)=\frac{n-1}{n^2}\longrightarrow0.$

2. 对所有分划的距离下界

我将证明
$\min_{\mathcal B}\|P_m-Q_{\mathcal B}\|_{2\to2} \ \ge\ \frac1{\sqrt{n+1}}.$

先排除块数不是 2 的分划：

只有一个块： $Q_{\mathcal B}=uu^\top$ ，故距离为 $\lambda=(n-1)/n\ge1/\sqrt{n+1}$ 。
至少三个块： $Q_{\mathcal B}$ 是秩至少为 3 的正交投影，而 $P_m$ 的秩为 2。因此存在单位向量 $x\in\operatorname{ran}(Q_{\mathcal B})\cap\ker(P_m)$ ，满足 $(P_m-Q_{\mathcal B})x=-x$ ，距离至少为 1。

剩下两块分划 $S,S^c$ 。利用取补集不改变分划，可假定 $s=|S|\le m$ 。记
$w=\sqrt{\frac{n}{s(n-s)}}\left(\mathbf1_S-\frac{s}{n}\mathbf1\right).$
则 $w$ 是与 $u$ 正交的单位向量，且
$Q_{\mathcal B}=uu^\top+ww^\top.$
若 $a=|S\cap A|$ 、 $b=|S\cap B|$ ，则
$|\langle v,w\rangle|^2 =\frac{n(a-b)^2}{(n-1)s(n-s)} \le\frac{ns}{(n-1)(n-s)} \le\frac{n}{n+1}.$
第一个不等式用到 $|a-b|\le s$ ；第二个用到 $s\le m=(n-1)/2$ 。当 $S=A$ 时等号成立。

令 $R=uu^\top+vv^\top$ ，它是投向 $\operatorname{span}(u,v)$ 的正交投影。因为 $(I-R)P_m=0$ 且 $Q_{\mathcal B}w=w$ ，所以
$\begin{aligned} \|P_m-Q_{\mathcal B}\|_{2\to2} &\ge\|(I-R)(P_m-Q_{\mathcal B})w\|_2\\ &=\|(I-R)w\|_2\\ &=\sqrt{1-|\langle v,w\rangle|^2}\\ &\ge\frac1{\sqrt{n+1}}. \end{aligned}$
至此覆盖了所有分划，而不是只检验某个自然分块。

3. 此构造的距离确实就是平方根量级

取具体分划 $\mathcal B_*=\{A,B\cup\{z\}\}$ 。上面的相关系数恰好满足
$|\langle v,w\rangle|^2=\frac{n}{n+1}.$
在 $v,w$ 张成的至多二维空间中直接计算，可得两个秩一正交投影的差满足
$\|vv^\top-ww^\top\|_{2\to2} =\sqrt{1-|\langle v,w\rangle|^2} =\frac1{\sqrt{n+1}}.$
又有 $\|P_m-R\|_{2\to2}=1/n$ ，于是
$\frac1{\sqrt{n+1}} \le \min_{\mathcal B}\|P_m-Q_{\mathcal B}\|_{2\to2} \le \frac1{\sqrt{n+1}}+\frac1n.$
结合 $\sqrt{\varepsilon_m}=\sqrt{n-1}/n$ ，两端除以 $\sqrt{\varepsilon_m}$ 都趋于 1。因此事实上
$\frac{\min_{\mathcal B}\|P_m-Q_{\mathcal B}\|_{2\to2}} {\sqrt{\varepsilon_m}}\longrightarrow1.$

结论与下一步

任何满足原问题要求的函数 $f$ ，都必须在这列 $\varepsilon_m$ 上至少具有平方根量级。特别地，所有 $C\varepsilon^\alpha$ 且 $\alpha>1/2$ 的统一上界都不成立。

这个例子的机制是：特殊点的总数量只有 1，但它必须在分划中完整归入某一块，导致投影子空间出现约 $n^{-1/2}$ 的偏转；幂等缺陷却只有约 $n^{-1}$ 。

接下来仍需证明普遍的 $C\sqrt{\varepsilon}$ 上界，或寻找距离衰减更慢、乃至不衰减的矩阵族。本回答并未证明这样的上界存在。

核查说明：上文是手工代数论证；另枚举了 $n=3,5,\ldots,17$ 的所有非空真子集，核对相关系数平方的最大值为 $n/(n+1)$ 。枚举仅作辅助核查，不替代证明。没有 Lean 形式化验证。