Finding the $LU$ factorization of the matrix

Question

Find the $LU$ factorization of the matrix: $$\begin{bmatrix} 1 & 1 & 1 \\ 3 & 5 & 6 \\ -2 & 2 & 7 \end{bmatrix}$$

I am aware that I need to find $L=\begin{bmatrix} 1 & 0 & 0 \\ * & 1 & 0 \\ * & * & 1 \end{bmatrix}$ and $U=\begin{bmatrix} 1 & * & * \\ 0 & 1 & * \\ 0 & 0 & 1 \end{bmatrix}$

I did row transformations and got $U=\begin{bmatrix} 1 & 1 & 1 \\ 0 & 2 & 3 \\ 0 & 0 & 3 \end{bmatrix}$ but I couldn't understand how to find $L=\begin{bmatrix} 1 & 0 & 0 \\ * & 1 & 0 \\ * & * & 1 \end{bmatrix}$

Can anyone explain how to find $L$

Answer 1

For doing LU decomposition, you need to do Gaussian elimination. Here I'll just help you with the procedure, but if you want to understand why I recommend you to see this pdf http://www.math.iit.edu/~fass/477577_Chapter_7.pdf. Lets apply Gaussian elimination to A \begin{equation*} A = \left[ \begin{matrix} 1 & 1 & 1\\ 3 & 5 & 6 \\ -2 & 2 & 7 \end{matrix} \right] \end{equation*} For eliminating $A_{12}$ and $A_{13}$, we need to multiply by $-3$ and by $2$ the first row and add this to the second and third row respectively, obtaining \begin{equation*} \left[ \begin{matrix} 1 & 1 & 1\\ 0 & 2 & 3 \\ 0 & 4 & 9 \end{matrix} \right] \end{equation*} Now we eliminate $A_{32}$ multiplying by $-2$ the second row and adding it to the third one, obtaining \begin{equation*} \left[ \begin{matrix} 1 & 1 & 1\\ 0 & 2 & 3 \\ 0 & 0 & 3 \end{matrix} \right] \end{equation*} Which is the $U$ matrix, for the $L$ matrix we use the factors by which we multiplied each row for obtaining the $U$ matrix, i.e. $3,-2,2$. We use this elements in the position of the elements they eliminated, then \begin{equation*} L = \left[ \begin{matrix} 1 & 0 & 0\\ 3 & 1 & 0 \\ -2 & 2 & 1 \end{matrix} \right] \end{equation*}

Answer 2

Going off of GBes's comment, you can find $L$ through some quick matrix multiplication. Let's call the original matrix $A$. We know that $A=LU$, and since you have $U$ (which is invertible), you can multiply by $U^{-1}$ on the right on both sides to get the following: $$\begin{align} A&=LU \\ AU^{-1}&=LUU^{-1} \\ AU^{-1}&=L\end{align}$$

Answer 3

I use to call $E_{ij}(d)$ the operation of summing to the $i$-th row the $j$-th row multiplied by $d$.

Thus the Gaussian elimination runs as \begin{align} \begin{bmatrix} 1 & 1 & 1 \\ 3 & 5 & 6 \\ -2 & 2 & 7 \end{bmatrix} &\xrightarrow{\begin{gathered} E_{31}(2) \\ E_{21}(-3) \end{gathered}} \begin{bmatrix} 1 & 1 & 1 \\ 0 & 2 & 3 \\ 0 & 4 & 9 \end{bmatrix} \\[6px] &\xrightarrow{E_{32}(-2)} \begin{bmatrix} 1 & 1 & 1 \\ 0 & 2 & 3 \\ 0 & 0 & 3 \end{bmatrix}=U \end{align} Now it's just a matter of replacing each transformation by its inverse: $$ L=E_{21}(3)E_{31}(-2)E_{32}(2)= \begin{bmatrix} 1 & 0 & 0 \\ 3 & 1 & 0 \\ -2 & 2 & 1 \end{bmatrix} $$ At place $(2,1)$ put $3$, and so on.

