LU decomposition of a matrix is the factorization of a given square matrix into two triangular matrices, one upper triangular matrix and one lower triangular matrix, such that the product of these two matrices gives the original matrix. It was introduced by Alan Turing in 1948, who also created the Turing machine.

LU Decomposition is a fundamental technique in linear algebra used to solve systems of linear equations, invert matrices, and compute determinants. It decomposes a given matrix into two triangular matrices, one lower (L) and one upper (U). This decomposition simplifies many matrix operations, making it an essential tool in various engineering applications.

Table of Content

- What is LU Decomposition?
- Gauss Elimination Method
- LU Decomposition Method
- Example of LU Decomposition

## What is LU Decomposition?

LU Decomposition expresses a given square matrix A as the product of two matrices:

- L: A lower triangular matrix with ones on the diagonal.
- U: An upper triangular matrix.

Mathematically, A can be written as

A = LU

**Gauss Elimination Method**

**Gauss Elimination Method**

Gaussian Elimination, also known as Gauss-Jordan Elimination, is a method used in linear algebra to solve systems of linear equations and to find the inverse of a matrix. It’s named after the mathematician Carl Friedrich Gauss and also the mathematician Wilhelm Jordan, who made significant contributions to its development.

According to the Gauss elimination method:

- Any zero row should be at the bottom of the matrix.
- The first non-zero entry of each row should be on the right-hand side of the first non-zero entry of the preceding row. This method reduces the matrix to row echelon form.

**LU Decomposition Method**

**LU Decomposition Method**

To factor any square matrix into two triangular matrices i.e., one is a lower triangular matrix and the other is an upper triangular matrix, we can use the following steps.

- Given a set of linear equations, first convert them into matrix form A X = C where A is the coefficient matrix, X is the variable matrix and C is the matrix of numbers on the right-hand side of the equations.
- Now, reduce the coefficient matrix A, i.e., the matrix obtained from the coefficients of variables in all the given equations such that for ‘n’ variables we have an nXn matrix, to row echelon form using Gauss Elimination Method. The matrix so obtained is U.
- To find L, we have two methods. The first one is to assume the remaining elements as some artificial variables, make equations using A = L U, and solve them to find those artificial variables. The other method is that the remaining elements are the multiplier coefficients because of which the respective positions became zero in the U matrix. (This method is a little tricky to understand by words but would get clear in the example below)
- Now, we have A (the nXn coefficient matrix), L (the nXn lower triangular matrix), U (the nXn upper triangular matrix), X (the nX1 matrix of variables), and C (the nX1 matrix of numbers on the right-hand side of the equations).
- The given system of equations is A X = C. We substitute A = L U. Thus, we have L U X = C. We put Z = U X, where Z is a matrix or artificial variables and solve for L Z = C first and then solve for U X = Z to find X or the values of the variables, which was required.

**Example of LU Decomposition**

**Example of LU Decomposition**

Solve the following system of equations using the LU Decomposition method:

[Tex]x_1 + x_2 + x_3 = 1 \\4x_1 + 3x_2 – x_3 = 6\\3x_1 + 5x_2 + 3x_3 = 4[/Tex]

Solution: Here, we have A =

[Tex]\begin{bmatrix} 1 & 1 & 1 \\ 4 & 3 & -1 \\ 3 & 5 & 3 \end{bmatrix} , X = \begin{bmatrix} x_1 \\ x_2 \\ x_3 \end{bmatrix}[/Tex]

and

[Tex]C = \begin{bmatrix} 1 \\ 6 \\ 4 \end{bmatrix}[/Tex]

such that A X = C. Now, we first consider

[Tex]\begin{bmatrix} 1 & 1 & 1 \\ 4 & 3 & -1 \\ 3 & 5 & 3 \end{bmatrix}[/Tex]

and convert it to row echelon form using Gauss Elimination Method. So, by doing

[Tex]R_2 \to R_2 – 4R_1\\R_3 \to R_3 – 3R_1[/Tex]

we get

[Tex]\begin{bmatrix} 1 & 1 & 1 \\ 4 & 3 & -1 \\ 3 & 5 & 3 \end{bmatrix} \sim[/Tex]

[Tex]\begin{bmatrix} 1 & 1 & 1 \\ 0 & -1 & -5 \\ 0 & 2 & 0 \end{bmatrix}[/Tex]

Now, by doing

[Tex]R_3 \to R_3 – (-2)R_2[/Tex]

We get

[Tex]\sim \begin{bmatrix} 1 & 1 & 1 \\ 0 & -1 & -5 \\ 0 & 0 & -10 \end{bmatrix}[/Tex]

(Remember to always keep ‘ – ‘ sign in between, replace ‘ + ‘ sign by two ‘ – ‘ signs) Hence, we get L =

[Tex]\begin{bmatrix} 1 & 0 & 0 \\ 4 & 1 & 0 \\ 3 & -2 & 1 \end{bmatrix}[/Tex]

and U =

[Tex]\begin{bmatrix} 1 & 1 & 1 \\ 0 & -1 & -5 \\ 0 & 0 & -10 \end{bmatrix}[/Tex]

(notice that in L matrix,

[Tex]l_{21} = 4[/Tex]

is from (1),

[Tex]l_{31} = 3[/Tex]

is from (2) and

[Tex]l_{32} = -2[/Tex]

is from (3)) Now, we assume Z

[Tex]= \begin{bmatrix} z_1 \\ z_2 \\ z_3 \end{bmatrix}[/Tex]

and solve L Z = C.

[Tex]\begin{bmatrix} 1 & 0 & 0 \\ 4 & 1 & 0 \\ 3 & -2 & 1 \end{bmatrix} \begin{bmatrix} z_1 \\ z_2 \\ z_3 \end{bmatrix}[/Tex]

[Tex]= \begin{bmatrix} 1 \\ 6 \\ 4 \end{bmatrix}[/Tex]

So, we have

[Tex]z_1 = 1 ,[/Tex]

[Tex]4z_1 + z_2 = 6 ,[/Tex]

[Tex]3z_1 – 2z_2 + z_3 = 4 .[/Tex]

Solving, we get

[Tex]z_1 = 1[/Tex]

[Tex]z_2 = 2[/Tex]

and

[Tex]z_3 = 5[/Tex]

. Now, we solve U X = Z

[Tex]\begin{bmatrix} 1 & 1 & 1 \\ 0 & -1 & -5 \\ 0 & 0 & -10 \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \\ x_3 \end{bmatrix}[/Tex]

[Tex]= \begin{bmatrix} 1 \\ 2 \\ 5 \end{bmatrix}[/Tex]

Therefore, we get

[Tex]x_1 + x_2 + x_3 = 1 ,[/Tex]

[Tex]-x_2 – 5x_3 = 2[/Tex]

[Tex]-10x_3 = 5 .[/Tex]

Thus, the solution to the given system of linear equations is

[Tex]x_1 = 1[/Tex]

[Tex]x_2 = 0.5[/Tex]

[Tex]x_3 = -0.5[/Tex]

and hence the matrix X =

[Tex]\begin{bmatrix} 1 \\ 0.5 \\ -0.5 \end{bmatrix}[/Tex]

## FAQs on LU Decomposition

### What is the LU decomposition method?

LU decomposition, short for Lower-Upper decomposition, is a matrix factorization technique used to break down a square matrix into the product of a lower triangular matrix (L) and an upper triangular matrix (U). It’s commonly employed to simplify solving systems of linear equations and calculating determinants.

### Why is LU decomposition unique?

LU decomposition is unique because it provides a way to factorize a square matrix A into lower and upper triangular matrices (L and U) uniquely, allowing efficient solving of linear systems and determinant calculation.

### How is LU decomposition calculated?

LU decomposition is calculated using Gaussian elimination, where you transform a square matrix A into lower (L) and upper (U) triangular matrices by performing row operations while keeping track of the changes in separate matrices. This process is iterative and continues until A is fully decomposed. The method with all the steps for LU decomposition is given in the article.

### When LU decomposition is not possible?

LU decomposition may not be possible when the matrix A is singular (non-invertible) or when it requires pivoting for stability, but the pivot element becomes zero, causing division by zero during the decomposition process.

### Are there any alternatives to LU decomposition?

Yes, alternatives to LU decomposition include Cholesky decomposition for symmetric positive definite matrices, QR decomposition for general matrices, and eigenvalue-based methods like spectral decomposition and singular value decomposition (SVD) for various matrix operations and applications.

### Can LU decomposition be applied to non-square matrices?

LU decomposition is typically applied to square matrices. For rectangular matrices, QR decomposition is more commonly used. However, variations like LUP decomposition can handle rectangular matrices as well, where P is a permutation matrix.

Elevate your coding journey with a Premium subscription. Benefit from ad-free learning, unlimited article summaries, an AI bot, access to 35+ courses, and more-available only with GeeksforGeeks Premium! Explore now!

GeeksforGeeks

Improve

Previous Article

Matrix Diagonalization

Next Article

Finding Inverse of a Square Matrix using Cayley Hamilton Theorem in MATLAB