retagged by
11,103 views
22 votes
22 votes

Consider solving the following system of simultaneous equations using $\text{LU}$ decomposition.

$$x_{1} + x_{2} – 2x_{3} = 4$$

$$x_{1} + 3x_{2} – x_{3} = 7$$

$$2x_{1} + x_{2} – 5x_{3} = 7$$

where $\textit{L}$ and $\textit{U}$ are denoted as

$L = \begin{pmatrix}L_{11} & 0 & 0 \\ L_{21} & L_{22} & 0 \\ L_{31} & L_{32} & L_{33} \end{pmatrix} , U = \begin{pmatrix}U_{11} & U_{12} & U_{13} \\ 0 & U_{22} & U_{23} \\ 0 & 0 & U_{33} \end{pmatrix}$

Which one of the following is the correct combination of values for $\textit{L}_{32}, \textit{U}_{33},$ and $x_{1}?$

  1. $\textit{L}_{32}=2, \textit{U}_{33}= – \frac{1}{2}, x_{1}= – 1$
  2. $\textit{L}_{32}=2, \textit{U}_{33}=2, x_{1}= – 1$
  3. $\textit{L}_{32}= – \frac{1}{2}, \textit{U}_{33}=2, x_{1}= 0$
  4. $\textit{L}_{32}= – \frac{1}{2}, \textit{U}_{33}= – \frac{1}{2}, x_{1}= 0$
retagged by

5 Answers

Best answer
28 votes
28 votes

Given question is incorrect and all the other answers are also incorrect because question says one option is correct but both (C) and (D) are correct here.

You can decompose the coefficient matrix in two ways as following:

$(1)$
   
$\begin{pmatrix}
1 & 1 & -2 \\
1 & 3 & -1 \\
2 & 1 & -5
\end{pmatrix}=\begin{pmatrix}
1 & 0 & 0 \\
1 & 1 & 0 \\
2 & \frac{-1}{2} & 1
\end{pmatrix}\begin{pmatrix}
1 & 1 & -2 \\
0 & 2 & 1 \\
0 & 0 & \frac{-1}{2}
\end{pmatrix}$
 
So, $L_{32}=\frac{-1}{2}$ and $U_{33}=\frac{-1}{2}$ 
   

$(2)$

$\begin{pmatrix}
1 & 1 & -2 \\
1 & 3 & -1 \\
2 & 1 & -5
\end{pmatrix}=\begin{pmatrix}
1 & 0 & 0 \\
1 & 1 & 0 \\
2 & \frac{-1}{2} & \frac{-1}{4}
\end{pmatrix}\begin{pmatrix}
1 & 1 & -2 \\
0 & 2 & 1 \\
0 & 0 & 2
\end{pmatrix}$

  
So, $L_{32}=\frac{-1}{2}$ and $U_{33}=2$ 
 
 
From the edit part at the end of this answer:
  
When $x=y=z=1,$ you get the first $LU$ decomposition and when $x=y=1$ and $z=\frac{-1}{4}$, you get the second $LU$ decomposition.
  
Now you can apply the method $(1)$ as given below and get the first $LU$ decomposition and to obtain the second $LU$ decomposition, you have to multiply third column of matrix $L$ in first $LU$ decomposition by $\frac{-1}{4}$ and divide the third row of matrix $U$ in first $LU$ decomposition by $\frac{-1}{4}$ as it is given in the below comment.
  
All the remaining things you can get from the rest of this answer.
---------------------------------------------------------------------------------------------------------------------------------------------------------

 

$\textbf{Method 1 (Shortcut)}:$

Here, we do $3$ elementary row operations on the following coefficient matrix $A$ to get $U$ as:


$ A = \begin{pmatrix}
1 & 1 & -2 \\
1 & 3 & -1 \\
2 & 1 & -5
\end{pmatrix} \xrightarrow[]{\text{$R_2\leftarrow\boldsymbol{-1}R_1 + R_2  $}} \begin{pmatrix}
1 & 1 & -2 \\
0 & 2 & 1 \\
2 & 1 & -5
\end{pmatrix} \xrightarrow[]{\text{$R_3\leftarrow\boldsymbol{-2}R_1 + R_3  $}} \begin{pmatrix}
1 & 1 & -2 \\
0 & 2 & 1 \\
0 & -1 & -1
\end{pmatrix}$

$ \xrightarrow[]{\text{$R_3\leftarrow\boldsymbol{\frac{1}{2}}R_2 + R_3  $}} \begin{pmatrix}
1 & 1 & -2 \\
0 & 2 & 1 \\
0 & 0 & \frac{-1}{2} 
\end{pmatrix}= \textbf{
U}
$


Now, to get $L,$ we just have to reverse the sign of the bold text which we have used in above row operations and put in that position of $L$ for which we have used the above row operations.


For Example, we have used $\boldsymbol{-1}R_1+R_2$ to make the position of second row and first column as zero. So, $L_{21} = 1.$ Similarly, $\boldsymbol{-2}R_1+R_3$ is used to make third row and first column as zero and so, $L_{31} = 2$ and $\boldsymbol{\frac{1}{2}}R_2+R_3$ is used to make third row and second column as zero and so, $L_{32} = \frac{-1}{2}.$ Since, diagonal elements of $U$ are not all $1s$ and hence, all diagonal elements of $L$ will be $1.$

Hence, $L = \begin{pmatrix}
1 & 0 & 0 \\
1 & 1 & 0 \\
2 & \frac{-1}{2} & 1 
\end{pmatrix}$ and $ U = \begin{pmatrix}
1 & 1 & -2 \\
0 & 2 & 1 \\
0 & 0 & \frac{-1}{2} 
\end{pmatrix}$


Therefore, $\textbf{(D)}$


If anyone wants to know why this works then reason lies in the third method below and you can see the results of $E_{21}^{-1},E_{31}^{-1},E_{32}^{-1}$ to know why it works.

$\textbf{Method 2:}$

$x_1 + x_2 -2x_3  = 4 \qquad   (1)$

$x_1 + 3x_2 -x_3  = 7 \qquad   (2)$

$2x_1 + x_2 -5x_3  = 7\qquad(3)$

$2 eq(2) – eq(3)$ gives $5x_2 + 3x_3 = 7 $

$2 eq(1) – eq(3)$ gives $x_2 + x_3 = 1 \implies 5x_2 + 5x_3 = 5$

Solving  $5x_2 + 3x_3 = 7 $ and $5x_2 + 5x_3 = 5$ gives $x_3=-1, x_2=2$ and by putting it in $eq(1),$ we get, $x_1=0$

So, $x_1=0,$ it means either option $(C)$ is correct or $(D)$

Now, we only need to find $U_{33}$ and get the answer for the given question.

To find $LU$ decomposition (if it is possible), we only need to convert the given matrix into $U$ by elementary row operations in Gaussian Elimination method (described at the end of the answer to find the complete solution for the given questions).

So, here, $A= \begin{bmatrix} 1 &1 &-2 \\ 1 &3 &-1 \\ 2 &1 &-5 \end{bmatrix}$

After $R_2 \leftarrow R_2 – R_1,$ $A$ becomes  $\begin{bmatrix} 1 &1 &-2 \\ 0 &2 &1 \\ 2 &1 &-5 \end{bmatrix}$

After $R_3 \leftarrow R_3 – 2R_1,$ $A$ becomes  $\begin{bmatrix} 1 &1 &-2 \\ 0 &2 &1 \\ 0 &-1 &-1 \end{bmatrix}$

After $R_3 \leftarrow R_3 +\frac{1}{2}R_2,$ $A$ becomes  $\begin{bmatrix} 1 &1 &-2 \\ 0 &2 &1 \\ 0 &0 &\frac{-1}{2} \end{bmatrix}$

