# How is the permutation matrix found in $A = P^tLU$ factorization?

I am learning how to factorize a matrix into the form $A = P^tLU$, and I am not understanding how the permutation matrix is obtained.

A = $\begin{bmatrix} 0 & 0 & -1 & 1\\ 1 & 1 & -1 & 2\\ -1 & -1 & 2 & 0\\ 1 & 2 & 0 & 2 \end{bmatrix}$

Row interchange $(E_1) \leftrightarrow (E_2)$, followed by $(E_3 + E_1) \rightarrow (E_3)$ and $(E_4 - E_1) \rightarrow (E_4)$ gives

$\begin{bmatrix} 1 & 1 & -1 & 2\\ 0 & 0 & -1 & 1\\ 0 & 0 & 1 & 2\\ 0 & 1 & 1 & 0 \end{bmatrix}$

Row interchange $(E_2) \leftrightarrow (E_4)$, followed by $(E_4 + E_3) \rightarrow (E_4)$ gives

U = $\begin{bmatrix} 1 & 1 & -1 & 2\\ 0 & 1 & 1 & 0\\ 0 & 0 & 1 & 2\\ 0 & 0 & 0 & 3 \end{bmatrix}$

The permutation matrix associated with the row interchange $(E_1) \leftrightarrow (E_2)$ and $(E_2) \leftrightarrow (E_4)$ is

P = $\begin{bmatrix} 0 & 1 & 0 & 0\\ 0 & 0 & 0 & 1\\ 0 & 0 & 1 & 0\\ 1 & 0 & 0 & 0 \end{bmatrix}$

How is $P$ obtained?

I think you must have written something wrong.

When you are permuting rows, that tells you what $P$ is.

You have, the permutation matrix associated with the row interchange $(E_1) \rightarrow (E_4)$ and $(E_2) \rightarrow (E_1)$ and $(E_4) \rightarrow (E_2)$. Row $E_3$ stayed put.

P = $\begin{bmatrix} 0 & 1 & 0 & 0\\ 0 & 0 & 0 & 1\\ 0 & 0 & 1 & 0\\ 1 & 0 & 0 & 0 \end{bmatrix}$

The way you would have come up with this permutation is by creating the augmented system using $A$, doing row eliminations, and swapping rows as the $P$ matrix says to get an upper triangular matrix.

Does that make sense? Take the matrix $A$, do Gaussian elimination on it and see how you would swap rows and you should get that P.

What you are actually doing is trying to write:

$$PAx = Pb.$$

Since $P^{-1} = P^{T}$, you end up with:

$$A = (P^T L) U$$

You show a $U$ above. If they gave you $A, P \text{and} U$, it is simple to find $L$.

However, you should be able to do this entire process just from $A$. If no $b$ is give, just skip that part of the problem and simply find $A = P^TLU$.

• I corrected my typos. – badjr Apr 7 '13 at 7:26
• Well done, and nicely explained! +1 – Namaste Apr 8 '13 at 0:47