Solving System of Linear Equations with LU Decomposition of $4 \times 3$ matrix

Question

The following is all confirmed to be true:

Matrix A = $ \begin{bmatrix} 0 & 1 & -2 \\ -1 & 2 & -1 \\ 2 & -4 & 3 \\ 1 & -3 & 2 \\ \end{bmatrix} $

U = $ \begin{bmatrix} -1 & 2 & -1 \\ 0 & 1 & -2 \\ 0 & 0 & 1 \\ 0 & 0 & 0 \\ \end{bmatrix} $

L = $ \begin{bmatrix} 1 & 0 & 0 & 0\\ 0 & 1 & 0 & 0\\ -2 & 0 & 1 & 0\\ -1 & -1 & -1 & 0\\ \end{bmatrix} $

Okay so using that I need to solve the following system:

$ x_2 - 2x_3 = 0 \\ -x_1 + 2x_2 - x_3 = -2 \\ 2x_1 -4x_2 + 3x_3 = 5 \\ x_1 - 3x_2 + 2x_3 = 1 $

So step one is solving $Ly = b$, where $y = Ux$

So that is:

$ y_1 = 0\\ y_2 = -2\\ -2y_1 + y_3 = 5 \\ -y_1 - y_2 -y_3 = 1 \\ $

How can we find $y_3$ in the last two equations? Because,

$ -2(0) + y_3 = 5 \\ -(0) - (-2) - y_3 = 1 \\ $

So in the second to last equation $y_3 = 5$, but in the last equation $y_3 = 1$. Very confused.

Answer 1

Multiplying the first row of $L$ with the first column of $U$ gives us $-1$, which is not the $(1,1)$ entry of $A$. Hence, you have made a mistake in computation of LU decomposition.

There seems to be a missing permutation matrix being involved in your computation.

Your procedure to solve the linear system upon computing the LU decomposition is correct.

Answer 2

Problem

$$ \mathbf{A} = \left[ \begin{array}{rrr} 0 & 1 & -2 \\ -1 & 2 & -1 \\ 2 & -4 & 3 \\ 1 & -3 & 2 \\ \end{array} \right] $$

Associated Permutation Matrix

Don't start with a $0$ pivot element. Move the first row down. The permutation matrix interchanges the first two rows.

$$ \mathbf{P} = \left[ \begin{array}{cccc} 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ \end{array} \right] $$

Input

$$ \begin{align} \mathbf{P} \mathbf{A} = % P \left[ \begin{array}{cccc} 0 & \boxed{1} & 0 & 0 \\ \boxed{1} & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ \end{array} \right] % A \left[ \begin{array}{rrr} 0 & 1 & -2 \\ -1 & 2 & -1 \\ 2 & -4 & 3 \\ 1 & -3 & 2 \\ \end{array} \right] % &= % L \left[ \begin{array}{rrr} -1 & 2 & -1 \\ 0 & 1 & -2 \\ 2 & -4 & 3 \\ 1 & -3 & 2 \\ \end{array} \right] \end{align} $$

Decomposition

$$ \begin{align} \mathbf{P} \mathbf{A} &= \mathbf{L} \mathbf{U} \\ % PA \underbrace{\left[ \begin{array}{rrr} -1 & 2 & -1 \\ 0 & 1 & -2 \\ 2 & -4 & 3 \\ 1 & -3 & 2 \\ \end{array} \right]}_{\color{blue}{m}\times \color{red}{n}} % &= % L \underbrace{\left[ \begin{array}{rrrc} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ -2 & 0 & 1 & 0 \\ -1 & -1 & -1 & 1 \\ \end{array} \right]}_{\color{blue}{m}\times \color{blue}{m}} % U \underbrace{\left[ \begin{array}{rrr} -1 & 2 & -1 \\ 0 & 1 & -2 \\ 0 & 0 & 1 \\ 0 & 0 & 0 \\ \end{array} \right]}_{\color{blue}{m}\times \color{red}{n}} \end{align} $$

Answer 3

$$ \begin{align} \mathbf{P} \mathbf{A} &= \mathbf{L} \mathbf{U} \\ % P \left[ \begin{array}{cccc} 0 & \boxed{1} & 0 & 0 \\ \boxed{1} & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ \end{array} \right] % A \left[ \begin{array}{rrr} 0 & 1 & -2 \\ -1 & 2 & -1 \\ 2 & -4 & 3 \\ 1 & -3 & 2 \\ \end{array} \right] % &= % L \left[ \begin{array}{rrr} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ -2 & 0 & 1 & 0 \\ -1 & -1 & -1 & 1 \\ \end{array} \right] % U \left[ \begin{array}{rrr} -1 & 2 & -1 \\ 0 & 1 & -2 \\ 0 & 0 & 1 \\ 0 & 0 & 0 \\ \end{array} \right] \end{align} $$