6.1 图拉普拉斯矩阵与谱坐标

一组观测未必附有每项特征的有意义坐标。我们可能只知道哪些对象互相作用，以及作用有多强。图记录的就是这类资料。要从图建立坐标，先要说清楚坐标应达成什么：相邻顶点的坐标差应小，但整个配置又不能全部塌缩至同一点。

本原创补充笔记为有限、无向、非负加权图推导这种构造。数学准备包括有限和、实内积、正交投影及基本微分。我们也会使用有限维紧致性：实欧氏空间中的闭有界集是紧致的，而非空紧致集上的连续实函数取得最大值及最小值。PCA 笔记已发展 SVD 与投影优化；我们沿用其中的投影权重方法，并在此证明所需的有限维实谱定理。MDS 笔记处理另一问题：重建给定的距离表。这里的路径是由互不相同顶点组成的有限序列，相邻顶点之间有正权边；零长路径把一个顶点连至自身。两点之间存在路径便称为连通，所得等价类称为连通分量。为证传递性，把两条路径串接成可重复顶点的游走，再删去同一顶点两次出现之间的部分。每次删除都保留端点并缩短游走，有限次之后便得到路径。

以下会明确区分三件事。对称亲和矩阵未必是半正定核矩阵；平稳的随机游走分布未必是极限分布；连续谱松弛未必精确解决其离散割问题。

1. 加权边与顶点函数的能量

设顶点集为 $V=\{1,\ldots,n\}$，先假设 $n\ge1$。权重矩阵 $W=(w_{ij})\in\mathbb R^{n\times n}$ 满足

$$w_{ij}=w_{ji}\ge0,\qquad w_{ii}=0.$$

权重可以是任何非负实数，不必是概率、整数或不大于一。支撑图恰在 $w_{ij}>0$ 时有无向边 $\{i,j\}$。所有连通分量均指此图的分量。即使图画上画了某对顶点之间的线，零权重也不提供连接。

加权度数、度数矩阵与未归一化拉普拉斯矩阵分别为

$$d_i=\sum_{j=1}^n w_{ij},\qquad D=\operatorname{diag}(d_1,\ldots,d_n), \qquad L=D-W.$$

由非负性，$d_i=0$ 当且仅当第 $i$ 行的权重全部为零；这样的顶点是孤立点。顶点函数是一个实列向量 $f=(f_1,\ldots,f_n)^T$，可表示候选坐标、温度或其他标量信号。矩阵乘法给出

$$(Lf)_i=\sum_jw_{ij}(f_i-f_j).$$

因此 $L\mathbf1=0$，其中 $\mathbf1$ 是全一列向量。把常数加到信号上不会改变边两端的差。

能量恒等式。 对每个 $f\in\mathbb R^n$，

$$f^TLf =\frac12\sum_{i,j}w_{ij}(f_i-f_j)^2 =\sum_{i<j}w_{ij}(f_i-f_j)^2.$$

证明。 展开双和，两个平方项给出 $\frac12\sum\limits_i d_i f_i^2+\frac12\sum\limits_j d_j f_j^2=\sum\limits_i d_i f_i^2$；第二个度数和的辨认使用了对称性。交叉项是 $-\sum\limits_{i,j}w_{ij}f_if_j$，相减便是 $f^T(D-W)f$。每个无序顶点对在双和出现两次，对角项则为零，故亦得到最后的等式。所有和均为有限和。∎

所以 $L$ 对称且半正定。强边的坐标差受到较重惩罚；这里没有使用协方差解释，也没有假设 $W$ 本身半正定。例如

$$W=\begin{pmatrix}0&a\\a&0\end{pmatrix},\qquad a>0,$$

的特征值为 $a,-a$，其拉普拉斯矩阵的特征值却是 $0,2a$。这个图亲和矩阵不是半正定 Gram 矩阵。反过来，两个实向量 $1,-1$ 的 Gram 矩阵为 $\begin{pmatrix}1&-1\\-1&1\end{pmatrix}$；其二次型是 $(x_1-x_2)^2$，所以半正定，但非对角元素有负数，并不符合这里的图假设。

核与连通分量。 函数属于 $\ker L$，当且仅当它在每个支撑分量上为常数。因此，若分量数为 $c$，则

