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$

Answer 1

$\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 \rightarrow(1)$

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

$2x_1 + x_2 -5x_3  = 7 \rightarrow(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$

Answer 2

Option D is the Answer.

 

Comments

Must be the best answer! It's very detailed one too!

---

Thanks

---

Shortcut to get LU Decomposition (Method 1)

By just only 3 row operations, you can get complete L and U matrices. No need to multiply matrices and solve equations.

---

This statement that “Every square matrix can be decomposed as A=LU where L is a lower triangular matrix and U is upper triangular matrix “ is WRONG 

---

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?

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