置换矩阵是一种方矩阵,其元素均为0或1,且每行每列恰有一个1。它将有限集合上的置换表示为重新排列坐标的线性变换。用置换矩阵左乘或右乘一个矩阵,可以重新排列其行或列,而不改变其中的元素。置换矩阵将线性代数与组合数学、群论联系起来,广泛应用于数值计算、图算法和优化。
定义与约定
设 σ 是 {1,…,n} 上的一个置换,e1,…,en 为标准坐标向量。其置换矩阵 Pσ 定义为
Pσej=eσ(j).
等价地,
(Pσ)ij={1,0,i=σ(j),i=σ(j).
因此,第 j 列为向量 eσ(j)。每个 n×n 置换矩阵都唯一确定一个置换,所以这样的矩阵共有 n! 个。
对于列向量 x,有
(Pσx)i=xσ−1(i).
这里出现逆置换,是因为原来位于位置 j 的坐标移到了位置 σ(j)。
有些文献采用另一种定义:将与 σ 对应的矩阵中的1放在第 i 行、第 σ(i) 列。按这种约定得到的矩阵,是本文所定义矩阵的转置。两种约定描述的是同一类矩阵,但涉及复合和坐标移动的公式取决于所采用的约定。
示例
对于循环 σ=(123),即 1↦2、2↦3、3↦1,有
Pσ=010001100.
因此,
Pσx1x2x3=x3x1x2.
单位矩阵是保持所有位置不变的置换所对应的置换矩阵。
行置换与列置换
对于 n×m 矩阵 A,用 n×n 置换矩阵左乘可得
(PσA)ij=Aσ−1(i),j.
因此,A 的第 j 行移到了第 σ(j) 行。
对于 m×n 矩阵 A,右乘置换矩阵可得
(APσ)ij=Ai,σ(j).
因此,APσ 的第 j 列是 A 的第 σ(j) 列。从原有列的移动来看,第 k 列移到了位置 σ−1(k)。
这两个公式区分了两种操作,而这两种操作有时都会被含糊地称为“应用置换”。如果要将原来的第 j 列移到位置 σ(j),应采用乘积 APσT。
当 A 为方阵时,
B=PσAPσT
会同时重新排列行和列:
Bσ(i),σ(j)=Aij.
这是一个相似变换,对应于对坐标重新编号。
代数性质
转置、逆与正交性
置换矩阵的各列是互不相同的标准坐标向量,因此构成一组标准正交基。于是,
PTP=PPT=I.
特别地,每个置换矩阵都是正交矩阵,其逆矩阵就是其转置:
Pσ−1=PσT=Pσ−1.
置换矩阵保持欧几里得长度和内积不变。更一般地,由于它们只是重新排列坐标,因此会保持所有标准坐标 ℓp 范数不变,包括最大值范数。
置换矩阵对称,当且仅当其对应的置换等于自身的逆置换:
Pσ=PσT⟺σ2=id.
这样的置换仅由不动点和互不相交的对换组成。
乘法与对称群
采用函数复合的约定
(σ∘τ)(j)=σ(τ(j)),则有
PσPτ=Pσ∘τ.
因此,所有 n×n 置换矩阵在矩阵乘法下构成一个群,与对称群 Sn 同构。这一构造给出了 Sn 的一个忠实表示:不同的置换对应不同的线性变换。
若 σ 的互不相交循环的长度为 ℓ1,…,ℓc,则使 Pσr=I 成立的最小正整数 r 为
r=lcm(ℓ1,…,ℓc).
行列式与迹
置换矩阵的行列式等于其对应置换的符号:
det(Pσ)=sgn(σ)∈{1,−1}.
若 σ 有 c 个互不相交的循环,其中不动点计为长度为1的循环,则
det(Pσ)=(−1)n−c.
矩阵的迹等于不动点的个数:
tr(Pσ)=#{i:σ(i)=i}.
上述结论针对实数域或复数域上的置换矩阵。同样的0–1构造也适用于其他域,不过在特征为2的域中,标量 1 与 −1 相同。
循环结构与特征值
对坐标基重新排序,将每个循环中的元素归在一起,就能把置换矩阵化为分块对角形式,每个循环对应一个块。
长度为 ℓ 的循环对应的特征多项式为
因此,若各循环的长度为 ℓ1,…,ℓc,则
det(tI−Pσ)=r=1∏c(tℓr−1).
在复数域上,其特征值均为单位根。每个长度为 ℓ 的循环贡献以下特征值:
e2πik/ℓ,k=0,…,ℓ−1.
每个置换矩阵在复数域上都可对角化,但在实数域上不一定可对角化,因为某些特征值可能不是实数。
特征值1的重数等于循环的个数。其对应的特征向量恰为在每个循环内各坐标取值相同的非零向量。特别地,全1向量总满足
Pσ1=1.
双随机矩阵与指派问题
双随机矩阵是元素均为非负实数、每行与每列的元素之和均为1的方阵。每个置换矩阵都是双随机矩阵,但一般的双随机矩阵可以含有非整数元素。
伯克霍夫–冯·诺伊曼定理指出,每个双随机矩阵都可表示为置换矩阵的凸组合:
D=r=1∑NαrPr,αr≥0,r=1∑Nαr=1.
等价地,置换矩阵恰好是双随机矩阵集合的极点。
这一结果是指派问题的理论基础。将 n 名工人分别指派给 n 项任务,每人恰好负责一项任务且每项任务恰好由一人负责,可以用置换矩阵 X 表示。设指派成本为 cij,则目标为
Xmini=1∑nj=1∑ncijXij.
将条件 Xij∈{0,1} 放宽为非负性,同时保留每行与每列元素之和均为1的条件,就得到一个具有相同最优值的线性规划问题。总存在一个最优的置换矩阵,不过当多个方案的成本相同时,含非整数元素的矩阵也可能是最优解。
计算应用
数值线性代数
置换矩阵用于记录选主元和重新排序的操作。在采用行选主元的高斯消元法中,LU分解的一种常见形式为
其中,P 记录行交换,L 为下三角矩阵,U 为上三角矩阵。不同文献的约定有所不同:写成 A=PLU 的分解可能采用逆置换。
对于稀疏矩阵,行和列的重新排序会显著影响存储需求,以及分解过程中新增的非零元素数量。置换改变的是元素的排列,而不是元素本身。
软件通常将置换存储为索引数组,而不是稠密矩阵。将置换应用于向量需要 O(n) 次索引操作;应用于矩阵时,则通过重新排列行或列实现,而不是使用一般的矩阵乘法。
图的重新标号
若 A 是一个图的邻接矩阵,则
是同一个图在顶点重新标号后的邻接矩阵。两个顶点数相同的有限图同构,当且仅当存在某个置换矩阵,使它们的邻接矩阵满足上述关系。
置换相似保持特征值不变,但仅凭邻接谱相同,并不能判定两个图同构。
相关矩阵类别
部分置换矩阵的元素属于 {0,1},且每行每列至多有一个1。它可以是矩形矩阵,可用于描述不完全的一一指派。
带符号置换矩阵将置换矩阵中的各个1分别替换为独立选取的 1 或 −1。这样的矩阵仍然是正交矩阵,但除了改变坐标位置外,还可以改变坐标的符号。
单项矩阵的每行每列恰有一个非零元素,这些非零元素不一定等于1。它将坐标置换与各坐标独立的非零缩放结合起来。与置换矩阵不同,一般的单项矩阵不一定保持长度不变。