$$\dim\ker L=c,\qquad \operatorname{rank}L=n-c.$$

证明。 若 $Lf=0$，则 $f^TLf=0$。能量的每项均非负，所以每条正权边的端点函数值必相同。沿路径传递此等式，便知每个分量上的值相同。反之，若函数在各分量为常数，则 $(Lf)_i=\sum\limits_jw_{ij}(f_i-f_j)$ 的每项均为零：正权边留在同一分量，零权边不作贡献。分量的指示列向量支撑互不相交，而且每个分量非空，所以它们线性独立，亦张成所有这类函数。每个孤立点同样贡献自己的指示向量。由秩—零度定理得到秩公式。∎

符号假设不能省略。若二点图的唯一边权为 $-1$，能量便是 $-(f_1-f_2)^2$，对非常数函数为负。有向图与带符号图需要不同陈述，不在本笔记范围内。

2. 有限维实谱桥梁与第二特征值

PCA 的构造使用实对称矩阵的正交归一特征基。以下给出有限维证明，让图的论证不依赖隐藏的谱定理。

实对称谱定理。 每个实对称矩阵 $S$ 都有由实特征向量组成的正交归一基。

证明。 零维时空基已足够。维数 $m\ge1$ 时，连续函数 $x\mapsto x^TSx$ 在紧致单位球面上取得最大值。选一个达到最大值的单位列向量 $v$。对任意满足 $h^Tv=0$ 的实列向量 $h$，曲线

$$x(t)=\frac{v+th}{\sqrt{1+t^2\|h\|^2}}$$

对每个实 $t$ 都有单位长度。可以在零点微分，其二次型导数为

$$\left.\frac{d}{dt}\bigl(x(t)^TSx(t)\bigr)\right|_{t=0} =2h^TSv=0.$$

所以 $Sv$ 垂直于 $v^\perp$ 的每个向量。由 $\operatorname{span}\{v\}$ 与 $v^\perp$ 的正交分解，存在实数 $\lambda$ 使 $Sv=\lambda v$。若 $h\in v^\perp$，对称性给出 $v^TSh=(Sv)^Th=\lambda v^Th=0$，故 $v^\perp$ 是不变子空间，限制在其上的算子仍实对称。对维数 $m-1$ 使用归纳假设，再加上 $v$，便得到所需正交归一特征基。∎

半正定矩阵的每个特征值均非负，因为 $Sq=\lambda q$ 且 $\|q\|=1$ 时有 $\lambda=q^TSq\ge0$。

将此用于 $L$。已知的零特征值方向使我们可以先选第一个特征向量：

$$q_1=\frac{\mathbf1}{\sqrt n}.$$

由 $\mathbf1^TLf=(L\mathbf1)^Tf=0$，空间 $\mathbf1^\perp$ 不变。对其限制使用定理，把特征值递增排列，得到

$$Lq_j=\lambda_jq_j,\qquad 0=\lambda_1\le\lambda_2\le\cdots\le\lambda_n.$$

此排序容许多个零特征值。把 $q_1$ 选成常数并不表示图连通。

当 $n\ge2$，第二特征值具有精确优化公式

$$\lambda_2 =\min_{\substack{f^T\mathbf1=0\\\|f\|=1}} f^TLf.$$

证明。 把中心化单位函数写为 $f=\sum\limits_{j=2}^n a_jq_j$，则 $\sum\limits_{j=2}^n a_j^2=1$，且 $f^TLf=\sum\limits_{j=2}^n\lambda_ja_j^2\ge\lambda_2$。取 $f=q_2$ 达到此界。等号成立当且仅当所有对应大于 $\lambda_2$ 特征值的系数为零。因此所有极小函数是 $\mathbf1^\perp$ 中 $\lambda_2$ 特征空间的单位向量，不是一个具有唯一方向的列向量。∎

特别地，$\lambda_2>0$ 当且仅当支撑图连通。若连通，核只有 $\operatorname{span}\{\mathbf1\}$，其正交补上的每个特征值均正。若不连通，便存在非零、中心化而分量常值的函数，故极小值为零。这是代数谱与组合结构之间的精确联系。

