Find LU decomposition of a matrix using partial pivoting

Question

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?

Answer 1

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}$$