特殊矩陣 (16):排列矩陣

本文的閱讀等級:中級

n\times n 階矩陣 P 稱為排列矩陣 (或稱置換矩陣,permutation matrix),若 P 的每一行和每一列恰有一個元為 1,其餘元為 0,例如:

P=\begin{bmatrix}  0&1&0&0\\    0&0&0&1\\    1&0&0&0\\    0&0&1&0    \end{bmatrix}

明顯地,P^T 也是一排列矩陣。設 A=\begin{bmatrix}    1\\    2\\    3\\    4    \end{bmatrix}B=\begin{bmatrix}    1&2&3&4    \end{bmatrix},則

PA=\begin{bmatrix}  0&1&0&0\\    0&0&0&1\\    1&0&0&0\\    0&0&1&0    \end{bmatrix}\begin{bmatrix}    1\\2\\3\\4    \end{bmatrix}=\begin{bmatrix}    2\\4\\1\\3    \end{bmatrix}

BP=\begin{bmatrix}  1&2&3&4    \end{bmatrix}\begin{bmatrix}    0&1&0&0\\    0&0&0&1\\    1&0&0&0\\    0&0&1&0    \end{bmatrix}=\begin{bmatrix}    3&1&4&2    \end{bmatrix}

左乘排列矩陣和右乘排列矩陣有不同的效果:PAA 的列按 2, 4, 1, 3 排序,BP 則將 B 的行按 3, 1, 4, 2 排序。寫出 (BP)^T=P^TB^T,配合轉置運算,右乘排列矩陣 P 可表示為左乘排列矩陣 P^T,以下限定排列矩陣總是以左乘方式執行。既然每一 n\times n 階排列矩陣 P 代表 n 個元素的一種特別排列,可知冪矩陣 P^k 表示連續執行 k 次排列,所以 P^k 也是一排列矩陣。考慮這個問題:試求一 5\times 5 階排列矩陣 P 使得 P^6=I,且 P^k\neq Ik=1,\ldots,5。純粹從矩陣分析角度不太容易看清解題方向,但如果我們了解排列的基本知識,無須複雜計算即可立刻得到答案,舉一例:

P=\begin{bmatrix}  0&1&0&0&0\\  1&0&0&0&0\\  0&0&0&1&0\\  0&0&0&0&1\\  0&0&1&0&0  \end{bmatrix}

 
以數學語言描述,所謂整數 1n 的排列 \pi 是指由集合 \{1,\ldots,n\} 至它自身的一對一的映射:

\pi:\{1,2,\ldots,n\}\to\{1,2,\ldots,n\}

或以陣列形式表達如下:

\begin{pmatrix}  1&2&\cdots&n\\    \pi(1)&\pi(2)&\cdots&\pi(n)    \end{pmatrix}

以下討論固定相同整數 n。因為 \pi 是一對一,對於任意 j=1,\ldots,n,必有唯一 i 使得 \pi(i)=j,例如,

\pi=\begin{pmatrix}  1&2&3&4\\    2&4&1&3    \end{pmatrix}

\sigma\tau 是兩個排列,對於任一 i,我們定義 \sigma\tau 的複合映射為

(\sigma\tau)(i)=\sigma(\tau(i))

兩個一對一映射的複合映射必定是一對一,可知 \sigma\tau 也是一排列。複合排列給出排列乘法的定義,我們稱 \sigma\tau\sigma\tau 的積 (product)。在一般情況下,\sigma\tau\neq\tau\sigma,也就是說排列乘法運算不具交換律。譬如,若

\sigma=\begin{pmatrix}  1&2&3&4\\    3&1&4&2    \end{pmatrix},~\tau=\begin{pmatrix}    1&2&3&4\\    2&4&3&1    \end{pmatrix}

\sigma\tau=\begin{pmatrix}  1&2&3&4\\    3&2&1&4    \end{pmatrix},~\tau\sigma=\begin{pmatrix}    1&2&3&4\\    1&2&4&3    \end{pmatrix}

 
排列乘法運算具有下列三個性質。