只有一个顶点时 $L=0$，既没有第二特征值，也没有中心化单位函数。两个或以上顶点的零矩阵有多个分量，且 $\lambda_2=0$。也可以另行容许空顶点集：矩阵为空，核的维数为零，但同样没有第二特征值。这些情况都不表示在不存在的单位向量上取极小值。

3. 不除以孤立度数的归一化

加权度数可能相差很大。归一化以端点度数调整边差，但必须先处理零度数。

设

$$S=\{i:d_i>0\},\qquad Z=V\setminus S.$$

没有边与 $Z$ 相接。把 $W,D,L$ 限于 $S$，所得矩阵记作 $W_S,D_S,L_S$。若 $S$ 非空，$D_S$ 正定，可以定义

$$N_S=D_S^{-1/2}L_SD_S^{-1/2} =I_S-D_S^{-1/2}W_SD_S^{-1/2}.$$

全空间的归一化拉普拉斯矩阵 $N$ 在 $S$ 上等于 $N_S$，在每个孤立坐标上则等于零。等价地，令对角矩阵 $R$ 在 $S$ 上的元素为 $d_i^{-1/2}$，在 $Z$ 上为零，则

$$N=RLR.$$

有孤立点时，此矩阵不等于 $I_n-RWR$；后者把孤立对角元素设成一。解释零模前必须交代使用哪种约定。本笔记始终使用零延拓。若 $S$ 为空，$N=0$，不会形成任何度数逆矩阵。

对活跃坐标上的列向量 $x$，令 $g=D_S^{-1/2}x$。能量恒等式给出

$$x^TN_Sx=\sum_{\substack{i<j\\i,j\in S}}w_{ij} \left(\frac{x_i}{\sqrt{d_i}}-\frac{x_j}{\sqrt{d_j}}\right)^2.$$

所以 $N_S$ 半正定。其核中的向量，在每个活跃支撑分量上都等于同一常数乘以 $\sqrt{d_i}$。逆向可由坐标公式看出，或注意分量常值的 $g$ 满足 $N_Sx=D_S^{-1/2}L_Sg=0$。因此每个活跃分量贡献限制于该分量的 $\sqrt d$ 列向量；零延拓下每个孤立列向量 $e_i$ 再贡献一个核向量。全归一化矩阵与未归一化矩阵的核维数相同，但在活跃分量上的向量缩放不同。

$N$ 的谱包含于 $[0,2]$。事实上，在活跃坐标上，由 $(a-b)^2\le2a^2+2b^2$ 得

$$0\le x^TN_Sx \le 2\sum_i d_i\left(\frac{x_i}{\sqrt{d_i}}\right)^2 =2\|x\|^2.$$

每条边分别贡献至两端的度数和，故没有额外的二倍因子。把此界用于单位特征向量，便知每个活跃特征值介乎零与二；孤立零特征值也符合此界。两个顶点由一条正权边相连时，归一化矩阵是 $\begin{pmatrix}1&-1\\-1&1\end{pmatrix}$，特征值 $0,2$ 同时达到两端。

归一化是度量的改变，不是把零度数取逆的许可。加权形式 $f^TDg$ 在活跃坐标上是内积，在全空间却会于孤立列向量上消失，仅为半正定形式。

4. 可逆游走未必收敛

只在活跃集上定义

$$P=D_S^{-1}W_S,\qquad P_{ij}=\frac{w_{ij}}{d_i}.$$

矩阵元素非负，每行和为一。因此它是行随机转移矩阵：$P_{ij}$ 表示一步由 $i$ 到 $j$ 的概率。对顶点函数 $f$，$(Pf)_i$ 是从 $i$ 出发走一步后的函数期望值。相反，概率列向量 $r_t$ 的更新是

$$r_{t+1}=P^Tr_t.$$

这个转置不可忽略。把概率列向量乘以 $P$ 使用了另一约定，未必保留其总质量。

本节余下所有矩阵与列向量均限于 $S$。由 $W$ 对称，

$$DP=W=P^TD.$$

因此 $P$ 对内积 $\langle f,g\rangle_D=f^TDg$ 自伴： $f^TDPg=f^TWg=(Pf)^TDg$。它未必在普通欧氏内积下对称。直接计算相似变换得

