Generalizing permutation matrices

Question

I'm working on LU factorization that involves pivoting rows and I'm still trying to work my head around how to obtain the permutation matrices with ease.

Say I want to interchange two rows. If I have something as simple as $A = \begin{bmatrix} a & b \\ c & d \end{bmatrix}$ then I can left multiply by $P = \begin{bmatrix} p_1 & p_2 \\ p_3 & p_4 \end{bmatrix}$, form a system under these matrices so that Gaussian elimination gives me $P = \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix}$, satisfying \begin{equation*} \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix} \begin{bmatrix} a & b \\ c & d \end{bmatrix} = \begin{bmatrix} c & d \\ a & b \end{bmatrix} \end{equation*}

But how do I do this for larger matrices between any arbitrary rows? Is there a fast algorithm that allows me to do this?

Answer 1

We say that $P$ is a permutation matrix if any row and any column have exactly one element equals 1 while the others are equals 0. Take, for example: $$ P = \begin{bmatrix} 1&0&0\\0&0&1\\0&1&0\end{bmatrix}$$

Let $A$ be a $3\times 3$ matrix. If $PA = A'$, $A'$ will be equal the following row swapping of $A$:

• The first row of $A'$ is equal the first row of $A$, because the first row of $P$ has $1$ in the 1st column.

• The second row of $A'$ is equal the third row of $A$, because the second row of $P$ has $1$ in the 3rd column.

• The third row of $A'$ is equal the second row of $A$, because the second row of $P$ has $1$ in the 2rd column.

I hope that the explanation was clear!