(1) 排列乘法滿足結合律。若 \pi, \sigma, \tau 是排列,則 (\pi\sigma)\tau=\pi(\sigma\tau),也就是對任何 i

((\pi\sigma)\tau)(i)=(\pi(\sigma\tau))(i)

證明於下。反覆運用排列乘法定義,上式等號左右兩邊分別為

((\pi\sigma)\tau)(i)=(\pi\sigma)(\tau(i))=\pi(\sigma(\tau(i)))

(\pi(\sigma\tau))(i)=\pi((\sigma\tau)(i))=\pi(\sigma(\tau(i)))

既然排列乘法滿足結合律,多個排列相乘時可省略括弧。針對一排列 \pi,我們以遞歸方式定義排列冪:令 \pi^1=\pi,若 k=1,2,\ldots\pi^{k+1}=\pi\cdot\pi^k。使用結合律可推得 \pi^p\pi^q=\pi^{p+q}(\pi^p)^q=\pi^{pq}

(2) 排列乘法存在一單位元素,記為 \epsilon,所有 i 滿足 \epsilon(i)=i。運用排列乘法定義即可證明對於任一排列 \pi

\pi\epsilon=\epsilon\pi=\pi

(3) 任何排列乘法都可「回復」,亦即每一排列 \pi 都存在一逆排列,記為 \pi^{-1},使得

\pi^{-1}\pi=\pi\pi^{-1}=\epsilon

對於 j=1,\ldots,n,存在唯一 i 使得 \pi(i)=j,所以 \pi^{-1}(j)=i,例如,

\pi^{-1}=\begin{pmatrix}  1&2&3&4\\    2&4&1&3    \end{pmatrix}^{-1}=\begin{pmatrix}    1&2&3&4\\    3&1&4&2    \end{pmatrix}

 
\mathcal{S}_n 代表整數 1n 的所有排列形成的集合,共包含 n! 種不同的排列。數學家稱滿足乘法封閉性及上述三個性質的集合 \mathcal{S}_n 為一群 (group),見 “線性代數裡的代數結構”。下面我們介紹一套常用的排列設計方法。基本列運算使用的列交換運算是最單純的一種排列形式。從1至 n 中選擇兩相異整數 pq,考慮

\begin{aligned}  \pi(p)&=q,\\    \pi(q)&=p, \\    \pi(i)&=i,~~i\neq p, i\neq q,\end{aligned}

稱為換位 (transposition),以 (p,q)(q,p) 表示。若 \pi 是一換位,則 \pi^2=\epsilon。擴展至一般情況,選取 k 個相異整數,設為 i_1,\ldots,i_k,但我們並不要求 i_1<\cdots<i_k。定義 \pi 如下:

\begin{aligned}  \pi(i_j)&=i_{j+1},~~j=1,\ldots,k-1\\    \pi(i_k)&=i_{1},\\    \pi(i)&=i,~~i\neq i_1,\ldots,i\neq i_k,\end{aligned}

稱為循環 (cycle) 或 k-循環,記作 (i_1,\ldots,i_k)。若 k=1,則 \pi=\epsilon;若 k=2,則 \pi 是一換位。舉一例說明,從整數 15 選取 2,5,4,循環 (2,5,4) 即為 \pi=\begin{pmatrix}    1&2&3&4&5\\    1&5&3&2&4    \end{pmatrix}。從循環本質即知 k-循環中每一元素 i_j 滿足 \pi^k(i_j)=i_j\pi^l(i_j)\neq i_j1\le l<k。這指出循環的表達方式並不唯一,譬如 (2,5,4)(5,4,2)(4,2,5) 都表示相同的排列規則,因此若 n=5k=3,總共有 \binom{5}{3}\cdot 3!/3=20 種不同的循環。我們說兩個循環 (i_1,\ldots,i_k)(j_1,\ldots,j_l) 不交集 (disjoint) 若沒有任何 ij 相同,譬如 (1,3)(2,5,4) 不交集。當循環 \sigma\tau 不交集,就有 \sigma\tau=\tau\sigma,即 \sigma\tau 是可交換排列。有了換位與循環設計,我們便可以將任一排列予以分解。

 
定理一:任一排列可分解為不交集循環的積。

\pi=\epsilon\pi 本身即為1-循環。以下設 \pi\neq\epsilon,也就有一 i 使得 \pi(i)\neq i。考慮序列 i, \pi(i), \pi^2(i),\ldots,因為1至 n 包含有限數目,必定存在 pq0\le p<q)使得 \pi^p(i)=\pi^q(i)。上式等號兩邊左乘 (\pi^{-1})^{p},即得 i=\pi^{q-p}(i),這證明存在一正整數 m 使得 \pi^m(i)=i。設 m 為滿足此關係的最小正整數,則 i, \pi(i),\ldots,\pi^{m-1}(i) 必定互異,故 (i,\pi(i),\ldots,\pi^{m-1}(i)) 構成一循環。如下例,考慮

\pi=\begin{pmatrix}  1&2&3&4&5\\    3&5&1&2&4    \end{pmatrix}

若選擇 i=2,就有

\begin{aligned}  \pi(2)&=5,\\    \pi^2(2)&=\pi(\pi(2))=\pi(5)=4,\\    \pi^3(2)&=\pi(\pi^2(2))=\pi(4)=2,\end{aligned}

即知 (2,5,4) 構成一3-循環。接著我們從1至 n 中選取一相異於循環 (i,\pi(i),\ldots,\pi^{m-1}(i)) 所含的數,設為 j,以同樣方式可產生由 j 帶領的另一循環。重複上述步驟,直到1至 n 的所有整數選盡為止。延續上例計算,若選擇 j=1,就有

\begin{aligned}  \pi(1)&=3,\\    \pi^2(1)&=\pi(\pi(1))=\pi(3)=1,\end{aligned}

於是得到一2-循環 (1,3),故排列 \pi 可分解為 (1,3)(2,5,4) 或寫成 (2,5,4)(1,3)

 
定理二:任一循環可分解為換位的積。

下面用一個例子解說循環的換位分解規則。考慮5-循環 (2,5,4,1,3),不難驗證以下關係成立:

(2,5,4,1,3)=(2,3)(2,1)(2,4)(2,5)

譬如,若 i=2,等號右邊排列運算結果為

\begin{aligned}  (2,3)(2,1)(2,4)(2,5)(2)&=(2,3)(2,1)(2,4)(5)=(2,3)(2,1)(5)\\    &=(2,3)(5)=5;\end{aligned}

i=3,可得

\begin{aligned}  (2,3)(2,1)(2,4)(2,5)(3)&=(2,3)(2,1)(2,4)(3)=(2,3)(2,1)(3)\\    &=(2,3)(3)=2;\end{aligned}

其他情況請讀者自行計算。合併定理一和定理三就得到以下必然結果。

 
定理三:任一排列可分解為換位的積。

例如,\pi=\begin{pmatrix}    1&2&3&4&5\\    3&5&1&2&4    \end{pmatrix} 可分解為 (1,3)(2,5,4)=(1,3)(2,4)(2,5)

 
接下來我們將上述排列性質轉移至排列矩陣上。給定一排列 \pi,傳統上我們以列排序來定義 n\times n 階排列矩陣 P_{\pi},如下:

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

也就是說,若 \pi(i)=jP_{\pi} 的第 i 列即為單位向量 \mathbf{e}_j 的轉置 (\mathbf{e}_j 的第 j 元為1,其餘各元為0),故 (P_{\pi})_{ij}=1。排列矩陣 P_{\pi} 是排列 \pi 的等價表達,於是立即可推得下列性質:排列矩陣乘積 P_{\sigma}P_{\tau} 對應排列積 \sigma\tau,因為

