## Permutation Matrices

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:

1. The determinant is +1 or -1.
2. 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]'
M(v,:)
```

Try a few other examples.

If PM permutes the rows of M, what does MP do?