GATE CSE 2022 | Question: 35

Question

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

• A. $\textit{L}_{32}=2, \textit{U}_{33}= – \frac{1}{2}, x_{1}= – 1$
• B. $\textit{L}_{32}=2, \textit{U}_{33}=2, x_{1}= – 1$
• C. $\textit{L}_{32}= – \frac{1}{2}, \textit{U}_{33}=2, x_{1}= 0$
• D. $\textit{L}_{32}= – \frac{1}{2}, \textit{U}_{33}= – \frac{1}{2}, x_{1}= 0$

Comments

Approach the question wisely:

From given system of equation write the augmented form: $[Ax\;|\;b]$ then do row operations you will get a upper triangular matrix.
Get the value of $x_1$ and then follow that upper triangular matrix to get $U_{33}$

Answer 1

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.

Comments

Beautiful explanation bro!!

---

Method 1 This shortcut is really amazing 👏

---

@ankitgupta.1729 will the method 1 work in any type of LU decomposition or did it work only in this particular scenario?

---

@Sanidhya Dakhera 

Please check the edit at the end of the answer.

There can be infinitely many LU decomposition for a matrix and it is not necessary that all the diagonal entries of L and U should be 1.

Method 1 can give you only one LU decomposition but based on the question you can change it into another LU decomposition.

For example, in some LU decomposition, if you have all the diagonal entries of matrix L as 1 i.e. x=y=z=1 and if you want another LU decomposition for which diagonal entries of matrix L are 2,3 and 4 then you have to multiply the first, second and third column of previous L by 2,3 and 4 respectively and divide the first, second and third row of previous U by 2,3 and 4 respectively.

Answer 2

Option D is the Answer.

 

Comments

Don't know why the above comment is downvoted here but it is true that not every matrix can be decomposes as $A=LU$. For example, you can't find the $A=LU$ decomposition for the matrix $\begin{pmatrix}
0 & 1 \\
2 & 3
\end{pmatrix}$ or $\begin{pmatrix}
0 & 1 & 1\\
1 & 0 & 1\\ 1 & 1 & 1
\end{pmatrix}.$

On a side note, Cramer's rule is not useful for computation because it requires evaluating $(n+1)$ determinants of $n \times n$ matrices to solve a system of $n$ linear equations in $n$ unknowns. The amount of computation to do this is far greater than that required to solve the system of equations using Gaussian elimination method.

---

can u pls explain what is X1 matrix here?

---

@M_Kumar $x1$ is the value we need to find. It’s given in the question.

Answer 3

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.

​

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

​

Similarly take 2nd row of A and multiply with every other row of B to get second row of C.
​

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

Answer 4

Ans :- D

Follow this YouTube link for better understanding :-

The LU decomposition shortcut “https://www.youtube.com/watch?v=UlWcofkUDDU”

its the same short trick that @ankitgupta explained in this solution