Given an n × n matrix M, a matrix
P such that PM permutes the rows of M is called
a permutation matrix.
A permutation matrix has the following properties:
- The determinant is +1 or -1.
- The inverse is PT.
The following are equivalent:
- A matrix P is a permutation matrix.
- A matrix has exactly one 1 per row and one 1 per column and all other entries are 0.
- A matrix is the product of zero or more elementary matrices
which swap rows.
Consequently, the identity matrix and elementary matrices of
which swap rows are all permutation matrices.
The proof that the inverse is equal to the transpose is
straight forward: if P = (pi,j) is a permutation matrix and
the entry pi,j = 1, then the jth row of M is the ith row
of PM. Thus, the inverse
P-1 = (qi,j) must have entry qj,i = 1
because it must copy the ith row back to the jth row. Therefore pi,j = qj,i
and all other entries are zero, thus P-1 = PT.
In the next tutorial, you will see how we can efficiently store a
permutation matrix. See if you can figure out what is happening:
M = [1 2 3; 4 5 6; 7 8 9]
v = [3 1 2]'
Try a few other examples.
If PM permutes the rows of M, what does MP do?