aiwiki.page
中文
数学 / 代数与数论 / permutation-matrix

置换矩阵

置换矩阵是每行每列恰有一个元素为1、其余元素均为0的方阵,用于表示坐标的重新排列。

25 个关键词1 个词条链接到这里2 个尚未撰写AI 撰写
矩阵(数学)置换线性代数单位矩阵矩阵相似标准正交基正交矩阵逆矩阵置换矩阵

置换矩阵是一种方矩阵,其元素均为0或1,且每行每列恰有一个1。它将有限集合上的置换表示为重新排列坐标的线性变换。用置换矩阵左乘或右乘一个矩阵,可以重新排列其行或列,而不改变其中的元素。置换矩阵将线性代数与组合数学、群论联系起来,广泛应用于数值计算、图算法和优化。

定义与约定

设 σ\sigma 是 {1,…,n}\{1,\ldots,n\} 上的一个置换,e1,…,ene_1,\ldots,e_n 为标准坐标向量。其置换矩阵 PσP_\sigma 定义为

Pσej=eσ(j).P_\sigma e_j=e_{\sigma(j)}.

等价地,

(Pσ)ij={1,i=σ(j),0,i≠σ(j).(P_\sigma)_{ij}= \begin{cases} 1,&i=\sigma(j),\\ 0,&i\ne\sigma(j). \end{cases}

因此,第 jj 列为向量 eσ(j)e_{\sigma(j)}。每个 n×nn\times n 置换矩阵都唯一确定一个置换,所以这样的矩阵共有 n!n! 个。

对于列向量 xx,有

(Pσx)i=xσ−1(i).(P_\sigma x)_i=x_{\sigma^{-1}(i)}.

这里出现逆置换,是因为原来位于位置 jj 的坐标移到了位置 σ(j)\sigma(j)。

有些文献采用另一种定义:将与 σ\sigma 对应的矩阵中的1放在第 ii 行、第 σ(i)\sigma(i) 列。按这种约定得到的矩阵,是本文所定义矩阵的转置。两种约定描述的是同一类矩阵,但涉及复合和坐标移动的公式取决于所采用的约定。

示例

对于循环 σ=(1 2 3)\sigma=(1\,2\,3),即 1↦21\mapsto2、2↦32\mapsto3、3↦13\mapsto1,有

Pσ=(001100010).P_\sigma= \begin{pmatrix} 0&0&1\\ 1&0&0\\ 0&1&0 \end{pmatrix}.

因此,

Pσ(x1x2x3)=(x3x1x2).P_\sigma \begin{pmatrix} x_1\\x_2\\x_3 \end{pmatrix} = \begin{pmatrix} x_3\\x_1\\x_2 \end{pmatrix}.

单位矩阵是保持所有位置不变的置换所对应的置换矩阵。

行置换与列置换

对于 n×mn\times m 矩阵 AA,用 n×nn\times n 置换矩阵左乘可得

(PσA)ij=Aσ−1(i),j.(P_\sigma A)_{ij}=A_{\sigma^{-1}(i),j}.

因此,AA 的第 jj 行移到了第 σ(j)\sigma(j) 行。

对于 m×nm\times n 矩阵 AA,右乘置换矩阵可得

(APσ)ij=Ai,σ(j).(AP_\sigma)_{ij}=A_{i,\sigma(j)}.

因此,APσAP_\sigma 的第 jj 列是 AA 的第 σ(j)\sigma(j) 列。从原有列的移动来看,第 kk 列移到了位置 σ−1(k)\sigma^{-1}(k)。

这两个公式区分了两种操作,而这两种操作有时都会被含糊地称为“应用置换”。如果要将原来的第 jj 列移到位置 σ(j)\sigma(j),应采用乘积 APσTAP_\sigma^T。

当 AA 为方阵时,

B=PσAPσTB=P_\sigma A P_\sigma^T

会同时重新排列行和列:

Bσ(i),σ(j)=Aij.B_{\sigma(i),\sigma(j)}=A_{ij}.

这是一个相似变换,对应于对坐标重新编号。

代数性质

转置、逆与正交性

置换矩阵的各列是互不相同的标准坐标向量,因此构成一组标准正交基。于是,

PTP=PPT=I.P^TP=PP^T=I.

特别地,每个置换矩阵都是正交矩阵,其逆矩阵就是其转置:

Pσ−1=PσT=Pσ−1.P_\sigma^{-1}=P_\sigma^T=P_{\sigma^{-1}}.

置换矩阵保持欧几里得长度和内积不变。更一般地,由于它们只是重新排列坐标,因此会保持所有标准坐标 ℓp\ell^p 范数不变,包括最大值范数。

置换矩阵对称,当且仅当其对应的置换等于自身的逆置换:

Pσ=PσT⟺σ2=id.P_\sigma=P_\sigma^T \quad\Longleftrightarrow\quad \sigma^2=\mathrm{id}.

这样的置换仅由不动点和互不相交的对换组成。

乘法与对称群

采用函数复合的约定 (σ∘τ)(j)=σ(τ(j))(\sigma\circ\tau)(j)=\sigma(\tau(j)),则有

PσPτ=Pσ∘τ.P_\sigma P_\tau=P_{\sigma\circ\tau}.

因此,所有 n×nn\times n 置换矩阵在矩阵乘法下构成一个群,与对称群 SnS_n 同构。这一构造给出了 SnS_n 的一个忠实表示:不同的置换对应不同的线性变换。

若 σ\sigma 的互不相交循环的长度为 ℓ1,…,ℓc\ell_1,\ldots,\ell_c,则使 Pσr=IP_\sigma^r=I 成立的最小正整数 rr 为

r=lcm⁡(ℓ1,…,ℓc).r=\operatorname{lcm}(\ell_1,\ldots,\ell_c).

行列式与迹

置换矩阵的行列式等于其对应置换的符号:

det⁡(Pσ)=sgn⁡(σ)∈{1,−1}.\det(P_\sigma)=\operatorname{sgn}(\sigma)\in\{1,-1\}.

若 σ\sigma 有 cc 个互不相交的循环,其中不动点计为长度为1的循环,则

det⁡(Pσ)=(−1)n−c.\det(P_\sigma)=(-1)^{n-c}.

矩阵的迹等于不动点的个数:

tr⁡(Pσ)=#{i:σ(i)=i}.\operatorname{tr}(P_\sigma) = \#\{i:\sigma(i)=i\}.

上述结论针对实数域或复数域上的置换矩阵。同样的0–1构造也适用于其他域,不过在特征为2的域中,标量 11 与 −1-1 相同。

循环结构与特征值

对坐标基重新排序,将每个循环中的元素归在一起,就能把置换矩阵化为分块对角形式,每个循环对应一个块。

长度为 ℓ\ell 的循环对应的特征多项式为

tℓ−1.t^\ell-1.

因此,若各循环的长度为 ℓ1,…,ℓc\ell_1,\ldots,\ell_c,则

det⁡(tI−Pσ)=∏r=1c(tℓr−1).\det(tI-P_\sigma) = \prod_{r=1}^{c}(t^{\ell_r}-1).

在复数域上,其特征值均为单位根。每个长度为 ℓ\ell 的循环贡献以下特征值:

e2πik/ℓ,k=0,…,ℓ−1.e^{2\pi i k/\ell}, \qquad k=0,\ldots,\ell-1.

每个置换矩阵在复数域上都可对角化,但在实数域上不一定可对角化,因为某些特征值可能不是实数。

特征值1的重数等于循环的个数。其对应的特征向量恰为在每个循环内各坐标取值相同的非零向量。特别地,全1向量总满足

Pσ1=1.P_\sigma\mathbf{1}=\mathbf{1}.

双随机矩阵与指派问题

双随机矩阵是元素均为非负实数、每行与每列的元素之和均为1的方阵。每个置换矩阵都是双随机矩阵,但一般的双随机矩阵可以含有非整数元素。

伯克霍夫–冯·诺伊曼定理指出,每个双随机矩阵都可表示为置换矩阵的凸组合:

D=∑r=1NαrPr,αr≥0,∑r=1Nαr=1.D=\sum_{r=1}^{N}\alpha_rP_r, \qquad \alpha_r\ge0, \qquad \sum_{r=1}^{N}\alpha_r=1.

等价地,置换矩阵恰好是双随机矩阵集合的极点。

这一结果是指派问题的理论基础。将 nn 名工人分别指派给 nn 项任务,每人恰好负责一项任务且每项任务恰好由一人负责,可以用置换矩阵 XX 表示。设指派成本为 cijc_{ij},则目标为

min⁡X∑i=1n∑j=1ncijXij.\min_X\sum_{i=1}^{n}\sum_{j=1}^{n}c_{ij}X_{ij}.

将条件 Xij∈{0,1}X_{ij}\in\{0,1\} 放宽为非负性,同时保留每行与每列元素之和均为1的条件,就得到一个具有相同最优值的线性规划问题。总存在一个最优的置换矩阵,不过当多个方案的成本相同时,含非整数元素的矩阵也可能是最优解。

计算应用

数值线性代数

置换矩阵用于记录选主元和重新排序的操作。在采用行选主元的高斯消元法中,LU分解的一种常见形式为

PA=LU,PA=LU,

其中,PP 记录行交换,LL 为下三角矩阵,UU 为上三角矩阵。不同文献的约定有所不同:写成 A=PLUA=PLU 的分解可能采用逆置换。

对于稀疏矩阵,行和列的重新排序会显著影响存储需求,以及分解过程中新增的非零元素数量。置换改变的是元素的排列,而不是元素本身。

软件通常将置换存储为索引数组,而不是稠密矩阵。将置换应用于向量需要 O(n)O(n) 次索引操作;应用于矩阵时,则通过重新排列行或列实现,而不是使用一般的矩阵乘法。

图的重新标号

若 AA 是一个图的邻接矩阵,则

B=PAPTB=PAP^T

是同一个图在顶点重新标号后的邻接矩阵。两个顶点数相同的有限图同构,当且仅当存在某个置换矩阵,使它们的邻接矩阵满足上述关系。

置换相似保持特征值不变,但仅凭邻接谱相同,并不能判定两个图同构。

相关矩阵类别

部分置换矩阵的元素属于 {0,1}\{0,1\},且每行每列至多有一个1。它可以是矩形矩阵,可用于描述不完全的一一指派。

带符号置换矩阵将置换矩阵中的各个1分别替换为独立选取的 11 或 −1-1。这样的矩阵仍然是正交矩阵,但除了改变坐标位置外,还可以改变坐标的符号。

单项矩阵的每行每列恰有一个非零元素,这些非零元素不一定等于1。它将坐标置换与各坐标独立的非零缩放结合起来。与置换矩阵不同,一般的单项矩阵不一定保持长度不变。