P_{\sigma}P_{\tau}\begin{bmatrix}  1\\  2\\  \vdots\\  n\end{bmatrix}=\begin{bmatrix}  \mathbf{e}^T_{\sigma(1)}\\  \mathbf{e}^T_{\sigma(2)}\\  \vdots\\  \mathbf{e}^T_{\sigma(n)}  \end{bmatrix}\begin{bmatrix}  \mathbf{e}^T_{\tau(1)}\\  \mathbf{e}^T_{\tau(2)}\\  \vdots\\  \mathbf{e}^T_{\tau(n)}  \end{bmatrix}\begin{bmatrix}  1\\  2\\  \vdots\\  n  \end{bmatrix}=\begin{bmatrix}  \mathbf{e}^T_{\sigma(1)}\\  \mathbf{e}^T_{\sigma(2)}\\  \vdots\\  \mathbf{e}^T_{\sigma(n)}  \end{bmatrix}\begin{bmatrix}  \tau(1)\\  \tau(2)\\  \vdots\\  \tau(n)  \end{bmatrix}=\begin{bmatrix}  \sigma(\tau(1))\\  \sigma(\tau(2))\\  \vdots\\  \sigma(\tau(n))  \end{bmatrix}

排列矩陣乘法不具有交換律,但有結合律。單位矩陣 I 則對應單位排列 \epsilon。逆矩陣 P^{-1}_{\pi} 對應逆排列 \pi^{-1},因為 \pi^{-1}(j)=i,即知 P^{-1}_{\pi} 的第 j 列即是 \mathbf{e}_i 的轉置,故 (P^{-1}_{\pi})_{ji}=1,這表明 P_{\pi}^{-1}=P_{\pi}^T,排列矩陣是正交矩陣 (P_{\pi}^TP_{\pi}=P_{\pi}P_{\pi}^T=I)。排列矩陣可應用於變數重新命名。如要將方陣 A 的列和行根據排列 \pi 排序,執行下列排列相似轉換 (見 “矩陣視覺化”):

A\to P_{\pi}AP^T_{\pi}

其中左乘 P_{\pi}A 的列排序 (即 P_{\pi}A),右乘 P^T_{\pi} 則對 A 的行排序 (即 AP^T_{\pi}=(P_{\pi}A^T)^T)。

 
最後我們回答本文開頭提出的問題。根據性質一,任一排列可分解為不交集循環的積。為方便說明,在不失一般性的原則下,考慮由連續數字構成的循環,如下例:\pi=(1,2)(3,4,5),對應的排列矩陣 P_{\pi} 可表示成兩主對角子陣的直和 (見 “Jordan 型式大解讀(上)”):

P_{\pi}=\begin{bmatrix}  0&1&0&0&0\\  1&0&0&0&0\\  0&0&0&0&1\\  0&0&1&0&0\\  0&0&0&1&0  \end{bmatrix}=\begin{bmatrix}  0&1\\  1&0  \end{bmatrix}\oplus\begin{bmatrix}  0&0&1\\  1&0&0\\  0&1&0  \end{bmatrix}

冪矩陣即為

P_{\pi}^k=\begin{bmatrix}  0&1\\  1&0  \end{bmatrix}^k\oplus\begin{bmatrix}  0&0&1\\  1&0&0\\  0&1&0  \end{bmatrix}^k

注意 \begin{bmatrix}  0&1\\  1&0  \end{bmatrix} 是2-循環,\begin{bmatrix}  0&0&1\\  1&0&0\\  0&1&0  \end{bmatrix} 是3-循環,故僅當 k 是偶數方有 \begin{bmatrix}  0&1\\  1&0  \end{bmatrix}^k=I_2,且僅當 k 是3的倍數才有 \begin{bmatrix}  0&0&1\\  1&0&0\\  0&1&0  \end{bmatrix}^k=I_3。因為6是2和3的最小公倍數,可知 P_{\pi}^6=I_5,但對於 k=1,\ldots,5P_{\pi}^k\neq I_5。再考慮一個類似問題:考慮排列矩陣 P_{\pi} 滿足 P^k_{\pi}\neq Ik=1,\ldots,m-1,且 P^m=I,求一使得 m 值最大的 10\times 10 階排列矩陣。按照同樣想法,設法將1至10分割成數個 k-循環,k_1,\ldots,k_s,使得 10=k_1+\cdots+k_sm=\mathrm{lcm}(k_1,\ldots,k_s) 最大。稍加計算可得 k_1=2, k_2=3, k_3=5,故 m=\mathrm{lcm}(2,3,5)=30,下為一例:

P_{\pi}=\begin{bmatrix}  0&1\\  1&0  \end{bmatrix}\oplus\begin{bmatrix}  0&0&1\\  1&0&0\\  0&1&0  \end{bmatrix}\oplus\begin{bmatrix}  0&0&0&0&1\\  1&0&0&0&0\\  0&1&0&0&0\\  0&0&1&0&0\\  0&0&0&1&0  \end{bmatrix}

 
本文參考
Paul R. Halmos, Finite-Dimensional Vector Spaces, Springer, 1974.

繼續閱讀:
廣告
本篇發表於 特殊矩陣, 線性代數專欄 並標籤為 , , , , 。將永久鏈結加入書籤。

13 Responses to 特殊矩陣 (16):排列矩陣

  1. yufenglyu 說道:

    周老师,
    正文中“排列乘法运算具有下列三个性质”上一行的 \sigma\tau\tau\sigma 两者是不是写反了?
    另外,逆置换(排列)\pi^{-1} 有没有简单求法?

  2. cokernel 說道:

    您好,$P_\sigma P_\tau$應該對應$\tau\sigma$吧?因為$e^T_{\sigma(i)}[\tau(1)\ldots \tau(n)]=$第$\sigma(i
    )$個分量$=\tau(\sigma(i))$。

  3. ccjou 說道:

    顯然你沒聽我的建議找一副撲克牌來玩。不要再執著於數學函數了!

  4. cokernel 說道:

    我想您説的“玩撲克牌”是指把
    \pi= \begin{pmatrix} &1 \ldots &n \\ &\pi(1) \ldots &\pi(n) \end{pmatrix}
    看作是把第i張牌放到第\pi(i)個位置上這個操作?
    那麽
    \sigma= \begin{pmatrix} &1 &2 &3 &4 \\ &3 &1 &4 &2 \end{pmatrix} ,
    \tau= \begin{pmatrix} &1 &2 &3 &4 \\ &2 &4 &3 &1 \end{pmatrix} ;
    \sigma作用于$(1 ~2 ~3 ~4)$得到:
    (2 ~4 ~1 ~3), 再將\tau作用于其上得到:
    (3 ~2 ~1 ~4)
    於是
    \tau\sigma = \begin{pmatrix} &1 &2 &3 &4 \\ &3 &2 &1 &4 \end{pmatrix}
    結果一樣。
    另外,如果您認爲我上一條用函數推導的過程不正確,請問是哪一步不對?

    • ccjou 說道:

      你太急了,快要走火入魔才會說:
      \sigma作用于(1,2,3,4)得到:(2,4,1,3),再將\tau作用于其上得到:(3,2,1,4)

      第一步應是 \sigma:(1,2,3,4)\to (3,1,4,2)。改寫
      \tau=\begin{pmatrix} a&b&c&d\\ b&d&c&a \end{pmatrix},則
      \tau:(3,1,4,2)\to(1,2,4,3)。故
      \tau(\sigma)=\begin{pmatrix} 1&2&3&4\\ 1&2&4&3 \end{pmatrix}

      去玩玩撲克牌吧!

發表迴響

在下方填入你的資料或按右方圖示以社群網站登入:

WordPress.com Logo

您的留言將使用 WordPress.com 帳號。 登出 / 變更 )

Twitter picture

您的留言將使用 Twitter 帳號。 登出 / 變更 )

Facebook照片

您的留言將使用 Facebook 帳號。 登出 / 變更 )

Google+ photo

您的留言將使用 Google+ 帳號。 登出 / 變更 )

連結到 %s