Matrix Tree
Binet-Cauchy
0x00前置
Laplace expansion
将常见的行列式行展开拓展一下，同时展开多行的Laplace展开为：
$ \left|A\right| = \sum_{1\leq j_1\leq j_2\leq \ldots \leq j_k\leq n} A \left( \begin{matrix} i_1 & i_2 & \ldots & i_k\ j_1 & j_2 & \ldots & j_k \end{matrix} \right) \cdot (-1)^{\sum_{t=1}^k i_t+\sum_{t=1}^k j_t}\cdot \left[ \begin{matrix} i_1 & i_2 & \ldots & i_k\ j_1 & j_2 & \ldots & j_k \end{matrix} \right] $
其含义为，取定第\(1\leq i_1\leq \ldots \leq i_k\leq n\)行，\(\det A\) 等于这 \(k\) 行形成的所有 \(k\) 阶子式与它自己的代数余子式的乘积之和.
其中, \(A\left( \begin{matrix} i_1 & i_2 & \ldots & i_k\\ j_1 & j_2 & \ldots & j_k \end{matrix} \right)\)表示\(A\)矩阵保留第\(i_1\ldots i_k\)行，第\(j_1\ldots j_k\)列的子式
\(A\left[ \begin{matrix} i_1 & i_2 & \ldots & i_k\\ j_1 & j_2 & \ldots & j_k \end{matrix} \right]\)表示\(A\)矩阵去除第\(i_1\ldots i_k\)行，第\(j_1\ldots j_k\)列的子式
证明略了，可以上网自学/感性理解一下
0x01描述
$ \left|AB\right| = \sum_{1\leq v_1\leq v_2\leq \ldots \leq v_s\leq n} A\left( \begin{array}{} 1 & 2 & \ldots & s\ v_1 & v_2 & \ldots & v_s \end{array} \right)\cdot B\left( \begin{array}{} v_1 & v_2 & \ldots & v_s\ 1 & 2 & \ldots & s \end{array} \right) $
0x02证明
1. 代数证明
构造一个行列式:$ \left|\begin{matrix} A & 0\ I_n & B\ \end{matrix}\right| $,对其进行初等行变换：
得到\(\left| AB \right|\)相关的形式
接下来计算行列式的值：
固定了矩阵的前\(s\)行，从前\(n\)列中选取任意\(s\)列(\(v_1\cdots v_s\))，进行Laplace展开：
$$ =\sum_{1\leq v_1\leq\cdots\leq v_s\leq n} A\left( \begin{array}{l} 1 & 2 & \cdots & s \\ v_1 & v_2 & \cdots & v_s \end{array}\right) \cdot(-1)^{\sum_s+\sum_{v_s}}\cdot \left|\begin{array}{l} 0 & 0 & \cdots & 0 \\ 1 & 0 & \cdots & 0 \\ 0 & 1 & \cdots & 0 \\ \vdots & \vdots& \ddots& \vdots& B \\ 0 & 0 & \cdots & 1 \end{array}\right| $$ 即可得到我们想要的前半部分.
有注意到剩余行列式中的\(1\)只存在于与\(v_1\cdots v_s\)互补的\(u_1\cdots u_{n-s}\)列中，则固定前\(n-s\)列，选取指定的第\(u_1\cdots u_{n-s}\)行继续展开。
而\(B\)中剩下的行与第\(u_1\cdots u_{n-s}\)行互补，所以剩下的就是第\(v_1\cdots v_s\)行。
整理一下就有
因为\(v_s\)与\(u_{n-s}\)互补，所以他们的和就是\(1+\cdots+n\)
现在有
吧\(-1\)挪到右边，为\((-1)^{s(s+1)+n(n+1)}\),看到\(s(s+1)+n(n+1)\)是偶数，则这一项为\(1\)
最终有:
证毕.
矩阵树定理
Laplacian Matrix
在 局部保留投影 (LPP) 中，核心优化目标是 \(\min \sum_{ij} W_{ij}(y_i - y_j)^2\)，这一项最终被写成了 \(y^T L y\) 的形式。这里的 \(L = D - W\) (或 \(D-A\)) 被称为 图拉普拉斯矩阵 (Graph Laplacian)。
它不仅仅是一个代数工具，它在数学、物理和信号处理中有着极其深刻的物理意义。它本质上是连续空间中 拉普拉斯算子 \(\Delta\) (或 \(\nabla^2\)) 在离散图结构上的推广。
以下是它在不同领域的解释和应用：
1. 组合数学：矩阵树定理 (Matrix Tree Theorem)
这是图论中一个非常优美的定理，揭示了 \(L\) 与图的连通性之间的深层联系。
- 应用：计算图的生成树 (Spanning Trees) 的数量。
- 定理内容：
对于一个无向图 \(G\)，其生成树的总数量等于其拉普拉斯矩阵 \(L\) 的任意一个 余子式 (Cofactor) 的值。
- 具体做法是：去掉 \(L\) 的任意一行和任意一列（例如第 \(i\) 行和第 \(i\) 列），计算剩下矩阵的行列式，结果就是生成树的个数。
- 直觉联系：
- \(L\) 的零空间的维数等于图的连通分量个数。如果图是连通的，\(\text{rank}(L) = n-1\)，这暗示了我们去掉一行一列后矩阵满秩。
- 在 LPP 中，我们要找特征向量。如果图断开了（非连通），\(L\) 会变成块对角矩阵，谱（特征值）分析会告诉我们图是如何断开的。
2. 信号处理：图傅里叶变换 (Graph Fourier Transform, GFT)
这是目前火热的 图神经网络 (GNN/GCN) 的数学基石。
- 背景： 在经典傅里叶分析中，傅里叶变换是将信号投影到 \(e^{i\omega t}\) 上。而 \(e^{i\omega t}\) 实际上是拉普拉斯算子 \(\Delta = \frac{d^2}{dt^2}\) 的特征函数（Eigenfunctions）： $$ \frac{d^2}{dt^2} (e^{i\omega t}) = -\omega^2 (e^{i\omega t}) $$
- 图上的推广： 既然经典频率是 \(\Delta\) 的特征值，那么在图上，\(L\) 的特征值 \(\lambda\) 就是“频率”，\(L\) 的特征向量 \(u\) 就是“基底”（图傅里叶模态）。
- 应用：
- 平滑度 (Smoothness)：对于图上的信号 \(x\)，值 \(x^T L x\) 被称为图总变差 (Graph Total Variation)。
$$ x^T L x = \sum_{i,j} W_{ij} (x_i - x_j)^2 $$
- 低频 (\(\lambda\) 小)：对应的特征向量在相邻节点上数值变化很小（平滑），\(x^T L x\) 很小。LPP 正是保留了这些“低频”分量。
- 高频 (\(\lambda\) 大)：对应的特征向量在相邻节点上数值剧烈跳变。
- 图卷积：两个图信号的卷积，等于它们在“图傅里叶域”的点积。通过对 \(L\) 进行特征分解，我们定义了图卷积网络。
- 平滑度 (Smoothness)：对于图上的信号 \(x\)，值 \(x^T L x\) 被称为图总变差 (Graph Total Variation)。
$$ x^T L x = \sum_{i,j} W_{ij} (x_i - x_j)^2 $$
3. 物理系统：2维弹簧质点系统 (Spring-Mass System)
这是最直观的物理诠释，完美解释了 LPP 为什么要最小化 \(y^T L y\)。
- 模型设定： 想象图中的每个节点是一个质量为 1 的质点，边是连接质点的弹簧。\(W_{ij}\) 是弹簧的劲度系数（stiffness）。
- 势能 (Potential Energy)： 根据胡克定律，如果我们将这些点放置在 1维或 2维空间 \(y\) 中，系统的总弹性势能为： $$ E = \frac{1}{2} \sum_{i,j} W_{ij} |y_i - y_j|^2 = y^T L y $$
- LPP 的物理意义：
- LPP 的目标 \(\min y^T L y\) (在约束下) 实际上是在寻找一种布局，使得整个弹簧系统的总势能最小。
- 这也就是为什么 LPP（以及 Laplacian Eigenmaps）降维后的结果，原本相连的点会靠得很近——因为弹簧把它们拉在了一起。
- 动力学 (Force)： 系统受到的力 \(F = -\nabla E = -L y\)。 如果让系统自由演化（\(\dot{y} = -Ly\)），所有点最终会坍缩到一点（势能为0）。LPP 通过 \(y^T D y = 1\) 的约束“撑住”了这些点，防止它们坍缩，从而在平衡状态下展示出数据的结构。
4. 其他领域的应用
A. 谱聚类 (Spectral Clustering)
- 应用：图像分割、社区发现。
- 原理：\(L\) 的第二小特征值对应的特征向量（Fiedler Vector）提供了图的最优二分切割（Ratio Cut 或 Normalized Cut）的近似解。
- 直觉：切断连接最弱的边（\(W_{ij}\) 小），使得两边的点分别尽可能紧密连接。这与 LPP 寻找低频基底是同一回事。
B. 热传导与扩散 (Heat Equation & Diffusion)
- 应用：信息在网络中的传播、PageRank。
- 方程：\(\frac{\partial u}{\partial t} = - L u\)。
- 解释：\(L\) 描述了流出量（Out-degree）和流入量（Neighbor sum）的差值。 $$ (Lx)i = d_i x_i - \sum (x_i - x_j) $$ 这表示节点 } W_{ij} x_j = \sum_{j \in N(i)} W_{ij\(i\) 的值会根据它与邻居的差值进行更新。如果我比邻居热，我就降温；如果我比邻居冷，我就升温。这正是扩散过程。
C. 分布式一致性 (Consensus Problem)
- 应用：多智能体控制（无人机编队）、分布式计算。
- 原理：如果每个智能体遵循 \(\dot{x}_i = -\sum_j (x_i - x_j)\) 的协议（即 \(\dot{x} = -Lx\)），只要图是连通的，所有智能体最终会收敛到同一个值（初始值的平均值）。\(L\) 的第二小特征值（代数连通度）决定了收敛的速度。
总结
在 LPP 中，使用 \(L = D - A\) 的核心原因是利用其物理上的势能最小化特性（把相似的点拉近）以及信号处理中的低频特性（保持局部平滑）。
- 矩阵树定理 告诉我们要保留图的骨架。
- 图傅里叶 告诉我们 LPP 实际上是一个低通滤波器。
- 弹簧系统 形象地展示了 LPP 是在能量最小化状态下的嵌入。