# Find LU decomposition of a matrix using partial pivoting

I've the following matrix:

$$A= \begin{bmatrix} 0& 7& 5& 1 \\ 4& 3& 2& 1 \\0 &0& 0& 1 \\ 0& 0& -1& -2 \end{bmatrix}$$

and I need to find the matrices $P, L$ and $U$, such that

$$PA = LU$$

what I need was to find the matrices representing the guassian elimination operations to obtain the upper triangle, and I found the following two:

$$l_2 l_2 A = U$$

specifically:

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

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

such that $$l_2 l_1 A = PA = U$$

where $$U = \begin{pmatrix} 4 & 3& 2& 1 \\ 0 & 7& 5& 1 \\0 & 0& -1& -2 \\ 0 & 0& 0& 1 \end{pmatrix}$$ So, what's the lower triangular matrix of this $LU$ decomposition? Is it the identity matrix?

• $\text{ P = }\left( \begin{array}{cccc} 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \\ \end{array} \right)$, $\text{ L = }\left( \begin{array}{cccc} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ \end{array} \right)$, $\text{ U = }\left( \begin{array}{cccc} 4 & 3 & 2 & 1 \\ 0 & 7 & 5 & 1 \\ 0 & 0 & -1 & -2 \\ 0 & 0 & 0 & 1 \\ \end{array} \right)$. Check $PA = LU$. – Moo May 1 '16 at 19:28
• @Moo Now, try to find for example the solution to the equation $A x = (26, 9, 1, -3)^T$. At least from my calculations, i.e. using $L$ and $U$ as you're and me are saying it seems that something is wrong because the solution that I found is wrong, even though $PA = LU$. – nbro May 1 '16 at 22:50
• Works perfectly! – Moo May 1 '16 at 23:17
• @Moo Could you please then show me and explain how are you doing it then? I've probably misunderstood something... – nbro May 2 '16 at 10:25
• @Moo Sorry man, I've time only now to have a look at your answer and explanations. I will give you some feedback in a few minutes. – nbro May 4 '16 at 21:05

For $A= \begin{pmatrix} 0& 7& 5& 1 \\ 4& 3& 2& 1 \\0 &0& 0& 1 \\ 0& 0& -1& -2 \end{pmatrix}$, we have:

$$\text{ P = }\left( \begin{array}{cccc} 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \\ \end{array} \right), \text{ L = }\left( \begin{array}{cccc} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ \end{array} \right), \text{ U = }\left( \begin{array}{cccc} 4 & 3 & 2 & 1 \\ 0 & 7 & 5 & 1 \\ 0 & 0 & -1 & -2 \\ 0 & 0 & 0 & 1 \\ \end{array} \right)$$

You can easily verify that:

$$PA = LU$$

Next, we want to use this result to solve $Ax = b$ such that:

$$\begin{pmatrix} 0& 7& 5& 1 \\ 4& 3& 2& 1 \\0 &0& 0& 1 \\ 0& 0& -1& -2 \end{pmatrix}x = \begin{pmatrix} 26 \\ 9 \\1 \\ -3 \end{pmatrix}$$

The general process is:

• Construct $L, U, P$ as shown above
• Compute $Pb$
• Solve $Ly = Pb$ for $y$ using Forward Substitution
• Solve $Ux = y$ for $x$ using Back Substitution

So, forming $Ly = P b$ and using forward substitution gives:

$$\left( \begin{array}{cccc} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ \end{array} \right) y = \begin{pmatrix} 9 \\ 26 \\ -3 \\ 1 \end{pmatrix} \implies y = \begin{pmatrix} 9 \\ 26 \\ -3 \\ 1 \end{pmatrix}$$

Next, we form $Ux = y$ in order to be able to solve for $x$ using back substitution:

$$\begin{pmatrix} 4& 3& 2& 1 \\ 0& 7& 5& 1 \\ 0& 0& -1& -2 \\ 0 &0& 0& 1 \end{pmatrix} \begin{pmatrix} x_1 \\ x_2 \\ x_3 \\ x_4 \end{pmatrix} = \begin{pmatrix} 9 \\ 26 \\ -3 \\ 1 \end{pmatrix}$$

Using back substitution, this yields:

$$x = \begin{pmatrix} x_1 \\ x_2 \\ x_3 \\ x_4 \end{pmatrix} = \begin{pmatrix} -\dfrac{9}{14} \\ \dfrac{20}{7} \\ 1 \\ 1 \end{pmatrix}$$

• I think you did a mistake in your calculations because the initial vector was $(9, 26, 1, -3)^T$ and not $(9, 26, -3, 1)^T$. – nbro May 5 '16 at 11:20
• Point 1: Recall from my steps above, we MUST setup $Ly = Pb$ and use forward substitution. What is $Pb$ in this case? Point 2: Test the solution, does it satisfy the system? – Moo May 5 '16 at 11:44
• Ok, sorry, I read part of the answer yesterday and part today. You're right, you multiplied first $P$ with $b$, what I don't understand exactly is why, maybe it's because I didn't think about how can we use $U$ and $L$ in general to solve a system of the form $Ax = b$. And yes, I got the same answer now. – nbro May 5 '16 at 11:50
• That is the reason I added that outline, because we also need to understand how to use the items we found that include the permutation matrix, as well as $U$ and $L$. – Moo May 5 '16 at 12:03