在數學中的矩陣論裡,置換矩陣(英語:permutation matrix)是一種係數只由0和1組成的方塊矩陣。置換矩陣的每一行和每一列都恰好有一個1,其餘元素都是0。在線性代數中,每個n階的置換矩陣都代表了一個對n個元素(n維空間的基)的置換。當一個矩陣乘上一個置換矩陣時,所得到的是原來矩陣的橫行(置換矩陣在左)或縱列(置換矩陣在右)經過置換後得到的矩陣。
嚴格定義[編輯]
每個n元置換都對應著唯一的一個置換矩陣。設π 為一個n元置換:
![{\displaystyle \pi :\lbrace 1,\ldots ,n\rbrace \to \lbrace 1,\ldots ,n\rbrace }](https://wikimedia.org/api/rest_v1/media/math/render/svg/80150e298427c9e41d677b8d9b5cacba23a3bbee)
給出其映射圖:
![{\displaystyle {\begin{bmatrix}1&2&\cdots &n\\\pi (1)&\pi (2)&\cdots &\pi (n)\end{bmatrix}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/692db7dec0570c501cf0c6703a807271365553a0)
它對應的n × n的置換矩陣Pπ是:在第i橫行只有π(i)位置上係數為1,其餘為0。即可以寫做:
![{\displaystyle P_{\pi }={\begin{bmatrix}\mathbf {e} _{\pi (1)}\\\mathbf {e} _{\pi (2)}\\\vdots \\\mathbf {e} _{\pi (n)}\end{bmatrix}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/19959b737305ce829f3758db0c3917af2bcaf184)
其中每個
表示正則基中的第j個,也就是一個左起第j個元素為1,其餘都是0的n元橫排數組。
由於單位矩陣是
![{\displaystyle I={\begin{bmatrix}\mathbf {e} _{1}\\\mathbf {e} _{2}\\\vdots \\\mathbf {e} _{n}\end{bmatrix}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3fc6a68662744f5e80ca1785317723b4955d8007)
置換矩陣也可以定義為單位矩陣的某些行和列交換後得到的矩陣。
對兩個n元置換π 和 σ的置換矩陣Pπ 和Pσ,有
![{\displaystyle P_{\pi }P_{\sigma }=P_{\sigma \circ \pi }}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5954a01d42652aa7f7a2d5d117fc6fc40021914a)
一個置換矩陣Pπ 必然是正交矩陣(即滿足
),並且它的逆也是置換矩陣:
![{\displaystyle P_{\pi }^{-1}=P_{\pi ^{-1}}=P_{\pi }^{T}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ce14f0f4428cb9710b9793aafc72a25cb757192d)
用置換矩陣
右乘一個列向量 g所得到的是 g 的係數經過置換後的向量:
![{\displaystyle 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}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a44d4d1df073aacd998780c2fd272dfa0c3e240f)
用置換矩陣
左乘一個行向量 h 所得到的是 h 的係數經過置換後的向量:
![{\displaystyle \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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/111f4935b1332047d34310b6c713eab3546b8462)
置換矩陣與置換[編輯]
設Sn是n次對稱群,由於n置換一共有n! 個,n階的置換矩陣也有n! 個。這n! 個置換矩陣構成一個關於矩陣乘法的群。這個群的單位元就是單位矩陣。設A是所有n階的置換矩陣的集合。映射Sn → A ⊂ GL(n, Z2)是一個群的忠實表示。
對一個置換σ,其對應的置換矩陣Pσ是將單位矩陣的橫行進行 σ 置換,或者將單位矩陣的橫行進行 σ−1 置換得到的矩陣。
置換矩陣是雙隨機矩陣的一種。伯克霍夫-馮·諾伊曼定理說明每個雙隨機矩陣都是同階的置換矩陣的凸組合,並且所有的置換矩陣構成了雙隨機矩陣集合的所有端點。
置換矩陣Pσ的跡數等於相應置換σ的不動點的個數。設 a1、a2、……、ak 為其不動點的序號,則ea1、ea2、……、eak 是Pσ的特徵向量。
由群論可以知道,每個置換都可以寫成若干個對換的複合。由此可知,置換矩陣Pσ都可以寫成若干個表示兩行交換的初等矩陣的乘積。Pσ的行列式就等於 σ 的符號差。
對應於置換π = (1 4 2 5 3)的置換矩陣Pπ 是
![{\displaystyle 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}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/84fc5db75920f1880e5aee59f964bb88030a78cb)
給定一個向量 g,
![{\displaystyle 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}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/faf6b35ff9bc24a6b6f2a75d265449e438425cf9)
置換矩陣概念的一個推廣是將方陣的情況推廣到一般矩陣的情況:
- 一個m×n的0-1矩陣 P 是置換矩陣若且唯若
![{\displaystyle P\cdot P^{T}=I_{m}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f00fa1d8e4d085d922c11ab1bd981f439da8280f)
這時一個0-1矩陣是置換矩陣若且唯若它的每一行恰有一個1,每一列至多有一個1。
置換矩陣概念的另一個推廣是將每行的1變為一個非零的實數:
- 一個n階的方塊矩陣 P 是置換矩陣若且唯若其每一行與每一列都恰好只有一個係數不為零。
這時的置換矩陣P可以看做由0和1組成的置換矩陣Q與一個對角矩陣相乘的結果。
參考資料[編輯]
- 張賢達. 矩阵分析与应用. 清華大學出版社. 2004 (中文(中國大陸)).
外部連結[編輯]