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

本文的閱讀等級：中級

設 $P$ 為一 $n\times n$ 階排列矩陣， $P$ 的每一行和每一列恰有一個元為1，其餘元為0。排列矩陣是可逆矩陣，且 $P^T=P^{-1}$ 。一 $n\times n$ 階矩陣 $A$ 相似於 $PAP^{-1}=PAP^T$ ，因為 $A$ 和 $PAP^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^T$ 將 $a_{ij}$ 置換至何處？考慮一排列 $\pi$ 為集合 $\{1,2,\ldots,n\}$ 至其自身的一對一映射（見“特殊矩陣 (16)：排列矩陣”），以陣列形式表示如下：

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

對應 $\pi$ 的 $n\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$ 階矩陣 $A$ 和 $B$ 整理成 $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$ 階矩陣 $A$ 和 $B$ 分別表示為

$\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$ ，步驟如下。因為 $A$ 和 $B$ 是實對稱矩陣，故可正交對角化為 $A=U\Lambda U^T$ ， $B=V\Lambda V^T$ ，其中 $\Lambda=\mathrm{diag}(\lambda_1,\ldots,\lambda_n)$ ， $U$ 和 $V$ 是正交矩陣， $U^T=U^{-1}$ 且 $V^T=V^{-1}$ 。推得 $B=V(U^TAU)V^T=(VU^T)A(VU^T)^T$ ，故 $P=VU^T$ 。這個解法有兩個缺點：第一，此法僅適用於給定數值的排列相似矩陣；第二，對角化涉及複雜計算，大尺寸矩陣尤其難以應付。

	輕鬆談如何教學二項式定理？… on 牛頓的二項式定理 (上)
	madhouse on 高斯消去法
	WishMobile on 翻轉 LU 分解
	周子傑 on Karush-Kuhn-Tucker (KKT) 條件
	Cloud Huang on 線性泛函與伴隨
	jeff85898 on 利用分塊矩陣證明 det(AB)=(det A)(det…

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

Leave a Reply Cancel reply

搜尋(繁體中文或英文)

訊息看板

近期文章

線性代數專欄

其他主題專欄

每週問題

數據充分性問題

其他分類

Recent Comments

近期最多人點閱

分類

Archives

標籤雲

線代線上影音課程

線代學習網站

線代電子書

矩陣計算器

LaTeX

Blogroll

訂閱

閱讀導引

學習資源

專題探究

急救查詢

其他分頁

Meta

網路狀態

Blog Stats

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

Share this:

Like this:

Leave a Reply Cancel reply

搜尋(繁體中文或英文)

訊息看板

近期文章

線性代數專欄

其他主題專欄

每週問題

數據充分性問題

其他分類

Recent Comments

近期最多人點閱

分類

Archives

標籤雲

線代線上影音課程

線代學習網站

線代電子書

矩陣計算器

LaTeX

Blogroll

訂閱