Permutations

In the example on solving systems of linear equations, we swapped the positions of rows 2 and 3. This is known as a permutation. 

When we are doing triangular factorization, we want our pivot values to be along the diagonal of the matrix, but this won't happen every time—in fact, it usually won't. So, instead, what we do is swap the rows so that we get our pivot values where we want them. 

But that is not their only use case. We can also use them to scale individual rows by a scalar value or add rows to or subtract rows from other rows.

Let's start with some of the more basic permutation matrices that we obtain by swapping the rows of the identity matrix. In general, we have n! possible permutation matrices that can be formed from an nxn identity matrix. In this example, we will use a 3×3 matrix and therefore have six permutation matrices, and they are as follows:

•  This matrix makes no change to the matrix it is applied on.
•  This matrix swaps rows two and three of the matrix it is applied on.
•  This matrix swaps rows one and two of the matrix it is applied on.

•  This matrix shifts rows two and three up one and moves row one to the position of row three of the matrix it is applied on.
•  This matrix shifts rows one and two down one and moves row three to the row-one position of the matrix it is applied on.
•  This matrix swaps rows one and three of the matrix it is applied on.

It is important to note that there is a particularly fascinating property of permutation matrices that states that if we have a matrix  and it is invertible, then there exists a permutation matrix that when applied to A will give us the LU factor of A. We can express this like so: