GATE1988-16i

Question

Assume that the matrix $A$ given below, has factorization of the form $LU=PA$, where $L$ is lower-triangular with all diagonal elements equal to 1, $U$ is upper-triangular, and $P$ is a permutation matrix. For

$A = \begin{bmatrix} 2 & 5 & 9 \\ 4 & 6 & 5 \\ 8 & 2 & 3 \end{bmatrix}$

Compute $L, U,$ and $P$ using Gaussian elimination with partial pivoting.

Answer 1

$A = \begin{bmatrix} 2 &5 &9 \\ 4 &6 &5 \\ 8&2 &3 \end{bmatrix}$

-- Using Gaussian Elimination, we will change $A$ into upper triangular matrix $U$ and simultaneously find out elementary matrices $E_{21}$, $E_{31}$ and $E_{32}$.

-- To get the elementary matrices, we have to do the same operation on the Identity matrix as we do on the original matrix $A.$

On applying $R_2 \leftarrow R_{2} - 2R_1$

$A$ becomes $\begin{bmatrix} 2 &5 &9 \\ 0 &-4 &-13 \\ 8 &2 &3 \end{bmatrix}$

and $E_{21}$ becomes $\begin{bmatrix} 1 &0 &0 \\ -2 &1 &0 \\ 0 &0 &1 \end{bmatrix}$ $[ \because R_2 \leftarrow R_{2} - 2R_1 $ on identity matrix $I$ will give $E_{21}]$

We can write it as $\begin{bmatrix} 2 &5 &9 \\ 0 &-4 &-13 \\ 8 &2 &3 \end{bmatrix}=$ $\begin{bmatrix} 1 &0 &0 \\ -2 &1 &0 \\ 0 &0 &1 \end{bmatrix}$* $\begin{bmatrix} 2 &5 &9 \\ 4 &6 &5 \\ 8&2 &3 \end{bmatrix} $

Now, applying $R_3 \leftarrow R_{3} - 4R_1$

$A$ becomes $\begin{bmatrix} 2 &5 &9 \\ 0 &-4 &-13 \\ 0 &-18 &-33 \end{bmatrix}$

and $E_{31}$ becomes $\begin{bmatrix} 1 &0 &0 \\ 0 &1 &0 \\ -4 &0 &1 \end{bmatrix}$ $[ \because R_3 \leftarrow R_{3} - 4R_1 $ on identity matrix $I$ will give $E_{31}]$

Now, applying $R_3 \leftarrow R_{3} - \frac{18}{4}R_2$

$A$ becomes $\begin{bmatrix} 2 &5 &9 \\ 0 &-4 &-13 \\ 0 &0 &\frac{51}{2} \end{bmatrix}$

and $E_{32}$ becomes $\begin{bmatrix} 1 &0 &0 \\ 0 &1 &0 \\ 0&\frac{-18}{4} &1 \end{bmatrix}$ $[ \because R_3 \leftarrow R_{3} - \frac{18}{4}R_2$ on identity matrix $I$ will give $E_{32}]$

So, here,

$U= \begin{bmatrix} 2 &5 &9 \\ 0 &-4 &-13 \\ 0 &0 &\frac{51}{2} \end{bmatrix},\;\; E_{21} =\begin{bmatrix} 1 &0 &0 \\ -2 &1 &0 \\ 0 &0 &1 \end{bmatrix},\;\; E_{31} =\begin{bmatrix} 1 &0 &0 \\ 0 &1 &0 \\ -4 &0 &1 \end{bmatrix},\;\; $$E_{32} =\begin{bmatrix} 1 &0 &0 \\ 0 &1 &0 \\ 0 &\frac{-18}{4} &1 \end{bmatrix},\;\;$

Now, we can write all these things as :-

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

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

Here, $E_{21}^{-1},\;E_{31}^{-1},\; E_{32}^{-1}$ are very simple to compute. Just do the reverse operation means in row operations where we have done subtraction , we have to do addition.

So, $\Rightarrow A = E_{21}^{-1}E_{31}^{-1}E_{32}^{-1} U$ becomes

$A= \begin{bmatrix} 1 &0 &0 \\ 2 &1 &0 \\ 0 &0 &1 \end{bmatrix}*\begin{bmatrix} 1 &0 &0 \\ 0 &1 &0 \\ 4 &0 &1 \end{bmatrix}*\begin{bmatrix} 1 &0 &0 \\ 0 &1 &0 \\ 0 &\frac{18}{4} &1 \end{bmatrix}*\begin{bmatrix} 2 &5 &9 \\ 0 &-4 &-13 \\ 0 &0 &\frac{51}{2} \end{bmatrix}$

