# Finding the $LU$ factorization of the matrix

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$

• have you tried to invert U and multiply the inversion by the right ? – GBes Jul 4 '18 at 15:33
• No, I actually have no idea how to get $L$. So, you say that I need to invert $U$ and then multiply the inverse with $U$ itself? – user572932 Jul 4 '18 at 15:37

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

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}

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.

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