Permutation matrices are matrices with only one element as 1 in each row/column and rest as zero. A matrix when multiplied with permutation (P) matrices results in row/column exchanges.
PA = A', A' is row-exchanged matrix
AP = A'', A'' is column-exchanged matrix
For example,
P = [ 0 0 1;
1 0 0;
0 1 0]
The inverse of P is same as is transpose.
A well-explained proof is given in the following discussion in stack exchange.
http://math.stackexchange.com/questions/98549/the-transpose-of-a-permutation-matrix-is-its-inverse
Quoting the same here:
(PPT)ij=∑k=1nPikPTkj=∑k=1nPikPjk
but Pik is usually 0, and so PikPjk is usually 0. The only time Pik is nonzero is when it is 1, but then there are no other i′≠i such that Pi′k is nonzero (i is the only row with a 1 in column k ). In other words,
∑k=1nPikPjk={10if i=jotherwise
and this is exactly the formula for the entries of the identity matrix, so
PPT=I
PA = A', A' is row-exchanged matrix
AP = A'', A'' is column-exchanged matrix
For example,
P = [ 0 0 1;
1 0 0;
0 1 0]
The inverse of P is same as is transpose.
A well-explained proof is given in the following discussion in stack exchange.
http://math.stackexchange.com/questions/98549/the-transpose-of-a-permutation-matrix-is-its-inverse
Quoting the same here:
