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

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.

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.

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

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