**Lu factorization is also known as the triangular decomposition method**. It is often called **Crout’s method** also. This method is based on the fact that **every square matrix can be expressed as the product of a lower and an upper triangular matrix provided the principal minors of the given square matrix **$\mathbf{A}\mathbf{}\mathbf{=}\mathbf{}\mathbf{\left(}{\mathbf{a}}_{\mathbf{ij}}\mathbf{\right)}\mathbf{}\mathbf{m}\mathbf{}\mathbf{x}\mathbf{}\mathbf{n}$** are non-singular** i.e.

Then we can also assure that the factorization is unique.

__DERIVATION__

Let us assume that the matrix A is factorized as the product of a lower triangular matrix L and upper triangular matrix U so that A = LU

Where,

Here the system of equation AX = b can be written as LUX = b

Putting UX = Y

Now LU = A will give us

From the above equation, we get,

**Generalizing the above equation we get,**

**For j > 1,**

**And for i > 1 but i < j,**

All ${\mathrm{l}}_{\mathrm{ij}}$ , ${\mathrm{u}}_{\mathrm{ij}}$ can be determined by applying the above relations, and hence L and U will be known.

Now ${\mathrm{y}}_{1},{\mathrm{y}}_{2},....,{\mathrm{y}}_{\mathrm{n}}$can be determined by forwarding substitution from LY = b and all unknown ${\mathrm{x}}_{1},{\mathrm{x}}_{2},....,{\mathrm{x}}_{\mathrm{n}}$ will be found by back substitution from the equation UX = Y

Alternatively, we can find ${\mathrm{L}}^{-1}$ and ${\mathrm{U}}^{-1}$ and we can write $\mathrm{Y}={\mathrm{L}}^{-1}\mathrm{b}$, $\mathrm{X}={\mathrm{U}}^{-1}\mathrm{Y}$. The inverse of A can be determined from the following relation:

We now discuss the particular case of 3 × 3 matrices of the form.

We get,

__INPUT:__

A matrix

__OUTPUT:__

The value after factorization.

__PROCESS:__

```
Step1: [taking the inputs]
Read n [the order of the matrix]
for i = 0 to n - 1 repeat
for j = 0 to n - 1 repeat
Read arr[i][j]
[End of ‘for’ loop]
[End of ‘for’ loop]
[reading the constant terms]
for i = 0 to n - 1 repeat
Read constant[i]
[End of ‘for’ loop]
Step 2: [LU Factorization]
for j = 0 to n - 1 repeat
for i = 0 to n - 1 repeat
If i ≤ j then
Set u[i][j] ← arr[i][j]
for k = 0 to i - 2 repeat
Set u[i][j] ← u[i][j] - l[i][k] × u[k][j]
[End of ‘for’ loop]
If i = j then
Set l[i][j] ← 1.0
else
Set l[i][j] ← 0.0
[End of ‘if’]
[End of ‘if’]
else
Set l[i][j] ← arr[i][j]
for k = 0 to j - 1 repeat
Set l[i][j] = l[i][j] - l[i][k] × u[k][j]
[End of ‘for’ loop]
Set l[i][j] = l[i][j] / u[j][j]
Set u[i][j] ← 0.0
[End of ‘if’]
[End of ‘for’ loop]
[End of ‘for’ loop]
Print "the values of matrix L"
for i = 0 to n - 1 repeat
for j = 0 to n - 1 repeat
Print l[i][j]
[End of ‘for’ loop]
Move to the next line
[End of ‘for’ loop]
Print "the values of matrix U:"
for i = 0 to n - 1 repeat
for j = 0 to n - 1 repeat
Print u[i][j]
[End of ‘for’ loop]
Move to the next line
[End of ‘for’ loop]
for i = 0 to n - 1 repeat
Set y[i] ← constant[i]
for j = 0 to i - 1 repeat
Set y[i] ← y[i] - l[i][j] × y[j]
[End of ‘for’ loop]
[end of ‘for’ loop]
Print "the value of matrix Y"
for i = 0 to n - 1 repeat
Print y[i]
[End of ‘for’ loop]
for i = n - 1 to 0 repeat
Set x[i] ← y[i]
for j = i + 1 to n - 1 repeat
Set x[i] ← x[i] - u[i][j] × x[j]
[End of ‘for’ loop]
Set x[i] ← x[i]/u[i][i]
[End of ‘for’ loop]
Print "the value of matrix X: "
for i = 0 to n - 1 repeat
Print x[i]
[End of ‘for’ loop]
[End of ‘LU Factorization’ method]
```

__ADVANTAGES__

**1.** It is done only using the matrix A, so after the factorization, it can be applied to any vector b.

**2.** It is better than the Gauss elimination and Gauss Jordan elimination method.

__DISADVANTAGES__

**1.** It requires forward and backward substitution.

**2.** It requires extra memory space to store the LU factors.

__APPLICATIONS__

**1.** It is used to solve the linear system Ax=b where a is a matrix.

**2.** It is used to find the determinant and inverse of a matrix.

Contributed by