排列相似的益智遊戲──尋找排列矩陣

本文的閱讀等級:中級

P 為一 n\times n 階排列矩陣,P 的每一行和每一列恰有一個元為1,其餘元為0。排列矩陣是可逆矩陣,且 P^T=P^{-1}。一 n\times n 階矩陣 A 相似於 PAP^{-1}=PAP^T,因為 APAP^T 透過排列變換建立相似關係,故稱為排列相似(permutation similar)。明顯地,PAP^T 僅將 A 的各個元置換行列並不改變其值。本文要探討的問題是排列相似的益智遊戲:若 A 排列相似於 B,尋找一排列矩陣 P 使得 B=PAP^T,如下例(取自2006年台大電機所碩士班入學試題):

A=\left[\!\!\begin{array}{rrrr}  2&0&-1&0\\  0&2&0&-1\\    -1&0&2&0\\    0&-1&0&2    \end{array}\!\!\right],~~B=\left[\!\!\begin{array}{rrrr}    2&-1&0&0\\    -1&2&0&0\\    0&0&2&-1\\    0&0&-1&2    \end{array}\!\!\right]

 
a_{ij} 代表 A(i,j) 元,回答上述問題前有必要先弄清楚排列相似變換 PAP^Ta_{ij} 置換至何處?考慮一排列 \pi 為集合 \{1,2,\ldots,n\} 至其自身的一對一映射(見“特殊矩陣 (16):排列矩陣”),以陣列形式表示如下:

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

對應 \pin\times n 階排列矩陣 P 定義為

P=\begin{bmatrix}  \mathbf{e}^T_{\pi(1)}\\  \mathbf{e}^T_{\pi(2)}\\  \vdots\\  \mathbf{e}^T_{\pi(n)}  \end{bmatrix}

也就是說,若 \pi(i)=j,則 P 的第 i 列為 \mathbf{e}^T_{j}(單位向量 \mathbf{e}_j 的第 j 元為1,其餘各元為0)。因此,左乘排列矩陣 P 置換 A 的列,就有

PA=\begin{bmatrix}  a_{\pi(1),1}&a_{\pi(1),2}&\cdots&a_{\pi(1),n}\\  a_{\pi(2),1}&a_{\pi(2),2}&\cdots&a_{\pi(2),n}\\  \vdots&\vdots&~&\vdots\\  a_{\pi(n),1}&a_{\pi(n),2}&\cdots&a_{\pi(n),n}  \end{bmatrix}

上式再右乘排列矩陣 P^T,寫成 (PA)P^T=(P(PA)^T)^T,其效果等於置換 (PA)^T 的列,即 PA 的行,故得到

(PA)P^T=\begin{bmatrix}  a_{\pi(1),\pi(1)}&a_{\pi(1),\pi(2)}&\cdots&a_{\pi(1),\pi(n)}\\  a_{\pi(2),\pi(1)}&a_{\pi(2),\pi(2)}&\cdots&a_{\pi(2),\pi(n)}\\  \vdots&\vdots&~&\vdots\\  a_{\pi(n),\pi(1)}&a_{\pi(n),\pi(2)}&\cdots&a_{\pi(n),\pi(n)}  \end{bmatrix}

\pi(p)=i\pi(q)=j,則 a_{ij} 被置換於 PAP^T(p,q) 元位置,但 \pi 是一對一映射,可知 p=\pi^{-1}(i), q=\pi^{-1}(j)

 
看下面的例子。設 n=3\pi=\begin{pmatrix}  1&2&3\\  2&3&1  \end{pmatrix},即 \pi(1)=2, \pi(2)=3, \pi(3)=1,對應排列 \pi 的排列矩陣為

P=\begin{bmatrix}  \mathbf{e}_2^T\\  \mathbf{e}_3^T\\  \mathbf{e}_1^T  \end{bmatrix}=\begin{bmatrix}  0&1&0\\  0&0&1\\  1&0&0  \end{bmatrix}

為方便說明,設 A 有相異元,如下:

A=\begin{bmatrix}  1&4&7\\  2&5&8\\  3&6&9  \end{bmatrix}

計算排列相似矩陣可得

B=PAP^T=\begin{bmatrix}  5&8&2\\  6&9&3\\  4&7&1  \end{bmatrix}

從逆排列 \pi^{-1}=\begin{pmatrix}  1&2&3\\  3&1&2  \end{pmatrix} 可決定每一 a_{ij} 置換後的新位置,如 a_{32}=6 被置換於 B(\pi^{-1}(3),\pi^{-1}(2))=(2,1) 元,而 a_{13}=7 則被置換於 B(\pi^{-1}(1),\pi^{-1}(3))=(3,2) 元。所以,若 A 有相異元,且 A 排列相似於 B,則對於任何 (i,j),僅有唯一 (p,q) 滿足 a_{ij}=b_{pq}。從置換關係 (i,j)\to(p,q) 立知 \pi(p)=i, \pi(q)=j,窮舉所有情況可歸納出 \pi,也就得到一排列矩陣 P 滿足 B=PAP^T。但若 A 包含相同元,如前例,A 有4個 2,4個 -1,與8個 0,這時可能存在不只一種符合條件的排列,那該如何將這些排列全部找齊?

 
欲求出所有可能的排列,我們其實只需要一個比較有效且不易出錯的簿記法。為清楚呈現 (i,j)\to(p,q) 的置換關係,將 n\times n 階矩陣 AB 整理成 n^2 維向量。如此一來,相似變換 PAP^T 則以矩陣-向量乘法表示,這個想法可藉由 Kronecker 積來實現。考慮 n\times n 階矩陣 A 的行向量表達 A=\begin{bmatrix}  \mathbf{a}_1&\cdots&\mathbf{a}_n  \end{bmatrix},定義 \mathrm{vec}(A) 為下列 n^2 維向量:

\mathrm{vec}(A)=\begin{bmatrix}  \mathbf{a}_1\\  \vdots\\  \mathbf{a}_n  \end{bmatrix}

同樣地,\mathrm{vec}(B)=\begin{bmatrix}  \mathbf{b}_1\\  \vdots\\  \mathbf{b}_n  \end{bmatrix}。將矩陣方程式 PAP^T=B 改寫為一般線性方程(證明見“Kronecker 積”):

(P\otimes P)\mathrm{vec}(A)=\mathrm{vec}(B)

其中 n^2\times n^2 階矩陣 P\otimes P 稱為 Kronecker 積,定義為

P\otimes P=\begin{bmatrix}  p_{11}P&p_{12}P&\cdots&p_{1n}P\\  p_{21}P&p_{22}P&\cdots&p_{2n}P\\  \vdots&\vdots&\ddots&\vdots\\  p_{n1}P&p_{n2}P&\cdots&p_{nn}P  \end{bmatrix}

例如,下列矩陣方程

\begin{bmatrix}  0&1&0\\  0&0&1\\  1&0&0  \end{bmatrix}\begin{bmatrix}  1&4&7\\  2&5&8\\  3&6&9  \end{bmatrix}\begin{bmatrix}  0&0&1\\  1&0&0\\  0&1&0  \end{bmatrix}=\begin{bmatrix}  5&8&2\\  6&9&3\\  4&7&1  \end{bmatrix}

等價於

\begin{bmatrix}  0&0&0&0&1&0&0&0&0\\  0&0&0&0&0&1&0&0&0\\  0&0&0&1&0&0&0&0&0\\  0&0&0&0&0&0&0&1&0\\  0&0&0&0&0&0&0&0&1\\  0&0&0&0&0&0&1&0&0\\  0&1&0&0&0&0&0&0&0\\  0&0&1&0&0&0&0&0&0\\  1&0&0&0&0&0&0&0&0  \end{bmatrix}\begin{bmatrix}  1\\2\\3\\4\\5\\6\\7\\8\\9  \end{bmatrix}=\begin{bmatrix}  5\\6\\4\\8\\9\\7\\2\\3\\1  \end{bmatrix}

觀察發現 9\times 9 階 Kronecker 積 P\otimes P 的「宏觀」結構與 3\times 3 階排列矩陣 P 的「微觀」結構相同,精確地說,P\otimes P 繼承了來自 P=\begin{bmatrix}  0&1&0\\  0&0&1\\  1&0&0  \end{bmatrix} 的分塊型態:

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

 
Kronecker 積 P\otimes P 的結構特性可以幫助我們簡化尋找排列矩陣的工作,詳述於下。將前例 4\times 4 階矩陣 AB 分別表示為

\mathrm{vec}(A)=\begin{bmatrix}  \mathbf{a}_1\\  \mathbf{a}_2\\  \mathbf{a}_3\\  \mathbf{a}_4  \end{bmatrix},~\mathbf{a}_1=\left[\!\!\begin{array}{r}  2\\  0\\  -1\\  0  \end{array}\!\!\right],~\mathbf{a}_2=\left[\!\!\begin{array}{r}  0\\  2\\  0\\  -1  \end{array}\!\!\right],~\mathbf{a}_3=\left[\!\!\begin{array}{r}  -1\\  0\\  2\\  0  \end{array}\!\!\right],~\mathbf{a}_4=\left[\!\!\begin{array}{r}  0\\  -1\\  0\\  2  \end{array}\!\!\right]

