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: