# PA = LU Decomposition with Row Exchange

I am not sure how to deal with the L with we do row exchange in PA = LU decomposition. Here's my example:

$A = \left[ {\begin{array}{ccc} 1 & 1 & 1\\ 0 & 0 & 1\\ 2 & 3 & 4\\ \end{array} } \right]$

Step 1: Swap row 1 and row 3

$U = \left[ \begin{array}{ccc} 2 & 3 & 4\\ 0 & 0 & 1\\ 1 & 1 & 1\\ \end{array} \right]$

$P = \left[ \begin{array}{ccc} 0 & 0 & 1\\ 0 & 1 & 0\\ 1 & 0 & 0\\ \end{array} \right]$

Step 2: row 3 <-- (-1/2) * row 1 + row 3

$U = \left[ \begin{array}{ccc} 2 & 3 & 4\\ 0 & 0 & 1\\ 0 & 1 & 2\\ \end{array} \right]$

$P = \left[ \begin{array}{ccc} 0 & 0 & 1\\ 0 & 1 & 0\\ 1 & 0 & 0\\ \end{array} \right]$

Step 3: swap row 2 and row 3

$U = \left[ \begin{array}{ccc} 2 & 3 & 4\\ 0 & 1 & 2\\ 0 & 0 & 1\\ \end{array} \right]$

$P = \left[ \begin{array}{ccc} 0 & 0 & 1\\ 1 & 0 & 0\\ 0 & 1 & 0\\ \end{array} \right]$

Therefore: $L = \left[ \begin{array}{ccc} 1 & 0 & 0\\ 1/2 & 1 & 0\\ 0 & 0 & 1\\ \end{array} \right]$ The reason why I build L at the last step, is because we are sure the order of the rows after the row swaps so we can plug the low diagonal elements back to L. Element (2,1) is 1/2 because of step 2, the rest of lower diagonals are 0 because in row 3 elements (3,1) and (3,2) are originally 0s.

But I tried to use L * U but it doesn't equal to L*A. Could someone explain why I am wrong? Thanks!

## 1 Answer

When you check you answer you have to check it by PA = LU.

What I did first was put A in an upper triangle.

$A = \left[ {\begin{array}{ccc} 1 & 1 & 1\\ 0 & 0 & 1\\ 2 & 3 & 4\\ \end{array} } \right]$

Step 1: $r_3$-2$r_1$→$r_3$

$= \left[ \begin{array}{ccc} 1 & 1 & 1\\ 0 & 0 & 1\\ 0 & 1 & 2\\ \end{array} \right]$

Step 2: $r_3$⟷$r_2$

$= \left[ \begin{array}{ccc} 1 & 1 & 1\\ 0 & 1 & 2\\ 0 & 0 & 1\\ \end{array} \right]$ $$\\$$ Now, every row swap you did on matrix A you to that to a 3x3 identity matrix because A is a 3x3 matrix.

$P = \left[ \begin{array}{ccc} 1 & 0 & 0\\ 0 & 1 & 0\\ 0 & 0 & 1\\ \end{array} \right]$

Step 3: $r_3$⟷$r_2$

$= \left[ \begin{array}{ccc} 0 & 0 & 1\\ 1 & 0 & 0\\ 0 & 1 & 0\\ \end{array} \right]$ $$\\$$ Now form C=PA because it will have an LU decomposition.

$$\begin{bmatrix} 1 & 0 & 0 \\ 0 & 0 & 1 \\ 0 & 1 & 0 \end{bmatrix} \times \begin{bmatrix} 1 & 1 & 1 \\ 0 & 0 & 1 \\ 2 & 3 & 4 \end{bmatrix} = \begin{bmatrix} 1 & 1 & 1 \\ 2 & 3 & 4 \\ 0 & 0 & 1 \end{bmatrix}$$ $$\\$$ Now you find the LU decomposition on matrix C. And you get:

$U = \left[ {\begin{array}{ccc} 1 & 1 & 1\\ 0 & 1 & 2\\ 0 & 0 & 1\\ \end{array} } \right]$

$L = \left[ {\begin{array}{ccc} 1 & 0 & 0\\ 2 & 1 & 0\\ 0 & 0 & 1\\ \end{array} } \right]$

• Very clear answer, thank you! – munmunbb Jun 25 '17 at 21:02
• I think you made a typo in your answer and wrote 0 instead of 1 in u22 field of the U matrix in the final C=LU equation. – kalmor Nov 11 '17 at 15:00
• but do anyone know, why we do this PA=LU decomposition? in which cases one should do (use) it? – ZelelB Jun 20 '18 at 20:26