\mathrm{vec}(B)=\begin{bmatrix}  \mathbf{b}_1\\  \mathbf{b}_2\\  \mathbf{b}_3\\  \mathbf{b}_4  \end{bmatrix},~\mathbf{b}_1=\left[\!\!\begin{array}{r}  2\\  -1\\  0\\  0  \end{array}\!\!\right],~\mathbf{b}_2=\left[\!\!\begin{array}{r}  -1\\  2\\  0\\  0  \end{array}\!\!\right],~\mathbf{b}_3=\left[\!\!\begin{array}{r}  0\\  0\\  2\\  -1  \end{array}\!\!\right],~\mathbf{b}_4=\left[\!\!\begin{array}{r}  0\\  0\\  -1\\  2  \end{array}\!\!\right]

P\otimes P 可表示為 4\times 4 階分塊矩陣,如下:

P\otimes P=\begin{bmatrix}  P_{11}&P_{12}&P_{13}&P_{14}\\  P_{21}&P_{22}&P_{23}&P_{24}\\  P_{31}&P_{32}&P_{33}&P_{34}\\  P_{41}&P_{42}&P_{43}&P_{44}  \end{bmatrix}

其中每一列和每一行僅有一分塊是 P,其餘分塊都是 0。將方程式 \mathrm{vec}(B)=(P\otimes P)\mathrm{vec}(A) 寫成

\begin{bmatrix}  \mathbf{b}_1\\  \mathbf{b}_2\\  \mathbf{b}_3\\  \mathbf{b}_4  \end{bmatrix}=\begin{bmatrix}  P_{11}&P_{12}&P_{13}&P_{14}\\  P_{21}&P_{22}&P_{23}&P_{24}\\  P_{31}&P_{32}&P_{33}&P_{34}\\  P_{41}&P_{42}&P_{43}&P_{44}  \end{bmatrix}\begin{bmatrix}  \mathbf{a}_1\\  \mathbf{a}_2\\  \mathbf{a}_3\\  \mathbf{a}_4  \end{bmatrix}

展開可得

\mathbf{b}_i=P_{i1}\mathbf{a}_1+P_{i2}\mathbf{a}_2+P_{i3}\mathbf{a}_3+P_{i4}\mathbf{a}_4,~~i=1,2,3,4

對於每一 i,僅有一 j 滿足 P_{ij}\neq 0,以下分開四種情況討論。在不失一般性的原則下,考慮 i=1

(1) 若 \mathbf{b}_1=P\mathbf{a}_1,可得

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

(2) 若 \mathbf{b}_1=P\mathbf{a}_2,可得

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

(3) 若 \mathbf{b}_1=P\mathbf{a}_3,可得

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

(4) 若 \mathbf{b}_1=P\mathbf{a}_4,可得

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

接下來是驗證工作。寫出這些 P 矩陣的 Kronecker 積,代入 (P\otimes P)\mathrm{vec}(A)=\mathrm{vec}(B),獲致結論:在 4!=24 種排列矩陣中,上述8個 P 皆符合給出的排列相似關係 B=PAP^T

 
最後補充說明排列相似可應用於約化矩陣。上例中,B 是一分塊對角矩陣,其特徵多項式可分解為主對角分塊特徵多項式的積:

\begin{aligned}  \det(B-\lambda I)&=\begin{vmatrix}  2-\lambda&-1&0&0\\  -1&2-\lambda&0&0\\  0&0&2-\lambda&0-1\\  0&0&-1&2-\lambda  \end{vmatrix}\\  &=\begin{vmatrix}  2-\lambda&-1\\  -1&2-\lambda  \end{vmatrix}^2=((2-\lambda)^2-1)^2,\end{aligned}

解出 B 有特徵值 3, 3, 1, 1。因為兩相似矩陣有相同的特徵值,故 B=PAP^T 的特徵值即為 A 的特徵值。

 
後記:我在2008年撰寫的台清交研究所入學試題解答中採用對角化方法求 P,步驟如下。因為 AB 是實對稱矩陣,故可正交對角化為 A=U\Lambda U^TB=V\Lambda V^T,其中 \Lambda=\mathrm{diag}(\lambda_1,\ldots,\lambda_n)UV 是正交矩陣,U^T=U^{-1}V^T=V^{-1}。推得 B=V(U^TAU)V^T=(VU^T)A(VU^T)^T,故 P=VU^T。這個解法有兩個缺點:第一,此法僅適用於給定數值的排列相似矩陣;第二,對角化涉及複雜計算,大尺寸矩陣尤其難以應付。

廣告
本篇發表於 特徵分析, 線性代數專欄 並標籤為 , , , 。將永久鏈結加入書籤。

發表迴響

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

WordPress.com Logo

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

Twitter picture

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

Facebook照片

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

Google+ photo

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

連結到 %s