# The transpose of a permutation matrix is its inverse.

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.

-
Perhaps you could be clearer on what $P$ is acting upon and how. I think you're multiplying some unnamed matrix $A$ on the left by $P$ to get $PA$, but it would be good to spell this out. When you say "each column $j$" that's also a bit confusing, since you've already used $j$ for something. –  Dylan Moreland Jan 12 '12 at 19:55
I think it would be clearer if you prove this first for permutation matrices corresponding to simple transpositions, as then $P$ will be an elementary matrix and we know what the inverse of elementary matrices are. Then use the fact that every permutation can be written as a product of transpositions, and that if $\sigma$ and $\rho$ are permutations, then $P_{\sigma\rho} = P_{\sigma}P_{\rho}$, to conclude the result for arbitrary permutations. But that's just me. –  Arturo Magidin Jan 12 '12 at 19:56
I also think it would be good to in the end show that $PP^t = (P^t)P = I_n$, where $I_n$ is the $n \times n$ identity matrix. This stuff about moving rows around isn't exactly wrong, though. –  Dylan Moreland Jan 12 '12 at 19:59
Another way of looking at this is to identify the permutation represented by the first matrix, compute the inverse permutation (easy), convert this to matrix form, and compare with the proposed inverse. –  Mark Bennet Jan 12 '12 at 20:18
@jobrien929: I suspect that trying to write it out carefully would just lead to precisely my suggestion, considering transpositions or products of transpositions. Otherwise, keeping track of all the row shuffles is going to be a pain. Clarification: you may want to show only that if $\tau$ is a transposition and $\sigma$ a permutation, then $P_{\tau}P_{\sigma} = P_{\tau\sigma}$, rather than trying to prove it for any two permutations. That should be enough. –  Arturo Magidin Jan 12 '12 at 21:37

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

-
Funny that we independently come up with almost identical answers. Since it seems you beat me to it, I can delete mine if you want. –  Jason DeVito Jan 12 '12 at 20:06

Using a little knowledge about orthogonal matrices the following proof is pretty simple:

Since $v^tw=\sum_{k=0}^nv_iw_i$ if $v=(v_1,...,v_n),w=(w_1,...,w_n)$ we have $v^tv=1$ whenever v is a column of $P$. On the other hand $v^tw=0$ if $v$ and $w$ are two distinct columns of $P$. Therefore we can conclude that $(P^tP)_{i,j}=\delta_{i,j}$ and so $P^t=P^{-1}$.

-

Less sophisticated, you could just crunch it out.

First, a lemma:

The inverse of a matrix, if it exists, is unique.

Proof: If both $B$ and $C$ are inverse to $A$, then we have $B = BI = B(AC) = (BA)C = IC = C$ so $B = C$. (Here, $I$ denotes the identity matrix).

Using this, it follows in our specific case that in order to show $A^t = A^{-1}$, we need only show $A^tA = A^t A = I$.

Assume $i\neq j$. Then $(AA^t)_{ij} = \sum_k A_{ik}A^t_{kj} = \sum_k A_{ik}A_{jk}$. But for each $k$, $A_{ik}A_{jk} = 0$ since there is only one nonzero entry in the $k$th row and $i\neq j$ (so $A_{ik}$ and $A_{jk}$ can't both be the nonzero entry). So, $(AA^t)_{ij} = 0$ when $i\neq j$.

The argument that $(A^tA)_{ij} = 0$ when $i\neq j$ is almost identical, but uses the fact that the columns of $A$ contain only one nonzero entry.

Can you see what happens when, instead, $i = j$?

-
Looks good to me too. A survey of style is probably good for this kind of question. –  Jack Schmidt Jan 12 '12 at 20:13