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

linear algebralu decompositionmatricessystems of equations

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.

Best Answer

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} $$

Related Question