6
$\begingroup$

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...?

$\endgroup$
2
  • $\begingroup$ Convince yourself that row swaps are also column swaps. Then ask what the row and column swapping is doing after you take the transpose. See if you can piece together why this makes sense from there. $\endgroup$ Sep 15, 2020 at 16:53
  • $\begingroup$ i think none of the answers provide the "intuitive explanation" asked by OP. IMO, it is just this: a permutation matrix can only perform a single swap in a given operation. It can swap either two rows or two columns at a given time. Inverting the linear transformation performed by a permutation matrix will swap the columns or rows back to original matrix. $\endgroup$
    – senseiwu
    Feb 17, 2023 at 9:40

2 Answers 2

2
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ I guess my question isn't so much why does $P^{-1} = P^T$ as it is why does $P^T$ un-swap the rows from $PA$... $\endgroup$
    – FafaDog
    Sep 14, 2020 at 20:50
  • $\begingroup$ Why does transposing the matrix mean reversing the order of the permutations? $\endgroup$ Sep 14, 2020 at 20:57
1
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ Really confused. Wy does having an inner product of $<x,x>$ mean $P^TP = I$? $\endgroup$
    – FafaDog
    Sep 14, 2020 at 21:09
  • $\begingroup$ @BigBear : $\langle Ax,y\rangle = \langle x,A^T y\rangle$ for a real inner product and a square matrix $A$. $\langle x,y\rangle = x^Ty$. $\endgroup$ Sep 14, 2020 at 21:42

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .