GATE CSE 2015 Set 1 | Question: 1‏8

Question

In the LU decomposition of the matrix $\begin{bmatrix}2 & 2 \\ 4 & 9\end{bmatrix}$, if the diagonal elements of $U$ are both $1$, then the lower diagonal entry $l_{22}$ of $L$ is_________________.

Comments

The Crout matrix decomposition algorithm differs slightly from the Doolittle method. Doolittle's method returns a unit lower triangular matrix and an upper triangular matrix, while the Crout method returns a lower triangular matrix and a unit upper triangular matrix.

Answer 1

Already, nice answers are given – mostly using $A=LDU$ decomposition.

But I guess we can directly decompose $A=LU$ such that diagonal elements $U$ are $1$.

Given : A = $\begin{bmatrix} 2 &2 \\ 4 &9 \end{bmatrix}$

On applying $R_1 \leftarrow R_1 \div 2$

$\begin{bmatrix} 1 &1 \\ 4 &9 \end{bmatrix} = \begin{bmatrix} \frac{1}{2} &0 \\ 0 &1 \end{bmatrix} \begin{bmatrix} 2 &2 \\ 4 &9 \end{bmatrix}$

So, here elimination matrix $E_{11}$ is $\begin{bmatrix} \frac{1}{2} &0 \\ 0 &1 \end{bmatrix}$

$E_{11}A = \begin{bmatrix} 1 &1 \\ 4 &9 \end{bmatrix}$

On applying $R_2 \leftarrow R_2 - 4R_1$

$\begin{bmatrix} 1 &1 \\ 0 &5 \end{bmatrix} = \begin{bmatrix} 1 &0 \\ -4 &1 \end{bmatrix} \begin{bmatrix} 1 &1 \\ 4 &9 \end{bmatrix}$

So, here elimination matrix $E_{21}$ is $\begin{bmatrix} 1 &0 \\ -4 &1 \end{bmatrix}$

$E_{21}E_{11}A = \begin{bmatrix} 1 &1 \\ 0 &5 \end{bmatrix}$

On applying $R_2 \leftarrow R_2 \div 5$

$\begin{bmatrix} 1 &1 \\ 0 &1 \end{bmatrix} = \begin{bmatrix} 1 &0 \\ 0 &\frac{1}{5} \end{bmatrix} \begin{bmatrix} 1 &1 \\ 0 &5 \end{bmatrix}$

So, here elimination matrix $E_{22}$ is $\begin{bmatrix} 1 &0 \\ 0 &\frac{1}{5} \end{bmatrix}$

$\therefore E_{22}E_{21}E_{11}A = \begin{bmatrix} 1 &1 \\ 0 &1 \end{bmatrix} = U$

$\therefore A = \left( E_{11}^{-1}E_{21}^{-1}E_{22}^{-1} \right)U$

$\therefore A = \left( \begin{bmatrix} \frac{1}{2} &0 \\ 0 &1 \end{bmatrix}^{-1}\begin{bmatrix} 1 &0 \\ -4 &1 \end{bmatrix}^{-1}\begin{bmatrix} 1 &0 \\ 0 &\frac{1}{5} \end{bmatrix}^{-1} \right)U$

$\therefore A = \left( \begin{bmatrix} 2 &0 \\ 0 &1 \end{bmatrix} \begin{bmatrix} 1 &0 \\ 4 &1 \end{bmatrix} \begin{bmatrix} 1 &0 \\ 0 &5 \end{bmatrix} \right)U$

$\therefore A = \begin{bmatrix} 2 &0 \\ 4 &5 \end{bmatrix} U = LU$

---

The elimination matrices that we got are of the form – 

$E_{11} = \begin{bmatrix} \frac{1}{d_1} &0 \\ 0 &1 \end{bmatrix}, E_{21} = \begin{bmatrix} 1 &0 \\ -l_{21} &1 \end{bmatrix} \text{ and } E_{22} = \begin{bmatrix} 1 &0 \\ 0 &\frac{1}{d_2} \end{bmatrix}$

$E_{11}^{-1} = \begin{bmatrix} d_1 &0 \\ 0 &1 \end{bmatrix}, E_{21}^{-1} = \begin{bmatrix} 1 &0 \\ l_{21} &1 \end{bmatrix} \text{ and } E_{22}^{-1} = \begin{bmatrix} 1 &0 \\ 0 &d_2 \end{bmatrix}$

$L = E_{11}^{-1}E_{21}^{-1}E_{22}^{-1} = \begin{bmatrix} d_1 &0 \\ 0 &1 \end{bmatrix} \begin{bmatrix} 1 &0 \\ l_{21} &1 \end{bmatrix} \begin{bmatrix} 1 &0 \\ 0 &d{2} \end{bmatrix} = \begin{bmatrix} d_1 &0 \\ l_{21} &d_2 \end{bmatrix}$

From here we can conclude, we can directly fill elements of $L$ based on what row operation we performed.