<s>[INST] 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?
 [/INST] 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}$$
</s>