# LU-decomposition of A

I have:

$A=\begin{bmatrix} 2 & -1 & 2 & 3 & 4 \\ 4 & -2 & 7 & 7 & 6 \\ 2 & -1 & 20 & 9 & -8 \end{bmatrix}$

and I'm asked to LU-decomposition A, then solve $Ax=0$.

What I did:

With these steps:

$1)$ $R2=R2-2\times R1$

$2)$ $R3=R3-R1$

I got:

$U=\begin{bmatrix} 2 & -1 & 2 & 3 & 4 \\ 0 & 0 & 3 & 1 & -2 \\ 0 & 0 & 18 & 6 & -12 \end{bmatrix}$

$L=\begin{bmatrix} 1 & 0 & 0 \\ 2 & 1 & 0 \\ 1 & 0 & 1 \end{bmatrix}$

And because:

$Ax=b\hspace{12mm}L(Ux)=b$

$Ly=b\hspace{12mm}Ux=y$

I got:

$Ly=0$

$\begin{bmatrix} 1 & 0 & 0 \\ 2 & 1 & 0 \\ 1 & 0 & 1 \end{bmatrix} \begin{bmatrix} y_1 \\ y_2 \\ y_3 \end{bmatrix} = \begin{bmatrix} 0 \\ 0 \\ 0 \end{bmatrix}$

Using this step:

$1)$ $R2=R2-2\times R1$

I got $y=0$

Then solving:

$Ux=y$

$\begin{bmatrix} 2 & -1 & 2 & 3 & 4 \\ 0 & 0 & 3 & 1 & -2 \\ 0 & 0 & 18 & 6 & -12 \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \\ x_3 \\ x_4 \\ x_5 \end{bmatrix} = \begin{bmatrix} 0 \\ 0 \\ 0 \end{bmatrix}$

And using this steps:

$1)$ $R1=R1+2\times R2$

$2)$ $R3=\frac{R3}{6}$

$3)$ $R3=R3-R2$

I got:

$\begin{cases} x_2=2x_1+8x_3+5x_4 \\ x_4=-3x_3+2x_5 \\ x_1\,,\,x_3\,,\,x_5\quad free \end{cases}$

And I chose free variables to be $x_1=1$ , $x_3=1$ , $x_5=1$ so I got:

$\begin{cases} x_1=1 \\ x_2=5 \\ x_3=1 \\ x_4=-1 \\ x_5=1 \end{cases}$

Just wondering if I have done it right? And if not, then how should I do it?

• The point of using the LU decomposition is that you can solve the sets where you first find $y$ and then $x$ by substitution. For example, from the form of $L$, you immediately have $y_1 = 0$, then $y_2 = 0$ ( by substitution of the solution of $y_1$ in the second equation. And doing the same gives $y_3 = 0$. The same trick applies to find $x$. (By backwards substitution, so working bottom-up). – Student Mar 18 '17 at 18:19
• So you mean $x$ is also $0$ ? I didn't quite undestood what you mean, it would be nice if you could show it as example. – RedRose Mar 18 '17 at 18:29
• That is one solution, but there are possible more solutions. It think (1,2,0,0,0) is a solution. – Student Mar 18 '17 at 18:30
• Hmm... But what about L and U matrices, are they correct? – RedRose Mar 18 '17 at 18:33
• They have the right form and there multiplication gives $A$ so yes :) – Student Mar 18 '17 at 18:54

First of all, LU-decomposition is useful for a number of reasons, let me give you one. Suppose you have to solve $Ax = b_1, Ax = b_2, \ldots, Ax = b_n$, you can do this simultaneously by row reducing the augmented matrix $$\begin{pmatrix} A & | & b_1 & b_2 & \ldots &b_n \end{pmatrix}$$ and although this is very practical for small matrices $A$ it becomes very time costly to do this for large matrices. A better way is by finding the LU decomposition of $A$ and solving the following systems of equations: $$Ly = b \quad \text{ and } Ux = y.$$ The reason this works is because solving equations of systems given by a triangular matrix is extremely easy, using what is called forward (in case of a lower triangular matrix) or backward (in case of an upper triangular matrix) substitution. Indeed, suppose we have a lower triangular $3 \times 3$-matrix $L$ and the following system: $$\begin{pmatrix} u_{11} & 0 & 0 \\ u_{21} & u_{22} & 0 \\ u_{31} & u_{32} & u_{33} \end{pmatrix} \begin{pmatrix} x_1 \\ x_2\\ x_3 \end{pmatrix} = \begin{pmatrix} b_1\\b_2\\b_3 \end{pmatrix}$$ then we have from the first row that $x_1 = \frac{b_1}{u_{11}}$ (in case $u_{11}$ is non zero) and plugging in this value for $x_1$ in the second row, we find a unique value for $x_2$ (in case $u_{22}$ is nonzero) and plugging in the values of $x_1, x_2$ in the third row gives us $x_3$. Hence the name 'forward substitution'.

Now for your question: You have found two correct LU decompositions, but I like the one in your question better than the one in your answer since the one in your answer uses an extra (unnecessary) step. So let me work with your first candidate for LU decompostion. I will take over your (correct) result, in order to make this answer easier to follow.

$$L=\begin{pmatrix} 1 & 0 & 0 \\ 2 & 1 & 0 \\ 1 & 0 & 1 \end{pmatrix} \quad \text{ and } \quad U=\begin{pmatrix} 2 & -1 & 2 & 3 & 4 \\ 0 & 0 & 3 & 1 & -2 \\ 0 & 0 & 18 & 6 & -12 \end{pmatrix}.$$ Your idea of using this LU decomposition of $A$ to solve $Ax = \vec{0}$ was correct: first we solve $Ly = \vec{0}$ and then we solve $Ux = y$. So let's take a closer look to the first step. We have the following matrix equation: $$\begin{pmatrix} 1 & 0 & 0 \\ 2 & 1 & 0 \\ 1 & 0 & 1 \end{pmatrix} \begin{pmatrix} y_1 \\ y_2\\ y_3 \end{pmatrix} = \begin{pmatrix} 0\\0\\0\end{pmatrix}.$$ Using the forward substitution I have described, we find from the first row that $y_1 = 0$. Plugging this value in row two, we find $2y_2 = 0$, hence $Y_2 = 0$ and by the same principle, we have from row $3$ that $Y_3 = 0$. So we find that $(y_1, y_2, y_3)^T = (0,0,0)^T$ (which should not be a surprise, since the $L$ matrix is invertible in this case, making the solution unique and the zero vector is obviously a solution).

Now for your second step. We want to solve the following matrix equation: $$\begin{pmatrix} 2 & -1 & 2 & 3 & 4 \\ 0 & 0 & 3 & 1 & -2 \\ 0 & 0 & 18 & 6 & -12 \end{pmatrix}\begin{pmatrix}x_1\\x_2\\x_3\\x_4\\x_5\end{pmatrix} = y = \begin{pmatrix}0\\0\\0\end{pmatrix}.$$

You already saw in your answer to your own question that the free variables are $x_2, x_4, x_5$. The reason we have free variables is because we have three equations (and from the $U$ matrix, we see that the last row is equal to the second row, so only $2$ equations) for $5$ variables.

In order to solve this problem and to find all possible solutions, we can do the following: First we solve the system of equations setting $x_4 = 0 = x_5$ (the resulting system of equations has three equations and three variables). We also solve the system of equations where we set $x_2 = x_5 = 0$ and we also solve this system of equations for $x_2 = x_4 = 0$. (These are three separate steps.)

$\color{red}{\text{Solution 1:$x_4 = 0 = x_5$}}$ Using backward substitution, we find that (from the last row of $U$) $x_3 = 0$. From the second equation, we don't get new information. The first equation gives us $2x_1 = x_2$. Since $x_2$ is a free variable, we can set $x_2 = 2$. The resulting solution is $x = (1,2,0,0,0)^T$. Note how easy this solution follows from the upper triangular structure of $U$: we just substituted solutions.

$\color{red}{\text{Solution 2:$x_2 = 0 = x_5$}}$ Using these values, we find from the last row that $18x_3 = -6x_4$. Picking $x_4 = 3$, we find that $x_3 = -1$. The second row does not give new information. From the first row, we find $2x_1 = -2x_3 - 3x_4$, hence we have that $x_1 = \frac{-7}{2}$. This gives the solution $x = (\frac{-7}{2}, 0, -1, 3, 0)^T$. If you do not like fractions, you could have taken $x_4 = 6$, which leads to the solution $(-7, 0, -2, 6, 0)^T$.

$\color{red}{\text{Solution 3:$x_2 = 0 = x_4$}}$ Once again, using backward substitution, we find from the last equation that $18x_3 = -12x_5$ and since $x_5$ is a free variable, we can give it the value $x_5 = 6$, making $x_3 = -4$. The second row does not give any new information. The first row give us $2x_1 = -2x_3 -4x_5$. Using our solution for $x_3$ and the value of $x_5$, we find that $x_1 = \frac{1}{2}(-2 \cdot (-4) - 4 \cdot 6) = -8$. Hence we find the solution $x = (-8, 0, 4, 0, 6)^T$.

Now all possible solutions of the given system are linear combinations of these three solutions (so your solution in your answer should also be). Indeed, if $Ax_1 = 0 = Ax_2$, then we have that $A(\lambda_1x_1 + \lambda_2x_2) = \lambda_1Ax_1 + \lambda_2Ax_2 = 0+0 = 0$, where the $\lambda_i$ are real numbers.

This is the general way to proceed. What I did with giving some of the free variables the value $0$ (leading to my 'three' solutions) is actually what you did to obtain one possible solution. The reason I took zero is because this gives easier computations. Note that setting all three free variables equal to zero gives the trivial zero solution. The computations I have made should be correct, but if you would find some computational error, let me know :)

• Thank you very much for your very detailed answer :) But just wondering why did you put in "solution 1" that "$T$" as in $x=(...)^T$? – RedRose Mar 19 '17 at 12:38
• @RedRose: I initially denoted $x$ to be a columnvector, whereas I denoted my solution as a rowvector. The $'T'$ stands for 'transpose', meaning that you change a row into a column and vice versa. Now that you mentioned it, it saw that I was to lazy to do it everywhere, my apologies :) – Student Mar 19 '17 at 12:46
• No problem :) Yes I know what for "$T$" stands, but isn't it enough to put $x=(...)$ or do I need put e.g. my answer too as $x=(...)^T$? – RedRose Mar 19 '17 at 12:49
• @RedRose: Actually, yes, since $x$ is a columnvector in the problem. However, I don't think that people will not understand what you have done if you would denote it without the $T$. Conclusion: perhaps you (and I) should do it, so people can't nitpick on these minor details ;) I will edit my answer ;) – Student Mar 19 '17 at 13:03
• Yes, I edited my answer too :) – RedRose Mar 19 '17 at 13:23

$A=\begin{bmatrix} 2 & -1 & 2 & 3 & 4 \\ 4 & -2 & 7 & 7 & 6 \\ 2 & -1 & 20 & 9 & -8 \end{bmatrix}$

With these steps:

$1)$ $R2=R2-2\times R1$

$2)$ $R3=R3-R1$

$3)$ $R3=R3-6\times R2$

I got:

$U=\begin{bmatrix} 2 & -1 & 2 & 3 & 4 \\ 0 & 0 & 3 & 1 & -2 \\ 0 & 0 & 0 & 0 & 0 \end{bmatrix}$

$L=\begin{bmatrix} 1 & 0 & 0 \\ 2 & 1 & 0 \\ 1 & 6 & 1 \end{bmatrix}$

Solving $x$ from $Ax=0$:

$Ly=0$

$\begin{bmatrix} 1 & 0 & 0 \\ 2 & 1 & 0 \\ 1 & 0 & 1 \end{bmatrix} \begin{bmatrix} y_1 \\ y_2 \\ y_3 \end{bmatrix} = \begin{bmatrix} 0 \\ 0 \\ 0 \end{bmatrix} \Longrightarrow \begin{cases} y_1=0 \\ 2y_1+y_2=0 \\ y_1+6y_2+y_3=0 \end{cases} \Longrightarrow \begin{cases} y_1=0 \\ y_2=0 \\ y_3=0 \end{cases} \Longrightarrow y= \begin{bmatrix} 0 \\ 0 \\ 0 \end{bmatrix} =0$

$Ux=y$

$Ux=0$

$\begin{bmatrix} 2 & -1 & 2 & 3 & 4 \\ 0 & 0 & 3 & 1 & -2 \\ 0 & 0 & 0 & 0 & 0 \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \\ x_3 \\ x_4 \\ x_5 \end{bmatrix} = \begin{bmatrix} 0 \\ 0 \\ 0 \end{bmatrix}$

And using this steps (to get echelon form):

$1)$ $R1=\frac{R1}{2}$

$2)$ $R1=R1+R2$

$3)$ $R2=\frac{R2}{3}$

And since the pivot columns of the matrix are $1$ and $3$, so the basic variables are $x_1$ and $x_3$. The remaining variables, $x_2\,,\,x_4$ and $x_5$ must be free.

I got:

$\begin{cases} x_1=\frac{1}{2}x_2-4x_3-\frac{5}{2}x_4 \\ x_3=-\frac{1}{3}x_4+\frac{2}{3}x_5 \\ x_2\,,\,x_4\,,\,x_5\quad free \end{cases}$

And I chose free variables to be $x_2=2$ , $x_4=6$ , $x_5=3$ so I got:

$\begin{cases} x_1=-14 \\ x_2=2 \\ x_3=0 \\ x_4=6 \\ x_5=3 \end{cases} \Longrightarrow x=\begin{bmatrix} -14 \\ 2 \\ 0 \\ 6 \\ 3 \end{bmatrix} =\begin{bmatrix} -14 & 2 & 0 & 6 & 3 \end{bmatrix}^T$

And I check it out by calculating:

$\Rightarrow L\times U$ and I got the $A$ so L and U matrices are correct

$\Rightarrow A\times x$ and I got $0$ so it $x$ values are correct, since it is true when $0=0$

Here is a photo of what I have done with the coefficients of $x_3$ and $x_4$:

• I was just started typing an answer and my first remark was, that indeed, your initial choice of free variables was wrong. The free variables are indeed $x_2, x_4, x_5$. The point is that you can set multiple values for these 'free variables', leading to different solutions. Moreover, any linear combination of these possible solutions will again be a solution. Note that in your resulting system of two equations, you still have and $x_5$ in your first equation! – Student Mar 19 '17 at 10:48
• Yes right, I can get different solutions for x values if I choose different values for free parameters. And I just realized today in morning how shoul I have done it. :) – RedRose Mar 19 '17 at 10:52
• In the 'I got.'-part of your answer: your first equation still has a $x_5$ part (you forgot $-2x_5$ in your equation!). I will write an answer on how you can find all possible solutions systematically in case you have some free variables. Also, I am not quite sure what you have done with the coefficients of $x_3$ and $x_4$ in that equation. – Student Mar 19 '17 at 10:55
• Okey, thanks. But in which equation there is $-2x_5$? In $x_1=...$ or $x_3=...$? – RedRose Mar 19 '17 at 11:00
• The only thing i would like to add is that in order to find all possible solutions, you should set one free variable equal to some non zero real number and the others equal to zero and repeat this for all free variables. For example: first take $x_2 = 2$ and $x_4 = x_5 = 0$ leading to $(1, 2, 0,0,0)$ and do this also for $x_4, x_5$. – Student Mar 19 '17 at 11:26