This is a question from the free Harvard online abstract algebra lectures.  I'm posting my solutions here to get some feedback on them.  For a fuller explanation, see this post.

This problem is from assignment 4.


  Prove that the transpose of a permutation matrix $P$ is its inverse.


A permutation matrix $P$ has a single 1 in each row and a single 1 in each column, all other entries being 0.  So column $j$ has a single 1 at position $e_{i_jj}$.  $P$ acts by moving row $j$ to row $i_j$ for each column $j$.  Taking the transpose of $P$ moves each 1 entry from $e_{i_jj}$ to $e_{ji_j}$.  Then $P^t$ acts by moving row $i_j$ to row $j$ for each row $i_j$.  Since this is the inverse operation, $P^t=P^{-1}$.

Again, I welcome any critique of my reasoning and/or my style as well as alternative solutions to the problem.

Thanks.

A direct computation is also fine:
$$(PP^T)_{ij} = \sum_{k=1}^n P_{ik} P^T_{kj} = \sum_{k=1}^n P_{ik} P_{jk}$$
but $P_{ik}$ is usually 0, and so $P_{ik} P_{jk}$ is usually 0.  The only time $P_{ik}$ is nonzero is when it is 1, but then there are no other $i' \neq i$ such that $P_{i'k}$ is nonzero ($i$ is the only row with a 1 in column $k$). In other words,
$$\sum_{k=1}^n P_{ik} P_{jk} = \begin{cases} 1 & \text{if } i = j \\ 0 & \text{otherwise} \end{cases}$$
and this is exactly the formula for the entries of the identity matrix, so
$$PP^T = I$$