Intuitive explanation for inverse of a permutation matrix

Question

Today in lecture we learned that the transpose of a permutation matrix is the inverse of the permutation matrix. Meaning, $$P^{T}P = I$$

I can work out the math by matrix multiplication but I'd prefer a deeper, more intuitive understanding.

What I have so far in my head is:

We know that the matrix $P$ will swap rows when we apply it to a matrix, let's say $A$. Then $PA$ will swap the $i^{th}$ row of A with the $j^{th}$ of $A$.

This then means that $P^{T}(PA)$ must swap our new $i^{th}$ row with the new $j^{th}$ row so we can have our original $A$ matrix back. Why is this always true? More specifically why does $P^{T}$ swap back out rows...?

Answer 1

The key point is that any permutation matrix can be obtained as a product of elementary permutation matrices each of one by left multiplication exchange only $2$ rows, therefore given

$$P=P_{i,j}\cdots P_{h,k}$$

the reverse operation is given by

$$P^{-1}=P_{h,k}\cdots P_{i,j}$$

and since elementary permutation matrices are symmetric

$$P^{-1}=P_{h,k}\cdots P_{i,j}=(P_{i,j}\cdots P_{h,k})^T=P^T$$

Refer to the related

• Symmetric permutation matrix

Answer 2

A permutation matrix $P$ preserves length. So $\|Px\|=\|x\|$, which gives $\langle P^TPx,x\rangle=\langle x,x\rangle$ in the Euclidean inner product. That's enough to imply that $P^TP=I$. So, $P^T$ has to undo any swapping done by $P$.