recategorized by
3,280 views
8 votes
8 votes
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.
recategorized by

3 Answers

Best answer
7 votes
7 votes
$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}\;\;\text{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, the 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}$
edited by
16 votes
16 votes

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

edited by
3 votes
3 votes

$\textbf{Gauss Elimination with Partial Pivoting}$


To solve the system of linear equations, we can use Gauss Elimination method, Gauss Jordan Method (specially used to find the inverse of a matrix) or LU Decomposition method but the Gauss Elimination method is most popular because compared to the other methods because it has the lowest amount of computational effort.


The method which we used here is called the $\textbf{Naive Gauss Elimination}$ method (I would request you to see that method first if you don't have any idea about that method and then come to this question).

Diagonal element on the $i^{th}$ row is called 'pivot' element. Why we call it as pivot because for doing any of the row operations at the $i^{th}$ step, most important element is the diagonal element.

In partial pivoting, we interchange rows so that diagonal/pivot elements will not be zero. During this row exchanges, we make sure that in each step, we look at the entire column and the value which has the largest magnitude or we can say the largest absolute value, becomes the pivot element. There is also a full pivoting/complete pivoting where we interchange both rows and columns. Full pivoting is typically not used in Gauss elimination because the amount of overhead to interchange the columns is high compared to partial pivoting.


Now, comes to the question,


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

$\textbf{Step 1:}$


Now, in first column, maximum absolute value is $8,$ So, interchanging the first and the third row i.e. $R_1 \leftrightarrow R_3.$ So, Now, $A_1$ and $P$ becomes:


$A_1 = \begin{pmatrix}
8 & 2 & 3 \\
4 & 6 & 5 \\
2 & 5 & 9
\end{pmatrix}$ and $P = \begin{pmatrix}
0 & 0 & 1 \\
0 & 1 & 0 \\
1 & 0 & 0
\end{pmatrix}$


$\textbf{Step 2:}$


Eliminate $4$ and $2$ from the first column of $A$ and so, $R_2 \leftarrow \frac{-1}{2}R_1 + R_2$ and $R_3 \leftarrow \frac{-1}{4}R_1 + R_3$. Now, $A_2$ and $P$ becomes:


$A_2 = \begin{pmatrix}
8 & 2 & 3 \\
0 & 5 & \frac{7}{2} \\
0 & \frac{9}{2} & \frac{33}{4}
\end{pmatrix}$ and $P = \begin{pmatrix}
0 & 0 & 1 \\
0 & 1 & 0 \\
1 & 0 & 0
\end{pmatrix}$

$\textbf{Step 3:}$


Now, in second column, maximum absolute value of $5$ and $\frac{9}{2}$ is $5$ and so, we don't need any interchanges and so, we do row operation $R_3 \leftarrow \frac{-9}{10}R_2 + R_3$ to make third row and second column as zero. So,  Now, $A_3$ and $P$ becomes:


$A_3 = U = \begin{pmatrix}
8 & 2 & 3 \\
0 & 5 & \frac{7}{2} \\
0 & 0 & \frac{51}{10}
\end{pmatrix}$ and $P = \begin{pmatrix}
0 & 0 & 1 \\
0 & 1 & 0 \\
1 & 0 & 0
\end{pmatrix}$

So, now, we have converted matrix $A$ into the $A_3$ which is nothing but the upper triangular matrix and if we try to summarize what we have done till now, we write the equation as:


$E_{32}E_{31}E_{21}PA = U$


And So,


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


Here, $E_{21},E_{31},E_{32}$ are nothing but the matrices which we got by the same row operations which we did above, on the identity matrix $I.$


So,


$E_{21} = \begin{pmatrix}
1 & 0 & 0 \\
\frac{-1}{2} & 1 & 0 \\
0 & 0 & 1
\end{pmatrix},$ $E_{31} = \begin{pmatrix}
1 & 0 & 0 \\
0 & 1 & 0 \\
\frac{-1}{4} & 0 & 1
\end{pmatrix}$ and $E_{32} = \begin{pmatrix}
1 & 0 & 0 \\
0 & 1 & 0 \\
0 & \frac{-9}{10} & 1
\end{pmatrix}$ 

Now, inverses of these elementary matrices are nor difficult to find, we just have to reverse signs while doing row operations, So,

$E_{21}^{-1} = \begin{pmatrix}
1 & 0 & 0 \\
\frac{1}{2} & 1 & 0 \\
0 & 0 & 1
\end{pmatrix},$ $E_{31}^{-1} = \begin{pmatrix}
1 & 0 & 0 \\
0 & 1 & 0 \\
\frac{1}{4} & 0 & 1
\end{pmatrix}$ and $E_{32}^{-1} = \begin{pmatrix}
1 & 0 & 0 \\
0 & 1 & 0 \\
0 & \frac{9}{10} & 1
\end{pmatrix}$ 

So, $E_{21}^{-1}E_{31}^{-1}E_{32}^{-1} = \begin{pmatrix}
1 & 0 & 0 \\
\frac{1}{2} & 1 & 0 \\
\frac{1}{4} & \frac{9}{10} & 1
\end{pmatrix} = L$


Hence, 
$$PA = \begin{pmatrix}
1 & 0 & 0 \\
\frac{1}{2} & 1 & 0 \\
\frac{1}{4} & \frac{9}{10} & 1
\end{pmatrix} \begin{pmatrix}
8 & 2 & 3 \\
0 & 5 & \frac{7}{2} \\
0 & 0 & \frac{51}{10}
\end{pmatrix} $$


Therefore, matrices $P,L$ and $U$ are:


$P= \begin{pmatrix}
0 & 0 & 1 \\
0 & 1 & 0 \\
1 & 0 & 0
\end{pmatrix}, L = \begin{pmatrix}
1 & 0 & 0 \\
\frac{1}{2} & 1 & 0 \\
\frac{1}{4} & \frac{9}{10} & 1
\end{pmatrix}$ and $U = \begin{pmatrix}
8 & 2 & 3 \\
0 & 5 & \frac{7}{2} \\
0 & 0 & \frac{51}{10}
\end{pmatrix}$

Related questions

7 votes
7 votes
3 answers
2
go_editor asked Dec 20, 2016
1,210 views
Are the two digraphs shown in the above figure isomorphic? Justify your answer.
1 votes
1 votes
1 answer
3
go_editor asked Dec 20, 2016
537 views
Verify whether the following mapping is a homomorphism. If so, determine its kernel.$f(x)=x^3$, for all $x$ belonging to $G$.
1 votes
1 votes
0 answers
4
go_editor asked Dec 20, 2016
477 views
Verify whether the following mapping is a homomorphism. If so, determine its kernel.$\overline{G}=G$