$$D^{1/2}PD^{-1/2}=D^{-1/2}WD^{-1/2}=I-N_S.$$

所以若 $N_Su=\mu u$，则 $f=D^{-1/2}u$ 满足 $Pf=(1-\mu)f$。$N_S$ 的正交归一特征基转成 $P$ 的 $D$-正交归一特征基。特别地，$P$ 的特征值均为实数且位于 $[-1,1]$，不需要另引随机矩阵谱定理。

若 $S$ 非空，总度数 $\operatorname{vol}(S)=\sum\limits_{i\in S}d_i$ 为正。定义概率列向量

$$\pi_i=\frac{d_i}{\operatorname{vol}(S)}.$$

对每个活跃 $j$，有限求和给出

$$(\pi^TP)_j =\sum_i\frac{d_i}{\operatorname{vol}(S)}\frac{w_{ij}}{d_i} =\frac{d_j}{\operatorname{vol}(S)}=\pi_j.$$

因此 $\pi$ 平稳。又有 $\pi_iP_{ij}=w_{ij}/\operatorname{vol}(S)=\pi_jP_{ji}$，即细致平衡恒等式。活跃图若不连通，在任一分量内单独归一化度数，便得到支撑于该分量的平稳分布；这些分布的凸组合也平稳。未经进一步论证，我们不宣称唯一性。

平稳不等于收敛。两个顶点之间只有一条正权边时，

$$P=\begin{pmatrix}0&1\\1&0\end{pmatrix},\qquad \pi=\begin{pmatrix}1/2\\1/2\end{pmatrix}.$$

分布 $\pi$ 保持不变，但从顶点一出发的游走，每个偶数时刻都在顶点一，奇数时刻都在顶点二，其分布不收敛。代数上，特征值 $-1$ 保留了一个交替分量；对应的归一化特征值是 $2$。所以存在平稳向量不能推出混合结论。本笔记不作一般收敛速率声明。

若所有度数为零，活跃集为空，没有活跃游走或由度数归一化得到的概率分布。可以另行把孤立状态设为吸收态，但那是额外模型资料，不是零除以零所得的值。

5. 谱坐标实际极小化什么

常数坐标的能量为零；把所有坐标设成零，更会令所有顶点重合。为避免这些塌缩，要求坐标列中心化且正交归一。

对整数 $0\le k\le n-1$，选 $U\in\mathbb R^{n\times k}$ 满足

$$U^TU=I_k,\qquad U^T\mathbf1=0.$$

顶点 $i$ 的坐标是第 $i$ 行 $U_{i:}\in\mathbb R^k$。把标量能量公式用于每列并求和，便证得

$$\operatorname{tr}(U^TLU) =\sum_{i<j}w_{ij}\|U_{i:}-U_{j:}\|^2.$$

此目标是加权边上的总平方变化，不是与给定成对距离表的误差。

最小迹原理。 沿用第2节的特征值排序，

$$\min_{\substack{U^TU=I_k\\U^T\mathbf1=0}} \operatorname{tr}(U^TLU) =\sum_{j=2}^{k+1}\lambda_j.$$

$k=0$ 时矩阵没有列，两边均为零。$k\ge1$ 时可取 $U=[q_2\ \cdots\ q_{k+1}]$ 达到此值。

证明。 在 $\mathbf1^\perp$ 内工作，其正交归一特征基为 $q_2,\ldots,q_n$。令

$$a_j=\|U^Tq_j\|^2,\qquad 2\le j\le n.$$

因 $UU^T$ 是到 $U$ 列空间的正交投影，$0\le a_j\le1$。把 $U$ 每个单位列向量在此基底展开，再加总其平方系数，得 $\sum\limits_{j=2}^na_j=k$。谱展开亦给出 $\operatorname{tr}(U^TLU)=\sum\limits_{j=2}^n\lambda_ja_j$。

设 $c=\lambda_{k+1}$。刚证得的总和恒等式给出精确差值

$$\begin{aligned} \sum_{j=2}^n\lambda_ja_j-\sum_{j=2}^{k+1}\lambda_j &=\sum_{j=2}^{k+1}(c-\lambda_j)(1-a_j)\\ &\quad+\sum_{j=k+2}^n(\lambda_j-c)a_j\ge0. \end{aligned}$$

