How can we use the $PA=LU$ decomposition to solve a system of linear equations?

[Chris L T521]

Thanks to those who participated in last week's POTW! Here's this week's problem!

-----

Problem: Given the matrix $A=\begin{pmatrix}2 & 1 & 5\\ 4 & 4 & -4\\ 1 & 3 & 1\end{pmatrix}$,

(a) Find it's $PA=LU$ decomposition where $P$ is a permutation matrix, $L$ is a lower triangular matrix, and $U$ is an upper triangular matrix.
(b) Use its $PA=LU$ decomposition to solve $\begin{pmatrix}2 & 1 & 5\\ 4 & 4 & -4\\ 1 & 3 & 1\end{pmatrix} \begin{pmatrix} x_1 \\ x_2 \\ x_3 \end{pmatrix} = \begin{pmatrix} 5 \\ 0 \\ 6 \end{pmatrix}$

Hint for (b):

Spoiler

Solve the matrix equations $Lc=Pb$ and $Ux=c$ and then use back substitution.

-----

 

[Chris L T521]

Sorry about posting the solution late - I was studying for my analysis prelim this past week and did some more cramming last night, and in the process I forgot about updating the POTWs for this week. The exam was this morning and was much better than what I was expecting - I'll know how well I did in the next couple weeks.

Anyways, this week's problem was correctly answered by Sudharaka. His solution can be found below.

Spoiler

The LUP decomposition is not unique. One possible answer is,

\[\begin{pmatrix}0& 1& 0\\0& 0& 1\\1& 0& 0\end{pmatrix}\begin{pmatrix}2 & 1 & 5\\ 4 & 4 & -4\\ 1 & 3 & 1\end{pmatrix}=\begin{pmatrix}1&0&0\\ 0.25& 1& 0\\ 0.5& -0.5& 1\end{pmatrix}\begin{pmatrix} 4& 4& -4\\ 0& 2& 2\\ 0& 0& 8\end{pmatrix}\]\[\Rightarrow\begin{pmatrix}2 & 1 & 5\\ 4 & 4 & -4\\ 1 & 3 & 1\end{pmatrix}=\begin{pmatrix}0& 1& 0\\0& 0& 1\\1& 0& 0\end{pmatrix}^{-1}\begin{pmatrix}1&0&0\\ 0.25& 1& 0\\ 0.5& -0.5& 1\end{pmatrix}\begin{pmatrix} 4& 4& -4\\ 0& 2& 2\\ 0& 0& 8\end{pmatrix}\]Therefore,\[\begin{pmatrix}0& 1& 0\\0& 0& 1\\1& 0& 0\end{pmatrix}^{-1}\begin{pmatrix} a_1 \\ a_2 \\ a_3 \end{pmatrix} = \begin{pmatrix} 5 \\ 0 \\ 6 \end{pmatrix}\]\[\Rightarrow \begin{pmatrix} a_1 \\ a_2 \\ a_3 \end{pmatrix} = \begin{pmatrix}0& 1& 0\\0& 0& 1\\1& 0& 0\end{pmatrix} \begin{pmatrix} 5 \\ 0 \\ 6 \end{pmatrix}= \begin{pmatrix} 0 \\ 6 \\ 5 \end{pmatrix}\]Now, \[\begin{pmatrix}1&0&0\\ 0.25& 1& 0\\ 0.5& -0.5& 1\end{pmatrix}\begin{pmatrix} b_1\\b_2\\b_3\end{pmatrix}=\begin{pmatrix} 0 \\ 6 \\ 5 \end{pmatrix}\]\[\Rightarrow \begin{pmatrix} b_1\\b_2\\b_3\end{pmatrix}=\begin{pmatrix} 0\\6\\8\end{pmatrix}\]Again we have,\[\begin{pmatrix} 4& 4& -4\\ 0& 2& 2\\ 0& 0& 8\end{pmatrix}\begin{pmatrix} x_1\\x_2\\x_3\end{pmatrix}=\begin{pmatrix} 0 \\ 6 \\ 8 \end{pmatrix}\]\[\Rightarrow \begin{pmatrix} x_1\\x_2\\x_3\end{pmatrix}= \begin{pmatrix} -1\\2\\1\end{pmatrix}\]