线性代数复习：置换矩阵和“名次向量”

2 min704 words
Legacy
Contents

没事瞎水博客系列……

在日常处理矩阵的时候，有时我们希望在不更改矩阵的前提下获知其每一行/列的字典序“名次”（rank）。MATLAB/NumPy 分别提供了sortrows/argsort方法来获得一个“索引向量”（index vector），表示排序后的矩阵的每一行/列对应原矩阵的行/列号。只需对索引向量再做一次排序，便可得到对应的”名次向量“（rank vector）。对应 MATLAB 代码大致如下：

[~, index] = sortrows(matrix);
[~, rank] = sort(index);

为了深入理解这个操作背后的原理，我参考了 StackExchange 上的这篇回答。从他的证明过程中我发现了一个关键：排序前后两个矩阵的关系可以用排列/置换（permutation）来刻画。下面我将站在线性代数的视角来系统化解释一下“名次向量”背后的原理。

Rank 在线性代数中本来指代矩阵的秩，但该单词同时也具备“名次”这个义项。“索引向量”和“名次向量”仅为英文直译结果，暂时还没有想到/发现更好的称呼。

置换和置换矩阵

在我的这篇博客中有简要提到置换这个概念。一般地，一个 nn 阶的置换可以刻画成 {1,2,…,n}\{1, 2, \dots, n\} 到自身的一个双射，这里记作 σ\sigma。其映射图为：

[12⋯nσ(1)σ(2)⋯σ(n)]\begin{bmatrix} 1 & 2 & \cdots & n\\ \sigma(1) & \sigma(2) & \cdots & \sigma(n) \end{bmatrix}

写成矩阵的形式就是：

Pσ=[eσ(1)eσ(2)⋯eσ(n)]P_\sigma = \begin{bmatrix} \mathbf{e}_{\sigma(1)} & \mathbf{e}_{\sigma(2)} & \cdots & \mathbf{e}_{\sigma(n)} \end{bmatrix}

其中 PσP_\sigma 表示 σ\sigma 对应的置换矩阵，ei\mathbf{e}_i 表示 Rn\mathbb{R}^n 中第 ii 个正交基，即只有第 ii 个元素为 11，其余均为 00 的列向量，i=1,2,…,ni = 1, 2, \dots, n。

观察置换矩阵的构成，显然它是正交的，即有 PσT=Pσ−1P_\sigma^T = P_\sigma^{-1}（矩阵的逆等于其转置）。同时，置换矩阵的转置也是置换矩阵。

所有 nn 阶置换在复合运算上构成一个置换群（或 nn 次对称群）。

置换和排序

矩阵按行/列排序，本质上可以视作一个行/列变换。下面仅讨论矩阵的列变换。

令 MM 为一 m×nm \times n 矩阵，M(s)M^{(s)} 为其列排序后的结果，则该排序过程可以视作在列向量上的一个置换作用。即，存在一个 nn 阶置换 σ\sigma 使得 M(s)=M⋅PσM^{(s)} = M \cdot P_\sigma。若我们事先已知 MM 的列的大小关系，并按从小到大顺序赋值 1,2,…,n1, 2, \dots, n，则可以得到一个行向量 rM\mathbf{r}_M，记作 MM 的“名次向量”。显然我们有：

rM⋅Pσ=[12⋯n]\mathbf{r}_M \cdot P_\sigma = \begin{bmatrix} 1 & 2 & \cdots & n \end{bmatrix}

即：

rM=[σ−1(1)σ−1(2)⋯σ−1(n)]\mathbf{r}_M = \begin{bmatrix} \sigma^{-1}(1) & \sigma^{-1}(2) & \cdots & \sigma^{-1}(n) \end{bmatrix}

由于 ∀1≤i,j≤n, Mi,j(s)=Mi,σ(j)\forall 1 \leq i, j \leq n,\ M^{(s)}_{i, j} = M_{i, \sigma(j)}，其中 Mi,jM_{i, j} 代表矩阵 MM 第 ii 行第 jj 列的元素，我们记 iM\mathbf{i}_M 为 MM 的“索引向量”，其值为：

iM=[12⋯n]⋅Pσ=[σ(1)σ(2)⋯σ(n)]\begin{align*} \mathbf{i}_M &= \begin{bmatrix} 1 & 2 & \cdots & n \end{bmatrix} \cdot P_\sigma\\ &= \begin{bmatrix} \sigma(1) & \sigma(2) & \cdots & \sigma(n) \end{bmatrix} \end{align*}

从“索引”到“名次”

现在对 iM\mathbf{i}_M 进行排序，其对应的置换记作 π\pi，则有：

iM⋅Pπ=[12⋯n]\mathbf{i}_M \cdot P_\pi = \begin{bmatrix} 1 & 2 & \cdots & n \end{bmatrix}

又因为：

riM⋅Pπ=[12⋯n]\mathbf{r}_{\mathbf{i}_M} \cdot P_\pi = \begin{bmatrix} 1 & 2 & \cdots & n \end{bmatrix}

所以有：

iM=riM[σ(1)σ(2)⋯σ(n)]=[π−1(1)π−1(2)⋯π−1(n)]\begin{align*} \mathbf{i}_M &= \mathbf{r}_{\mathbf{i}_M}\\ \begin{bmatrix} \sigma(1) & \sigma(2) & \cdots & \sigma(n) \end{bmatrix} &= \begin{bmatrix} \pi^{-1}(1) & \pi^{-1}(2) & \cdots & \pi^{-1}(n) \end{bmatrix} \end{align*}

因此 σ=π−1\sigma = \pi^{-1}，即 σ\sigma 和 π\pi 互逆，于是有：

iiM=[π(1)π(2)⋯π(n)]=[σ−1(1)σ−1(2)⋯σ−1(n)]=rM\begin{align*} \mathbf{i}_{\mathbf{i}_M} &= \begin{bmatrix} \pi(1) & \pi(2) & \cdots & \pi(n) \end{bmatrix}\\ &= \begin{bmatrix} \sigma^{-1}(1) & \sigma^{-1}(2) & \cdots & \sigma^{-1}(n) \end{bmatrix}\\ &= \mathbf{r}_M \end{align*}

自此，我们证明了“索引向量的索引向量为原矩阵的名次向量”这一命题。

Contents