排列矩陣

在數學中的矩陣論裡，**置換矩陣**（英語：**permutation matrix**）是一種係數只由 0 和 1 組成的方塊矩陣。置換矩陣的每一行和每一列都恰好有一個 1，其餘元素都是 0。在線性代數中，每個 _n_ 階的置換矩陣都代表了一個對 _n_ 個元素（_n_ 維空間的基）的置換。當一個矩陣乘上一個置換矩陣時，所得到的是原來矩陣的橫行（置換矩陣在左）或縱列（置換矩陣在右）經過置換後得到的矩陣。

## 嚴格定義

每個 _n_ 元置換都對應著唯一的一個置換矩陣。設 π 為一個 _n_ 元置換：

　
: $\pi :\lbrace 1,\ldots ,n\rbrace \to \lbrace 1,\ldots ,n\rbrace $

給出其映射圖：

　
: ${\begin{bmatrix}1&2&\cdots &n\\\pi (1)&\pi (2)&\cdots &\pi (n)\end{bmatrix}}$

它對應的 _n × n_ 的置換矩陣 _P_π 是：在第 _i_ 橫行只有 π(_i_) 位置上係數為 1，其餘為 0。即可以寫做：

　
: $P_{\pi }={\begin{bmatrix}\mathbf {e} _{\pi (1)}\\\mathbf {e} _{\pi (2)}\\\vdots \\\mathbf {e} _{\pi (n)}\end{bmatrix}}$

其中每個 $\mathbf {e} _{j}$ 表示正則基中的第 _j_ 個，也就是一個左起第 _j_ 個元素為 1，其餘都是 0 的 _n_ 元橫排數組。

由於單位矩陣是

　
: $I={\begin{bmatrix}\mathbf {e} _{1}\\\mathbf {e} _{2}\\\vdots \\\mathbf {e} _{n}\end{bmatrix}}$

置換矩陣也可以定義為單位矩陣的某些行和列交換後得到的矩陣。

## 性質

對兩個 _n_ 元置換 π 和 σ 的置換矩陣 _P_π 和 _P_σ，有

　
: $P_{\pi }P_{\sigma }=P_{\sigma \circ \pi }$

一個置換矩陣 _P_π 必然是正交矩陣（即滿足 $P_{\pi }P_{\pi }^{T}=I$ ），並且它的逆也是置換矩陣：

　
: $P_{\pi }^{-1}=P_{\pi ^{-1}}=P_{\pi }^{T}$

用置換矩陣 $P_{\pi }$ 右乘一個列向量 **g** 所得到的是 **g** 的係數經過置換後的向量：

　
: $P_{\pi }\mathbf {g} ={\begin{bmatrix}\mathbf {e} _{\pi (1)}\\\mathbf {e} _{\pi (2)}\\\vdots \\\mathbf {e} _{\pi (n)}\end{bmatrix}}{\begin{bmatrix}g_{1}\\g_{2}\\\vdots \\g_{n}\end{bmatrix}}={\begin{bmatrix}g_{\pi (1)}\\g_{\pi (2)}\\\vdots \\g_{\pi (n)}\end{bmatrix}}.$

用置換矩陣 $P_{\pi }$ 左乘一個行向量 **h** 所得到的是 **h** 的係數經過置換後的向量：

　
: $\mathbf {h} P_{\pi }={\begin{bmatrix}h_{1}\;h_{2}\;\dots \;h_{n}\end{bmatrix}}{\begin{bmatrix}\mathbf {e} _{\pi (1)}\\\mathbf {e} _{\pi (2)}\\\vdots \\\mathbf {e} _{\pi (n)}\end{bmatrix}}={\begin{bmatrix}h_{\pi ^{-1}(1)}\;h_{\pi ^{-1}(2)}\;\dots \;h_{\pi ^{-1}(n)}\end{bmatrix}}$

## 置換矩陣與置換