每个显示的系数均非负。取中心空间内首 $k$ 个特征向量便达到等号，证明了极小值。这正是 PCA 使用的投影权重方法，只因现在极小化变化而非极大化方差，所以特征值排序方向相反。∎

对 $k\ge1$，差值公式亦给出精确等号条件。在 $\mathbf1^\perp$ 内，保留列空间必须包含特征值小于 $c$ 的全部特征空间，并垂直于特征值大于 $c$ 的全部特征空间；在特征值等于 $c$ 的空间内，则可任选补足至 $k$ 维所需的维数。理由是：$a_j=1$ 表示投影保留 $q_j$ 的全部范数，故 $q_j$ 在该列空间；$a_j=0$ 表示它垂直于该空间。截断值处的零系数恰好留下上述自由。即使 $c>0$，也不会要求把已排除的常数方向重新纳入。

若 $k<n-1$ 且 $\lambda_{k+1}<\lambda_{k+2}$，保留子空间确定。若 $k=n-1$，保留的就是整个中心空间，也确定。但两者都没有固定一个带方向的基底。若两个可行矩阵 $U,V$ 张成同一子空间，定义 $Q=U^TV$。因到该空间的投影同时等于 $UU^T$ 与 $VV^T$，

$$UQ=UU^TV=V,\qquad Q^TQ=V^TUU^TV=V^TV=I_k.$$

方阵 $Q$ 正交，所以 $V=UQ$ 不改变行坐标间的距离，亦有 $VV^T=UU^T$。但是跨越截断边界的重特征值可以容许真正不同的保留子空间；它们的行距离未必相同，第2题会明算此现象。

若图不连通，某些中心化分量指示组合具有零能量。定理仍成立，可以把不同分量分开而不为不存在的连接付出能量，但不会辨认出唯一聚类。一个顶点只允许 $k=0$。空图也可另行容许空的零列配置，不涉及任何非零维嵌入声明。

比较其目标：PCA 从特征观测保留最大方差方向；经典 MDS 从距离寻找中心化 Gram 实现；此处则由给定边权定义平滑程度，保留最低非常数图能量方向。使用特征向量不代表解的是同一问题。因此以上正交归一图坐标并未声称具有 PCA 解释方差比例、MDS 距离保留定理，或逆平方根特征值缩放。

6. 归一化割的精确指示商与松弛

现在假设支撑图连通且 $n\ge2$，故每个度数均正。对非空真子集 $A\subset V$，令 $B=V\setminus A$，定义

$$\operatorname{vol}(A)=\sum_{i\in A}d_i,\qquad \operatorname{cut}(A,B)=\sum_{\substack{i\in A\\j\in B}}w_{ij}.$$

体积把内部边计两次、跨界边计一次：

$$\operatorname{vol}(A) =2\sum_{\substack{i<j\\i,j\in A}}w_{ij}+\operatorname{cut}(A,B).$$

把每个度数和按邻点在 $A$ 内外分开，便得到此式。它不是仅数与 $A$ 相接的边。写 $a=\operatorname{vol}(A)>0$、$b=\operatorname{vol}(B)>0$，归一化割值定义为

$$\operatorname{Ncut}(A,B) =\operatorname{cut}(A,B)\left(\frac1a+\frac1b\right).$$

这个指标有精确二次型表示。定义两级函数

$$f_i=\begin{cases}1/a,&i\in A,\\-1/b,&i\in B.\end{cases}$$

其度数加权平均和平方范数为

$$f^TD\mathbf1=1-1=0,\qquad f^TDf=\frac1a+\frac1b.$$

只有跨界边对能量有贡献，所以

$$f^TLf=\operatorname{cut}(A,B)\left(\frac1a+\frac1b\right)^2.$$

以能量除以正的平方范数，证得

$$\frac{f^TLf}{f^TDf}=\operatorname{Ncut}(A,B).$$

要放松 $f$ 只能取这两个值的限制，令 $x=D^{1/2}f$，则