$\Rightarrow A= \begin{bmatrix} 1 &0 &0 \\ 2 &1 &0 \\ 4 &\frac{18}{4} &1 \end{bmatrix}*\begin{bmatrix} 2 &5 &9 \\ 0 &-4 &-13 \\ 0 &0 &\frac{51}{2} \end{bmatrix}$

It is the LU decomposition where $L= \begin{bmatrix} 1 &0 &0 \\ 2 &1 &0 \\ 4 &\frac{18}{4} &1 \end{bmatrix}\;\;and\; U=\begin{bmatrix} 2 &5 &9 \\ 0 &-4 &-13 \\ 0 &0 &\frac{51}{2} \end{bmatrix}$

Since, we have not done any row exchange, So, permutation matrix will not be changed. It will remain identity matrix $I.$

So, Answer is :-

$L= \begin{bmatrix} 1 &0 &0 \\ 2 &1 &0 \\ 4 &\frac{18}{4} &1 \end{bmatrix}\;\; U=\begin{bmatrix} 2 &5 &9 \\ 0 &-4 &-13 \\ 0 &0 &\frac{51}{2} \end{bmatrix}$ and $P= \begin{bmatrix} 1 &0 &0 \\ 0 &1 &0 \\ 0 &0 &1 \end{bmatrix}$

Comments

How are we obtaining elementary matrices ?

---

@Satbir

edited.

Answer 2

Here $LU=PA\rightarrow(1)$

Where $L=\begin{bmatrix} l_{11}&0 &0 \\ l_{21}&l_{22} &0 \\ l_{31}&l_{32} &l_{33} \end{bmatrix}$

Given that $l_{11}=l_{22}=l_{33}=1$

$L=\begin{bmatrix} 1&0 &0 \\ l_{21}&1 &0 \\ l_{31}&l_{32} &1 \end{bmatrix}$

$U=\begin{bmatrix} u_{11}&u_{12} &u_{13} \\ 0&u_{22} &u_{23} \\ 0&0 &u_{33} \end{bmatrix}$

$P=\begin{bmatrix} 1&0 &0\\ 0&1 &0 \\ 0&0 &1 \end{bmatrix}$

$A = \begin{bmatrix} 2 & 5 & 9 \\ 4 & 6 & 5 \\ 8 & 2 & 3 \end{bmatrix}$

Put the values in equation $(1),$ we get

$\begin{bmatrix} 1&0 &0 \\ l_{21}&1 &0 \\ l_{31}&l_{32} &1 \end{bmatrix}\cdot \begin{bmatrix} u_{11}&u_{12} &u_{13} \\ 0&u_{22} &u_{23} \\ 0&0 &u_{33} \end{bmatrix}=\begin{bmatrix} 1&0 &0\\ 0&1 &0 \\ 0&0 &1 \end{bmatrix}\cdot \begin{bmatrix} 2 & 5 & 9 \\ 4 & 6 & 5 \\ 8 & 2 & 3 \end{bmatrix} $

$\begin{bmatrix} u_{11}&u_{12} &u_{13} \\ l_{21}u_{11}&l_{21}u_{12}+u_{22} &l_{21}u_{13}+u_{23} \\l_{31}u_{11} &l_{31}u_{12}+l_{32}u_{22} &l_{31}u_{13}+l_{32}u_{23}+u_{33} \end{bmatrix}  =\begin{bmatrix} 2 & 5 & 9 \\ 4 & 6 & 5 \\ 8 & 2 & 3 \end{bmatrix}$

Compare each element of both side and we get,

$u_{11}= 2,u_{12}= 5,u_{13}= 9$

$l_{21}u_{11}= 4\implies l_{21}=2$

$l_{21}u_{12}+u_{22} = 6\implies u_{22}=-4$ 

$l_{21}u_{13}+u_{23}= 5\implies u_{23}=-13$

$l_{31}u_{11} = 8\implies l_{31}=4$

$l_{31}u_{12}+l_{32}u_{22} = 2\implies l_{32}=4.5$

$l_{31}u_{13}+l_{32}u_{23}+u_{33} = 3\implies u_{33}=25.5$

So, $L=\begin{bmatrix} 1&0 &0 \\ 2&1 &0 \\ 4&4.5 &1 \end{bmatrix}$

$U=\begin{bmatrix} 2&5 &9 \\ 0&-4&-13 \\ 0&0 &25.5 \end{bmatrix}$

$P=\begin{bmatrix} 1& 0&0 \\0 &1 &0 \\ 0&0 &1\end{bmatrix}$

Reference$:$ http://mathworld.wolfram.com/PermutationMatrix.html