設 _Sn_ 是 n 次對稱群，由於 _n_ 置換一共有 _n_! 個，_n_ 階的置換矩陣也有 _n_! 個。這 _n_! 個置換矩陣構成一個關於矩陣乘法的群。這個群的單位元就是單位矩陣。設 _A_ 是所有 _n_ 階的置換矩陣的集合。映射 _S_n → A ⊂ GL(_n_, **Z**2) 是一個群的忠實表示。

對一個置換 σ，其對應的置換矩陣 _P_σ 是將單位矩陣的橫行進行 σ 置換，或者將單位矩陣的橫行進行 σ−1 置換得到的矩陣。

置換矩陣是雙隨機矩陣的一種。伯克霍夫 - 馮・諾伊曼定理說明每個雙隨機矩陣都是同階的置換矩陣的凸組合，並且所有的置換矩陣構成了雙隨機矩陣集合的所有端點。

置換矩陣 _P_σ 的跡數等於相應置換 σ 的不動點的個數。設 _a_1、_a_2、……、_a_k 為其不動點的序號，則_**e**_a1、_**e**_a2、……、_**e**_ak 是 _P_σ 的特徵向量。

由群論可以知道，每個置換都可以寫成若干個對換的複合。由此可知，置換矩陣 _P_σ 都可以寫成若干個表示兩行交換的初等矩陣的乘積。_P_σ 的行列式就等於 σ 的符號差。

## 例子

對應於置換 π = (1 4 2 5 3) 的置換矩陣 _P_π 是

　
: $P_{\pi }={\begin{bmatrix}\mathbf {e} _{\pi (1)}\\\mathbf {e} _{\pi (2)}\\\mathbf {e} _{\pi (3)}\\\mathbf {e} _{\pi (4)}\\\mathbf {e} _{\pi (5)}\end{bmatrix}}={\begin{bmatrix}\mathbf {e} _{1}\\\mathbf {e} _{4}\\\mathbf {e} _{2}\\\mathbf {e} _{5}\\\mathbf {e} _{3}\end{bmatrix}}={\begin{bmatrix}1&0&0&0&0\\0&0&0&1&0\\0&1&0&0&0\\0&0&0&0&1\\0&0&1&0&0\end{bmatrix}}.$

給定一個向量 **g**，

　
: $P_{\pi }\mathbf {g} ={\begin{bmatrix}\mathbf {e} _{\pi (1)}\\\mathbf {e} _{\pi (2)}\\\mathbf {e} _{\pi (3)}\\\mathbf {e} _{\pi (4)}\\\mathbf {e} _{\pi (5)}\end{bmatrix}}{\begin{bmatrix}g_{1}\\g_{2}\\g_{3}\\g_{4}\\g_{5}\end{bmatrix}}={\begin{bmatrix}g_{1}\\g_{4}\\g_{2}\\g_{5}\\g_{3}\end{bmatrix}}.$

## 推廣

置換矩陣概念的一個推廣是將方陣的情況推廣到一般矩陣的情況：

　
: 一個 _m_×_n_ 的 0-1 矩陣 _P_ 是置換矩陣若且唯若 $P\cdot P^{T}=I_{m}$

這時一個 0-1 矩陣是置換矩陣若且唯若它的每一行恰有一個 1，每一列至多有一個 1。

置換矩陣概念的另一個推廣是將每行的 1 變為一個非零的實數：

　
: 一個 _n_ 階的方塊矩陣 _P_ 是置換矩陣若且唯若其每一行與每一列都恰好只有一個係數不為零。

這時的置換矩陣 _P_ 可以看做由 0 和 1 組成的置換矩陣 _Q_ 與一個對角矩陣相乘的結果。

## 參見

* 變號矩陣
* 廣義置換矩陣

## 參考資料

* 張賢達。矩阵分析与应用。清華大學出版社. 2004 （中文（中國大陸））.

## 外部連結

* 左光紀，置換矩陣的組合合成及其圖表示
* 0-1 矩陣與置換矩陣
* 置換矩陣（英文）
* 置換矩陣介紹（英文）