$$x^TNx=f^TLf,\qquad x^Tx=f^TDf,\qquad x^T\sqrt d=f^TD\mathbf1=0,$$

其中 $\sqrt d=(\sqrt{d_1},\ldots,\sqrt{d_n})^T$。连通图的 $N$ 恰有由 $\sqrt d$ 张成的一维核。先取其归一化核向量，再如第2节般把正交补对角化。若特征值依序为 $0=\mu_1<\mu_2\le\cdots\le\mu_n$，在该正交归一特征基展开便证得

$$\mu_2=\min_{\substack{x\ne0\\x^T\sqrt d=0}} \frac{x^TNx}{x^Tx} \le\min_{\varnothing\ne A\subsetneq V}\operatorname{Ncut}(A,V\setminus A).$$

非空真子集只有有限个，所以割的最小值存在。不等式成立是因为每个由指示函数所得的向量，都是连续问题的可行竞争者。松弛可行集还有很多其他向量，因此不必取等号。第4题给出严格差距。符号或排序阈值程序是额外的离散化选择；这里没有证明它的一般精确割或近似保证。

图若有孤立点，某一侧可能体积为零，使此商没有定义。第3节的活跃归一化矩阵仍存在，却不会因此替零分母指派值。归一化割定理特意使用连通且正度数的支撑。

7. 常见解读错误

零特征值记录分量常值信号，不代表唯一且有信息的坐标；支撑不连通便有多个零模。孤立点不能按度数取逆，而把其零区块暗改为一，会改变归一化算子。

$P$ 的欧氏对称性强于加权恒等式 $DP=P^TD$。同样，细致平衡与平稳向量不保证从每个起点收敛。二点例子把这些区别都保持为有限而精确的计算。

最后，坐标符号任意，重特征值则要求留意保留子空间。即使子空间已确定，基底仍可旋转；重值若跨越截断边界，子空间本身也可改变。若不检查这些选择便比较绘图轴，可能把代数不唯一性误当成资料改变。

8. 题目与完整解答

Question 1

四个顶点的权重为 $w_{12}=1$、$w_{23}=2$，其他非对角权重均零。求度数、拉普拉斯矩阵、分量、核与完整未归一化谱。求可处理孤立点的归一化谱及一组正交归一特征基，再求活跃转移矩阵与度数平稳分布。解释为何活跃均匀分布及全矩阵 $I_4-RWR$ 都不符合所述结论或约定。

Solution. 对称性给出反向边权。矩阵为

$$W=\begin{pmatrix}0&1&0&0\\1&0&2&0\\0&2&0&0\\0&0&0&0\end{pmatrix},\qquad D=\operatorname{diag}(1,3,2,0),\qquad L=\begin{pmatrix}1&-1&0&0\\-1&3&-2&0\\0&-2&2&0\\0&0&0&0\end{pmatrix}.$$

两个分量为 $\{1,2,3\}$ 与 $\{4\}$，故核由 $(1,1,1,0)^T$ 及 $e_4$ 张成。为计算其余特征值而非凭图猜测，令 $L_3$ 为左上三阶区块。展开三对角行列式得

$$\begin{aligned} \det(tI-L_3) &=(t-1)\bigl((t-3)(t-2)-4\bigr)-(t-2)\\ &=t(t^2-6t+6). \end{aligned}$$

孤立零区块再给一个因子 $t$，故完整谱（包括重数）为 $0,0,3-\sqrt3,3+\sqrt3$。

活跃集上的归一化矩阵是

$$N_3=\begin{pmatrix} 1&-1/\sqrt3&0\\ -1/\sqrt3&1&-\sqrt{2/3}\\ 0&-\sqrt{2/3}&1 \end{pmatrix}.$$

直接相乘得到正交归一特征基

$$u_0=\frac{(1,\sqrt3,\sqrt2)^T}{\sqrt6},\qquad u_1=\frac{(\sqrt2,0,-1)^T}{\sqrt3},\qquad u_2=\frac{(1,-\sqrt3,\sqrt2)^T}{\sqrt6},$$

对应特征值依次为 $0,1,2$。分子的平方范数依次为 $6,3,6$，彼此点积为零，核实了归一化与独立性。给这三列加上第四个零元素，再加 $e_4$，便成为全矩阵 $N$ 的正交归一特征基，其谱为 $0,0,1,2$。

