Jamal's question via email about solving a system with a PLU decomposition.

[Prove It]

Consider the linear system $\displaystyle \begin{align*} A\,\mathbf{x} = \mathbf{b} \end{align*}$. The coefficient matrix A has the following PLU decomposition:

$\displaystyle \begin{align*} A = \left[ \begin{matrix} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 0 & 0 \end{matrix} \right] \left[ \begin{matrix} \phantom{-}1 & \phantom{-}0 & 0 \\ -\frac{1}{3} & \phantom{-}1 & 0 \\ \phantom{-}\frac{1}{3} & -\frac{1}{4} & 1 \end{matrix} \right] \left[ \begin{matrix} -3 & \phantom{-}4 & 0 \\ \phantom{-}0 & -\frac{8}{3} & 1 \\ \phantom{-}0 & \phantom{-}0 & \frac{5}{4} \end{matrix} \right] \end{align*}$

and $\displaystyle \begin{align*} \mathbf{b} = \left[ \begin{matrix} -3 \\ -5 \\ -18 \end{matrix} \right] \end{align*}$.

Use the PLU decomposition of the coefficient matrix A to find the solution of the linear system $\displaystyle \begin{align*} A\,\mathbf{x} = \mathbf{b} \end{align*}$.

To start with, since $\displaystyle \begin{align*} A = P\,L\,U \end{align*}$, that means in our system we have $\displaystyle \begin{align*} P\,L\,U\,\mathbf{x} = \mathbf{b} \end{align*}$. Normally to solve for $\displaystyle \begin{align*} \mathbf{x} \end{align*}$ we would use inverses, so we would premultiply both sides by $\displaystyle \begin{align*} P^{-1} \end{align*}$, but luckily since $\displaystyle \begin{align*} P \end{align*}$ is orthogonal, $\displaystyle \begin{align*} P^{-1} = P^T \end{align*}$, so this gives $\displaystyle \begin{align*} L\,U\,\mathbf{x} = P^T\,\mathbf{b} \end{align*}$. Notice that

$\displaystyle \begin{align*} P^T\,\mathbf{b} &= \left[ \begin{matrix} 0 & 0 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \end{matrix} \right] \left[ \begin{matrix} -3 \\ -5 \\ -18 \end{matrix} \right] \\ &= \left[ \begin{matrix} -18 \\ -3 \\ -5 \end{matrix} \right] \end{align*}$

Now since L and U are triangular matrices, it makes solving systems easier as they can be solved directly with forward or back substitution. If we were to multiply $\displaystyle \begin{align*} U\,\mathbf{x} \end{align*}$, we would get a 3x1 column matrix, which we can call $\displaystyle \begin{align*} \mathbf{g} \end{align*}$, so the system reduces to $\displaystyle \begin{align*} L\,\mathbf{g} = P^T\,\mathbf{b} \end{align*}$ and $\displaystyle \begin{align*} U\,\mathbf{x} = \mathbf{g} \end{align*}$. Solving for $\displaystyle \begin{align*} \mathbf{g} \end{align*}$...

$\displaystyle \begin{align*} \left[ \begin{matrix} \phantom{-}1 & \phantom{-}0 & 0 \\ -\frac{1}{3} & \phantom{-}1 & 0 \\ \phantom{-}\frac{1}{3} & -\frac{1}{4} & 1 \end{matrix} \right] \left[ \begin{matrix} g_1 \\ g_2 \\ g_3 \end{matrix} \right] &= \left[ \begin{matrix} -18 \\ -3 \\ -5 \end{matrix} \right] \end{align*}$

So we can see:

$\displaystyle \begin{align*} g_1 &= -18 \\ \\ -\frac{1}{3}\,g_1 + g_2 &= -3 \\ 6 + g_2 &= -3 \\ g_2 &= -9 \\ \\ \frac{1}{3}\,g_1 - \frac{1}{4}\,g_2 + g_3 &= -5 \\ -6 + \frac{9}{4} + g_3 &= -5 \\ -\frac{15}{4} + g_3 &= -\frac{20}{4} \\ g_3 &= -\frac{5}{4} \end{align*}$

and now using this to solve for $\displaystyle \begin{align*} \mathbf{x} \end{align*}$ in $\displaystyle \begin{align*} U\,\mathbf{x} = \mathbf{g} \end{align*}$ gives

$\displaystyle \begin{align*} \left[ \begin{matrix} -3 & \phantom{-}4 & 0 \\ \phantom{-}0 & -\frac{8}{3} & 1 \\ \phantom{-}0 & \phantom{-}0 & \frac{5}{4} \end{matrix} \right] \left[ \begin{matrix} x_1 \\ x_2 \\ x_3 \end{matrix} \right] &= \left[ \begin{matrix} -18 \\ -9 \\ -\frac{5}{4} \end{matrix} \right] \end{align*}$

So we can see:

$\displaystyle \begin{align*} \frac{5}{4}\,x_3 &= -\frac{5}{4} \\ x_3 &= -1 \\ \\ -\frac{8}{3}\,x_2 + x_3 &= -9 \\ -\frac{8}{3}\,x_2 - 1 &= -9 \\ -\frac{8}{3}\,x_2 &= -8 \\ x_2 &= 3 \\ \\ -3\,x_1 + 4\,x_2 &= -18 \\ -3\,x_1 + 12 &= -18 \\ -3\,x_1 &= -30 \\ x_1 &= 10 \end{align*}$

Thus the solution to the system is $\displaystyle \begin{align*} \mathbf{x} = \left[ \begin{matrix} \phantom{-}10 \\ \phantom{-}3 \\ -1 \end{matrix} \right] \end{align*}$.