Permutation Matrix

A Matrix that exchanges 2 or more rows is called a permutation matrix

  • a permutation matrix $P$ is a matrix that is obtained by permuting rows/columns of identity matrix $I$
  • this is an important type of matrices - it's used for solving System of Linear Equations and for LU Factorization
  • e.g. for Gaussian Elimination when we have a zero in the pivot position, we would like to exchange this to get non-zero pivot - this is done with a Permutation Matrix


$P$ for Square Matrices

Suppose we have a $3 \times 3$ matrix $A$ and we want to permute it's rows

Let's list all possible permutation matrices for $3 \times 3$

  • $\begin{bmatrix}

1 & 0 & 0\\ 0 & 1 & 0\\ 0 & 0 & 1\\ \end{bmatrix}$ - permutes nothing

  • $\begin{bmatrix}

0 & 1 & 0\\ 1 & 0 & 0\\ 0 & 0 & 1 \end{bmatrix}$ - permutes 1st and 2nd rows

  • $\begin{bmatrix}

0 & 0 & 1\\ 0 & 1 & 0\\ 1 & 0 & 0\\ \end{bmatrix}$ - 1st and 3rd

  • $\begin{bmatrix}

1 & 0 & 0\\ 0 & 0 & 1\\ 0 & 1 & 0\\ \end{bmatrix}$ - 2nd and 3rd

  • $\begin{bmatrix}

0 & 1 & 0\\ 0 & 0 & 1\\ 1 & 0 & 0\\ \end{bmatrix}$ - 2nd, 3rd and 1st

  • $\begin{bmatrix}

0 & 0 & 1\\ 1 & 0 & 0\\ 0 & 1 & 0\\ \end{bmatrix}$ - 3, 1, 2


Permutations

In how many ways we can permute rows of $I_n$?

  • it's the number of permutations of $n$: $n!$


Types

Row Exchange

$\begin{bmatrix} 0 & 1\\ 1 & 0 \end{bmatrix} \times \begin{bmatrix} a & b\\ c & d \end{bmatrix} = \begin{bmatrix} c & d\\ a & b \end{bmatrix}$


Column Exchange

What if we want to exchange columns?

$\left[ \; \; \LARGE ? \; \; \; \right] \times \begin{bmatrix} a & b\\ c & d \end{bmatrix} = \begin{bmatrix} b & a\\ d & c \end{bmatrix}$


Can't put such a matrix on the left! Put in on the right instead

$\begin{bmatrix} a & b\\ c & d \end{bmatrix} \times \begin{bmatrix} 0 & 1\\ 1 & 0 \end{bmatrix} = \begin{bmatrix} b & a\\ d & c \end{bmatrix}$


Properties

  • When we transpose $P$ or inverse, the obtained matrix is also a permutation matrix
  • $P^{-1} = P^T$
  • thus $P^T P = P P^T = I$


Sources

Share your opinion