因 $R_{44}=0$，矩阵 $I_4-RWR$ 把 $e_4$ 送到 $e_4$，会把孤立特征值由零换成一；其活跃区块相同，孤立点约定却不同。

顶点 $1,2,3$ 上的转移矩阵与平稳概率列向量为

$$P=\begin{pmatrix}0&1&0\\1/3&0&2/3\\0&1&0\end{pmatrix},\qquad \pi=\frac16\begin{pmatrix}1\\3\\2\end{pmatrix}.$$

直接相乘或使用度数恒等式，均得 $\pi^TP=(1,3,2)/6$。相反，均匀行向量 $(1/3,1/3,1/3)$ 变成 $(1/9,2/3,2/9)$，并不平稳。又 $P_{12}=1$ 而 $P_{21}=1/3$，所以 $P$ 不欧氏对称；正确的对称性是 $D_3P=P^TD_3$。此活跃构造没有定义第四个孤立转移行，故既不使用四顶点度数逆矩阵，也不由这种逆矩阵指派概率质量。

Question 2

对三顶点无权完全图，解一维与二维坐标的最小迹问题。比较两个一维选择

$$u=\frac{(1,-1,0)^T}{\sqrt2},\qquad v=\frac{(1,1,-2)^T}{\sqrt6}.$$

计算各自三对坐标的平方距离，判断是否所有极小坐标都有相同距离。保留整个二维中心空间时，证明任意两个正交归一坐标矩阵以正交变换相连，并计算其成对行坐标平方距离。

Solution. 每个顶点度数为二，邻接矩阵是 $J-I$，其中 $J=\mathbf1\mathbf1^T$，所以 $L=3I-J$。常数列向量有特征值零；每个中心化列向量 $f$ 都满足 $Jf=0$ 及 $Lf=3f$，故谱为 $0,3,3$。两个给定列向量均中心化且为单位长，因此每个一维可行目标均为三，它们都是极小解。

对 $u$，按 $12,13,23$ 排列的平方距离为

$$(\sqrt2)^2=2,\qquad (1/\sqrt2)^2=1/2,\qquad(-1/\sqrt2)^2=1/2.$$

对 $v$ 则为

$$0,\qquad (3/\sqrt6)^2=3/2,\qquad (3/\sqrt6)^2=3/2.$$

两组距离不同。一维正交变换只能把所有坐标同乘 $1$ 或 $-1$，不会改变距离，因此这两个极小解不是如此相连。重特征值容许在二维中心特征空间内选不同的一维子空间。

$k=2$ 时每个可行列空间都是整个 $\mathbf1^\perp$，最小值为 $3+3=6$，正交投影是 $H=I-J/3$。若 $U,V$ 为任意两个可行矩阵，令 $Q=U^TV$，则 $UQ=UU^TV=HV=V$，且 $Q^TQ=V^THV=I_2$，确实得到把两组坐标相连的正交矩阵。两者的 Gram 矩阵为 $UU^T=VV^T=H$。对不同 $i,j$，行坐标平方距离是

$$H_{ii}+H_{jj}-2H_{ij}=\frac23+\frac23-2\left(-\frac13\right)=2.$$

保留整个重特征空间固定了子空间与全部距离；在它之中截断则不然。这些结论关于明确的图能量约束，并未指定另一张 MDS 距离表。

Question 3

两个顶点由一条权为 $a>0$ 的边相连。推导活跃转移矩阵、平稳分布与归一化特征值。从点质量出发，计算每个时刻的分布并判断是否收敛。另解释第1题的加权路径转移矩阵不对称，为何不违反可逆性。对全零图，度数公式究竟定义了什么？

Solution. 此处 $D=aI_2$，$W=a\begin{pmatrix}0&1\\1&0\end{pmatrix}$，所以

$$P=\begin{pmatrix}0&1\\1&0\end{pmatrix},\qquad \pi=\begin{pmatrix}1/2\\1/2\end{pmatrix},\qquad N=\begin{pmatrix}1&-1\\-1&1\end{pmatrix}.$$

