每週問題 March 23, 2015

證明排列矩陣 (permutation matrix) 的轉置即為其逆矩陣。

A permutation matrix is a matrix that has exactly one 1 in each row and each column, and all entries elsewhere are 0. Show that any permutation matrix is invertible and its inverse is equal to its transpose.

 
參考解答:

每一 n\times n 階排列矩陣 P 與有序數組 \{1,2,\ldots,n\} 的排列 (permutation) \pi 具有一對一的對應關係。例如,排列矩陣

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

對應的排列為

\displaystyle  \pi=\left(\begin{matrix}  1&2&3&4\\  2&4&1&3\end{matrix}\right)

交換有序數組 \{1,2,\ldots,n\} 其中兩個相異元稱為換位 (transposition),所對應的 n\times n 階排列矩陣 T 為對稱矩陣且 T^2=I (重複二次相同的換位等於無作用),即知 T^T=T=T^{-1}。明顯地,每一排列可表示成多個換位的複合。換句話說,每一排列矩陣 P 可表示成多個換位矩陣的積。設 P=T_1T_2\cdots T_k,其中 T_1,T_2,\ldots,T_k 是換位矩陣,因此

\displaystyle\begin{aligned}  P^{-1}&=(T_1T_2\cdots T_k)^{-1}\\  &=T_k^{-1}\cdots T_2^{-1}T_1^{-1}\\  &=T_k^T\cdots T_2^TT_1^T\\  &=(T_1T_2\cdots T_k)^T\\  &=P^T.\end{aligned}

Advertisements
本篇發表於 pow 線性方程與矩陣代數, 每週問題 並標籤為 。將永久鏈結加入書籤。

4 則回應給 每週問題 March 23, 2015

  1. Trent 說道:

    Classic!

  2. bob 說道:

    I can only prove it in a very basic way:

    Assume that A=\{a_{ij}\} is an arbitrary nxn permutation matrix and its transpose matrix is A^{T}=\{b_{ij}\}.

    Let AA^{T}=\{c_{ij}\} then c_{ij}=\sum\limits_{k=1}^n a_{ik}b_{kj}.

    Now we only have to prove that c_{ij}=1 when i=j and c_{ij}=0 otherwise.

    Let a_{it} be the only element of value 1 in row i of A, then we have following facts:

    1. a_{ik}=0 when k \neq t

    2. b_{ti}=1

    3. b_{tj}=0 when j \neq i

    1 implies that \sum\limits_{k=1}^n a_{ik}b_{kj}=a_{it}b_{tj} and 2,3 imply that a_{it}b_{tj}=1 when i=j and a_{it}b_{tj}=0 otherwise.

    So we have AA^{T}=I.

  3. ccjou 說道:

    Thank you for your solution. Indeed, the (i,j) entry of PP^T is the dot product of the ith row of P and the jth column of P^T, or equivalently, the dot product of the ith row of P and the jth row of P. This observation leads to the conclusion immediately.

發表迴響

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

WordPress.com Logo

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

Twitter picture

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

Facebook照片

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

Google+ photo

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

連結到 %s