Monday, February 24, 2014

Inverse of permutation matrices are nothing but their transposes.

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.

Quoting the same here:

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 ii such that Pik 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