查看“︁置换矩阵”︁的源代码

{{No reference |time=2019-12-15}}

在[[数学]]中的[[矩阵论]]裡，'''置换矩阵'''（{{lang-en|'''permutation matrix'''}}）是一种系数只由0和1组成的[[方块矩阵]]。置换矩阵的每一行和每一列都恰好有一个1，其余元素都是0。在[[线性代数]]中，每个''n''阶的置换矩阵都代表了一个对''n''个元素（''n''维空间的[[基 (代數)|基]]）的[[置换]]。当一个矩阵乘上一个置换矩阵时，所得到的是原来矩阵的横行（置换矩阵在左）或纵列（置换矩阵在右）经过置换后得到的矩阵。

== 严格定义 ==
每个''n''元置换都对应着唯一的一个置换矩阵。设π 为一个''n''元置换：
:<math>\pi : \lbrace 1, \ldots, n \rbrace \to \lbrace 1, \ldots, n \rbrace</math>
给出其映射图：
:<math>\begin{bmatrix} 1 & 2 & \cdots & n \\ \pi(1) & \pi(2) & \cdots & \pi(n) \end{bmatrix} </math>
它对应的''n × n''的置换矩阵''P''<sub>π</sub>是：在第''i''横行只有π(''i'')位置上系数为1，其余为0。即可以写做：
:<math>P_\pi = \begin{bmatrix} \mathbf e_{\pi(1)} \\ \mathbf e_{\pi(2)} \\ \vdots \\ \mathbf e_{\pi(n)} \end{bmatrix} </math>
其中每个<math>\mathbf e_j</math>表示正则基中的第''j''个，也就是一个左起第''j''个元素为1，其余都是0的''n''元横排数组。

由于[[单位矩阵]]是
:<math>I = \begin{bmatrix} \mathbf e_1 \\ \mathbf e_2 \\ \vdots \\ \mathbf e_n\end{bmatrix}</math>

置换矩阵也可以定义为单位矩阵的某些行和列交换后得到的矩阵。

== 性质 ==

对两个''n''元置换π 和 σ的置换矩阵''P''<sub>π</sub> 和''P''<sub>σ</sub>，有
:<math>P_{\pi} P_{\sigma} = P_{\sigma \circ \pi}</math>

一个置换矩阵''P''<sub>π</sub> 必然是[[正交矩阵]]（即满足<math>P_{\pi}P_{\pi}^{T} = I</math>），并且它的逆也是置换矩阵：
:<math>P_{\pi}^{-1} = P_{\pi^{-1}} = P_{\pi}^{T}</math>

用置换矩阵<math>P_{\pi}</math>右乘一个[[列向量]] '''g'''所得到的是 '''g''' 的系数经过置换后的向量：
:<math>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}.
</math>

用置换矩阵<math>P_{\pi}</math>左乘一个[[行向量]] '''h''' 所得到的是 '''h''' 的系数经过置换后的向量：
:<math>\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}
</math>

== 置换矩阵与置换 ==

设''S<sub>n</sub>''是[[对称群 (n次对称群)|n次对称群]]，由于''n''置换一共有''n''! 个，''n''阶的置换矩阵也有''n''! 个。这''n''! 个置换矩阵构成一个关于矩阵乘法的[[群]]。这个群的[[单位元]]就是单位矩阵。设''A''是所有''n''阶的置换矩阵的集合。映射''S''<sub>''n''</sub> → A ⊂ GL(''n'', '''Z'''<sub>2</sub>)是一个[[群表示|群的忠实表示]]。

对一个置换σ，其对应的置换矩阵''P''<sub>σ</sub>是将单位矩阵的横行进行 σ 置换，或者将单位矩阵的横行进行 σ<sup>−1</sup> 置换得到的矩阵。 

置换矩阵是[[双随机矩阵]]的一种。[[伯克霍夫-冯·诺伊曼定理]]说明每个双随机矩阵都是同阶的置换矩阵的[[凸组合]]，并且所有的置换矩阵构成了双随机矩阵集合的所有[[端点]]。

置换矩阵''P''<sub>σ</sub>的[[迹数]]等于相应置换σ的[[不动点]]的个数。设 ''a''<sub>1</sub>、''a''<sub>2</sub>、……、''a''<sub>''k''</sub> 为其不动点的序号，则'''''e'''''<sub>''a''<sub>1</sub></sub>、'''''e'''''<sub>''a''<sub>2</sub></sub>、……、'''''e'''''<sub>''a''<sub>''k''</sub></sub> 是''P''<sub>σ</sub>的[[特征向量]]。

由群论可以知道，每个置换都可以写成若干个[[对换]]的复合。由此可知，置换矩阵''P''<sub>σ</sub>都可以写成若干个表示两行交换的[[初等矩阵]]的乘积。''P''<sub>σ</sub>的[[行列式]]就等于 σ 的[[符号差]]。

== 例子 ==
对应于置换π = (1 4 2 5 3)的置换矩阵''P''<sub>π</sub> 是
:<math>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}.
</math>

给定一个向量 '''g'''，
:<math>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}.
</math>

== 推广 ==
置换矩阵概念的一个推广是将方阵的情况推广到一般矩阵的情况：
:一个''m''×''n''的[[0-1矩阵]] ''P'' 是置换矩阵当且仅当 <math>P \cdot P^T = I_m</math>

这时一个[[0-1矩阵]]是置换矩阵当且仅当它的每一行恰有一个1，每一列至多有一个1。

置换矩阵概念的另一个推广是将每行的1变为一个非零的实数：
:一个''n''阶的[[方块矩阵]] ''P'' 是置换矩阵当且仅当其每一行与每一列都恰好只有一个系数不为零。

这时的置换矩阵''P''可以看做由0和1组成的置换矩阵''Q''与一个对角矩阵相乘的结果。

== 参见 ==
* [[变号矩阵]]
* [[广义置换矩阵]]

== 参考资料 ==
{{Reflist}}

* {{cite book |author=张贤达 |title=矩阵分析与应用 |publisher=清华大学出版社 |edition= |isbn= |language=zh-cn |year=2004}}

== 外部链接 ==
* [https://web.archive.org/web/20160304100602/http://166.111.121.20:9080/mathjournal/SSYJ200101/ssyj200101017.caj.pdf 左光纪，置换矩阵的组合合成及其图表示]
* [http://courseware.ecnudec.com/zsb/zsx/zsx09/zsx09a/zsx09a01/zsx09a013.htm 0-1矩阵与置换矩阵]{{Dead link|date=2019年6月 |bot=InternetArchiveBot |fix-attempted=yes }}
* [https://web.archive.org/web/20081006200458/http://www.physics.arizona.edu/~restrepo/475A/Notes/sourcea/node67.html 置换矩阵（英文）]
* [https://web.archive.org/web/20080308130542/http://www.brynmawr.edu/math/people/stromquist/math203/PermutationMatrices.doc 置换矩阵介绍（英文）]

{{DEFAULTSORT:permutation matrix}}
[[Category:矩阵]]
[[Category:置换]]