This is justified by the fact that, if you consider $E_{ij}(d)$ the matrix you obtain by applying the transformation to the identity, then performing the row operation is the same as multiplying by this matrix.

Thus we have written $$ U=E_{32}(-2)E_{31}(2)E_{21}(-3)A $$ (where $A$ is your original matrix) and so $$ A=\underbrace{E_{21}(3)E_{31}(-2)E_{32}(2)}_{L}U $$ If one follows a strict order in doing the Gaussian elimination (top down and left to right), filling the matrix $L$ is just putting the coefficients in the indicated place.

Answer 4

Gaussian Elimination without Pivoting is as follows. The primary purpose of Gaussian elimination if you follow this is to find $\ell_{jk}$ which zeros out the row below. That is why it is the ratio of the two rows and then you subtract them. This continues on and on.

Suppose that

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

$$ U =A, L=I$$ $$ k=1,m=3,j=2$$ $$\ell_{21} = \frac{u_{21}}{u_{11}} = \frac{a_{21}}{a_{11}} = 3 $$ $$ u_{2,1:3} = u_{2,1:3} - 3 \cdot u_{1,1:3} $$ Then we're going to subtract 3 times the 1st row from the 2nd row $$ \begin{bmatrix} 3 & 5 & 6 \end{bmatrix} - 3 \cdot \begin{bmatrix} 1 & 1 & 1 \end{bmatrix} = \begin{bmatrix} 0 & 2 & 3\end{bmatrix} $$ Updating each of them $$U = \begin{bmatrix} 1 & 1 & 1 \\ 0 & 2 & 3 \\ -2 & 2 & 7 \end{bmatrix} $$ $$ L =\begin{bmatrix} 1 & 0 & 0 \\ 3 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix} $$ $$k=1,j=3,m=3 $$ $$\ell_{31} = \frac{u_{31}}{u_{11}} = \frac{-2}{1} = -2 $$ $$ u_{3,1:3} = u_{3,1:3} +2 \cdot u_{1,1:3} $$ Then we add two times the first row to the third row $$ \begin{bmatrix} -2 & 2 & 7 \end{bmatrix} + 2 \cdot \begin{bmatrix} 1 & 1& 1 \end{bmatrix} = \begin{bmatrix}0 & 4 & 9 \end{bmatrix} $$ Updating $$ U = \begin{bmatrix} 1 & 1 & 1 \\ 0 & 2 & 3 \\ 0 & 4 & 9 \end{bmatrix} $$ $$ L =\begin{bmatrix} 1 & 0 & 0 \\ 3 & 1 & 0 \\ -2 & 0 & 1 \end{bmatrix} $$ $$ k=2, j=3,m=3 $$ $$ \ell_{32} = \frac{u_{32}}{u_{22}} = \frac{4}{2} = 2$$ We're subtracting out little blocks $$ u_{3,2:3} = u_{3,2:3} - 2 \cdot u_{2,2:3} $$ $$ \begin{bmatrix} 4 & 9 \end{bmatrix} - 2 \cdot\begin{bmatrix} 2& 3 \end{bmatrix} = \begin{bmatrix} 0 & 3 \end{bmatrix} $$ Updating $$ U = \begin{bmatrix} 1 & 1 & 1 \\ 0 & 2 & 3 \\ 0 & 0 & 3 \end{bmatrix} $$ $$ L =\begin{bmatrix} 1 & 0 & 0 \\ 3 & 1 & 0 \\ -2 & 2 & 1 \end{bmatrix} $$ It now terminates $$ A = LU $$ $$ \underbrace{\begin{bmatrix} 1 & 1 & 1 \\ 3 & 5 & 6 \\ -2 & 2 & 7 \end{bmatrix}}_{A} = \underbrace{\begin{bmatrix} 1 & 0 & 0 \\ 3 & 1 & 0 \\ -2 & 2 & 1 \end{bmatrix}}_{L} \underbrace{\begin{bmatrix} 1 & 1 & 1 \\ 0 & 2 & 3 \\ 0 & 0 & 3 \end{bmatrix}}_{U} $$