列向量 $(1,1)^T/\sqrt2$ 与 $(1,-1)^T/\sqrt2$ 的归一化特征值为 $0,2$，对应转移特征值 $1,-1$。因 $P^2=I_2$，归纳得对每个整数 $m\ge0$，$P^{2m}=I_2$、$P^{2m+1}=P$。从概率列向量 $r_0=e_1$ 出发，注意此特例 $P^T=P$，得到 $r_{2m}=e_1$、$r_{2m+1}=e_2$。第一坐标有值恒为一与恒为零的两个子序列，所以没有极限。然而平稳列向量仍满足 $P^T\pi=\pi$；以相同权重平均两个起始状态便消去交替分量。

第1题的路径有 $D_3=\operatorname{diag}(1,3,2)$，直接相乘得

$$D_3P=\begin{pmatrix}0&1&0\\1&0&2\\0&2&0\end{pmatrix}=P^TD_3.$$

这是在另一个正内积下自伴，而非普通矩阵对称。细致平衡使用 $\pi_iP_{ij}=\pi_jP_{ji}$，所以不相等的一步概率由不相等的平稳质量平衡。概率列向量按 $P^T$ 更新；$Pf$ 则取函数的条件期望。两者在二点特例中碰巧是同一矩阵，在加权路径则不是。

若所有权重为零，所有度数及总体积均为零，活跃集为空。零延拓归一化拉普拉斯矩阵是零矩阵，但 $D^{-1}W$ 与 $d/\sum\limits_i d_i$ 都不是有定义的全空间公式。零列向量的元素和为零，也不是概率分布。把孤立状态设为吸收态会是额外转移约定，并非此构造的结论。

Question 4

对无权路径 $1-2-3-4$，计算归一化谱，并核实

$$f=(1,1/2,-1/2,-1)^T$$

是满足 $Lf=(1/2)Df$ 的广义特征函数。计算互换两侧视为相同后的全部归一化割值，比较精确最优值与谱松弛，并求中央割的两级指示商。

Solution. 度数矩阵与拉普拉斯矩阵为

$$D=\operatorname{diag}(1,2,2,1),\qquad L=\begin{pmatrix}1&-1&0&0\\-1&2&-1&0\\0&-1&2&-1\\0&0&-1&1\end{pmatrix}.$$

四个列向量

$$f_0=(1,1,1,1)^T,\quad f_{1/2}=(1,1/2,-1/2,-1)^T,\quad f_{3/2}=(1,-1/2,-1/2,1)^T,\quad f_2=(1,-1,1,-1)^T$$

满足 $Lf_\mu=\mu Df_\mu$，可逐项相乘核实。例如 $Lf_{1/2}=(1/2,1/2,-1/2,-1/2)^T=(1/2)Df_{1/2}$。其度数加权平方范数依次为 $6,3,3,6$。乘以 $D^{1/2}$ 再除以相应正范数平方根，便得到 $N$ 的单位特征向量。不同特征值使它们正交：对称 $N$ 给 $x^TNy$ 的两个表示，故 $(\mu_y-\mu_x)x^Ty=0$。因此四个向量独立，穷尽四维，归一化谱恰为 $0,1/2,3/2,2$。

给定的 $f$ 是 $f_{1/2}$，加权平均为 $1+1-1-1=0$，加权平方范数为三。其 Rayleigh 商为 $1/2$，故达到松弛最小值。

无序的非平凡割有七个，因为两侧恰有一侧包含顶点一，选它作 $A$ 即可；总体积为六。每条跨界路径边权为一，直接列举得

最小离散值为 $2/3$，由 $\{1,2\}\mid\{3,4\}$ 达到。这个割的两级函数为 $g=(1/3,1/3,-1/3,-1/3)^T$。只有中央边贡献能量，故 $g^TLg=(2/3)^2=4/9$；而 $g^TDg=6/9=2/3$，两者比值为 $2/3$，直接验证了指示公式。

我们得到严格不等式

$$\mu_2=\frac12<\frac23=\min_A\operatorname{Ncut}(A,V\setminus A).$$

松弛极小解取四个不同值，割函数则只取两个值。符号阈值在此例恰好找出最优中央割，但这既不消除严格目标差距，也不证明阈值离散化的一般保证。