[科普中國]-置換矩陣

判定定理

定理 1 當(dāng) m≦n時(shí)，一個(gè) m×n 的(0,1) 矩陣P為置換矩陣的充要條件是P的每一行恰有一個(gè) 1，每一列恰有一個(gè) 1。

置換矩陣在數(shù)學(xué)中的矩陣論里，置換矩陣是一種系數(shù)只由0和1組成的方塊矩陣。置換矩陣的每一行和每一列都恰好有一個(gè)1，其余的系數(shù)都是0。在線性代數(shù)中，每個(gè)n階的置換矩陣都代表了一個(gè)對n個(gè)元素（n維空間的基）的置換。當(dāng)一個(gè)矩陣乘上一個(gè)置換矩陣時(shí)，所得到的是原來矩陣的橫行（置換矩陣在左）或縱列（置換矩陣在右）經(jīng)過置換后得到的矩陣。1

嚴(yán)格定義每個(gè)n元置換都對應(yīng)著唯一的一個(gè)置換矩陣。設(shè)π 為一個(gè)n元置換：

給出其映射圖：

它對應(yīng)的n × n的置換矩陣Pπ是：在第i橫行只有π(i)位置上系數(shù)為1，其余為0。即可以寫做：

其中每個(gè)表示正則基中的第j個(gè)，也就是一個(gè)左起第j個(gè)元素為1，其余都是0的n元橫排數(shù)組。

由于單位矩陣是

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

性質(zhì)對兩個(gè)n元置換π 和 σ的置換矩陣Pπ 和Pσ，有

一個(gè)置換矩陣Pπ 必然是正交矩陣（即滿足

），

并且它的逆也是置換矩陣：

用置換矩陣Pπ右乘一個(gè)列向量 g所得到的是 g 的系數(shù)經(jīng)過置換后的向量：

用置換矩陣Pπ左乘一個(gè)行向量 h 所得到的是 h 的系數(shù)經(jīng)過置換后的向量：

置換矩陣與置換設(shè)Sn是n次對稱群，由于n置換一共有n! 個(gè)，n階的置換矩陣也有n! 個(gè)。這n! 個(gè)置換矩陣構(gòu)成一個(gè)關(guān)于矩陣乘法的群。這個(gè)群的單位元就是單位矩陣。設(shè)A是所有n階的置換矩陣的集合。映射Sn → A ? GL(n, Z2)是一個(gè)群的忠實(shí)表示。

對一個(gè)置換σ，其對應(yīng)的置換矩陣Pσ是將單位矩陣的橫行進(jìn)行 σ 置換，或者將單位矩陣的橫行進(jìn)行 σ 置換得到的矩陣。

置換矩陣是雙隨機(jī)矩陣的一種。伯克霍夫-馮·諾伊曼定理說明每個(gè)雙隨機(jī)矩陣都是同階的置換矩陣的凸組合，并且所有的置換矩陣構(gòu)成了雙隨機(jī)矩陣集合的所有端點(diǎn)。

置換矩陣Pσ的跡數(shù)等于相應(yīng)置換σ的不動(dòng)點(diǎn)的個(gè)數(shù)。設(shè) a1、a2、……、ak 為其不動(dòng)點(diǎn)的序號，則ea1、ea2、……、eak 是Pσ的特征向量。

由群論可以知道，每個(gè)置換都可以寫成若干個(gè)對換的復(fù)合。由此可知，置換矩陣Pσ都可以寫成若干個(gè)表示兩行交換的初等矩陣的乘積。Pσ的行列式就等于 σ 的符號差。

例子對應(yīng)于置換π = (1 4 2 5 3)的置換矩陣Pπ 是

給定一個(gè)向量 g，

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

一個(gè)m×n的0-1矩陣 P 是置換矩陣當(dāng)且僅當(dāng) 這時(shí)一個(gè)0-1矩陣是置換矩陣當(dāng)且僅當(dāng)它的每一行恰有一個(gè)1，每一列至多有一個(gè)1。3

置換矩陣概念的另一個(gè)推廣是將每行的1變?yōu)橐粋€(gè)非零的實(shí)數(shù)：

一個(gè)n階的方塊矩陣 P 是置換矩陣當(dāng)且僅當(dāng)其每一行與每一列都恰好只有一個(gè)系數(shù)不為零。 這時(shí)的置換矩陣P可以看做由0和1組成的置換矩陣Q與一個(gè)對角矩陣相乘的結(jié)果。4