## 每週問題 March 23, 2015

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.

$\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)$

\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}

### 4 Responses to 每週問題 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 $i$th row of $P$ and the $j$th column of $P^T$, or equivalently, the dot product of the $i$th row of $P$ and the $j$th row of $P$. This observation leads to the conclusion immediately.

• bob 說道：

true it could be made briefer.