Intuitive explanation for inverse of a permutation matrix 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...?

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