So, $U= \begin{bmatrix} 1 &1 &-2 \\ 0 &2 &1 \\ 0 &0 &\frac{-1}{2} \end{bmatrix}$

  It means $U_{33} = \frac{-1}{2}$

Hence, $\textbf{Answer: D}$

$\textbf{Method 3:}$

Now, to find the complete solution for the given question, we can use this previous year question to find the $LU$ decomposition and then find $x_1$

After Applying $R_2 \leftarrow R_2 – R_1,$ $A$ becomes $\begin{bmatrix} 1 &1 &-2 \\ 0 &2 &1 \\ 2 &1 &-5 \end{bmatrix}$ and $E_{21}$ becomes $\begin{bmatrix} 1 &0 &0 \\ -1 &1 &0 \\ 0 &0 &1 \end{bmatrix}$

After Applying $R_3 \leftarrow R_3 – 2R_1,$ $A$ becomes $\begin{bmatrix} 1 &1 &-2 \\ 0 &2 &1 \\ 0 &-1 &-1 \end{bmatrix}$ and $E_{31}$ becomes $\begin{bmatrix} 1 &0 &0 \\ 0 &1 &0 \\ -2 &0 &1 \end{bmatrix}$

After Applying $R_3 \leftarrow R_3 + \frac{1}{2}R_2,$ $A$ becomes $\begin{bmatrix} 1 &1 &-2 \\ 0 &2 &1 \\ 0 &0 &\frac{-1}{2} \end{bmatrix}$ and $E_{32}$ becomes $\begin{bmatrix} 1 &0 &0 \\ 0 &1 &0 \\ 0 &\frac{1}{2} &1 \end{bmatrix}$

So, $U= \begin{bmatrix} 1 &1 &-2 \\ 0 &2 &1 \\ 0 &0 &\frac{-1}{2} \end{bmatrix}$

and $E_{32}E_{31}E_{21}(A) = U$

$A= E_{21}^{-1} E_{31}^{-1}E_{32}^{-1}U $

$A= \begin{bmatrix} 1 &0 &0 \\ 1 &1 &0 \\ 0 &0 &1 \end{bmatrix} \begin{bmatrix} 1 &0 &0 \\ 0 &1 &0 \\ 2 &0 &1 \end{bmatrix} \begin{bmatrix} 1 &0 &0 \\ 0 &1 &0 \\ 0 &\frac{-1}{2} &1 \end{bmatrix} U$

$A=  \begin{bmatrix} 1 &0 &0 \\ 1 &1 &0 \\ 2 &\frac{-1}{2} &1 \end{bmatrix} U$

Hence, $L=\begin{bmatrix} 1 &0 &0 \\ 1 &1 &0 \\ 2 &\frac{-1}{2} &1 \end{bmatrix}$ and $U= \begin{bmatrix} 1 &1 &-2 \\ 0 &2 &1 \\ 0 &0 &\frac{-1}{2} \end{bmatrix}$

Now, to find $x_1,x_2,x_3,$ we can write:

$AX=B \implies LUX = B$

let $UX=Y, $ So, $LY=B$

we can write $LY=B$ in matrix notation as: $\begin{bmatrix} 1 &0 &0 \\ 1 &1 &0 \\ 2 &\frac{-1}{2} &1 \end{bmatrix}$$\begin{bmatrix} y_1\\y_2 \\ y_3 \end{bmatrix} = \begin{bmatrix} 4\\7 \\ 7 \end{bmatrix}$

So, $y_1=4,y_1+y_2=7 \implies y_2=3, 8 – \frac{3}{2} + y_3 = 7 \implies y_3=\frac{1}{2}$

So, $y_1=4, y_2=3,y_3=\frac{1}{2}$

Now, on solving $UX=Y$ i.e. $\begin{bmatrix} 1 &1 &-2 \\ 0 &2 &1 \\ 0 &0 &\frac{-1}{2} \end{bmatrix} \begin{bmatrix} x_1\\x_2 \\ x_3 \end{bmatrix} = \begin{bmatrix} 4\\3 \\ \frac{1}{2} \end{bmatrix}  $

It means $\frac{-x_3}{2}=\frac{1}{2} \implies x_3=-1, 2x_2-1=3 \implies x_2 =2, x_1+x_2-2x_3 = 4 \implies x_1+2+2=4\implies x_1=0$

Hence, $x_1=0,x_2=2,x_3=-1$

Edit:

$LU$ decomposition is not necessarily unique if it exists.

Here, you can make infinitely many $A=LU$ decomposition as:

$A = \begin{pmatrix}
x & 0 & 0 \\
x & y & 0 \\
2x & \frac{-y}{2} & z
\end{pmatrix}  \begin{pmatrix}
\frac{1}{x} & \frac{1}{x} & \frac{-2}{x} \\
0 & \frac{2}{y} & \frac{1}{y} \\
0 & 0 & \frac{-1}{2z}
\end{pmatrix}$

where $x,y,z \in \mathbb{R}$ for which $\det(L)$ and $\det(U)$ are non-zero because $\det(A)\neq 0.$

Now you can take $x=1,y=2,z=3$ or $x=3,y=-1,z=5$ etc, you get the same coefficient matrix.

The reason is that you can make LU decomposition unique by imposing the constraints on either the diagonal entries of $L$ or $U$.

You can make the above $LU$ decomposition by assuming $L_{11}=x,L_{22}=y,L_{33}=z$ and rest of the entries of $L$ and $U$ will automatically be obtained when you solve by solving equations after writing $A=LU.$

Another way is to assume $U_{11}=x,U_{22}=y,U_{33}=z$ and you get a different $LU$ decomposition.

12 votes
12 votes

Option D is the Answer.

 

7 votes
7 votes

Answer D.

Check this online website to calculate LU decomposition.

In this answer, I want to show idea behind LU decomposition. This answer contains crux of LA, please spend some time in reading.

Lets see how to multiply two matrices using some not so well known method at graduate level.

There are usually 3 ways to multiply matrices. 

  1. Row View 
  2. Column View
  3. Usual way – Row x Column = element

To Understand LU decomposition, we need to understand “Row View”. Lets understand it clearly.

(I have already explained column view in one more question of this year – here)

Suppose you want to multiply 2 matrices then you can use following approach (view) to do so.


Chart, bar chartDescription automatically generated

Take first Row of A and Multiply with every other row of B to get first row of C.

A screenshot of a computerDescription automatically generated with low confidence

Similarly take 2nd row of A and multiply with every other row of B to get second row of C.
A picture containing iconDescription automatically generated

And So on…

Lets just Verify this by taking simple example of $2x2$ matrix.

$ \begin{bmatrix}
1 & 0 \\ 2 &1
\end{bmatrix}
\begin{bmatrix}
3 & 0 \\ 0 &1
\end{bmatrix} = \color{red}{?}

 

$\begin{array} {rrr}
& 1 \times & \begin{bmatrix}
3 & 0
\end{bmatrix} \\
\text{First row of C} =  & + & &=\begin{bmatrix}
3 & 0
\end{bmatrix}\\
& 0 \times & \begin{bmatrix}
0 & 1
\end{bmatrix} \\
 \end{array}$

$\begin{array} {rrr}
& 2 \times & \begin{bmatrix}
3 & 0
\end{bmatrix} \\
\text{Secondd row of C} =  &+ & &=\begin{bmatrix}
6 & 1
\end{bmatrix}\\
& 1 \times & \begin{bmatrix}
0 & 1
\end{bmatrix} \\
 \end{array}$
Hence 

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

 

We will use this amazing idea in LU decomposition. We will always have $L_i$ and $U_i$ such that $L_i U_i = A$.

To start with, we will take $L_0$ as identity and $U_0$ as $A$.

Now we will convert $U_0$ to upper tringular matrix with row operations that can be depicted by $L_i$

For calculation – refer here

edited by
Answer:

Related questions