# LU Decomposition: Study Notes

By Mukul Yadav|Updated : March 15th, 2023

LU decomposition, also known as LU factorization, is a matrix factorization technique used to solve linear systems of equations. It decomposes a square matrix A into two matrices, L and U, where L is a lower triangular matrix with 1's on the diagonal and U is an upper triangular matrix. LU decomposition has several applications, including solving linear systems of equations, calculating matrix inverses, and calculating determinants. It can also be used to efficiently solve linear equations for multiple right-hand sides, as the LU decomposition only needs to be performed once for a given matrix.

There are several methods for computing the LU decomposition, including Gaussian elimination and Crout's method. Each method has its own advantages and disadvantages, and the choice of method depends on the specific problem being solved. In this article, LU decomposition is discussed in detail with their examples.

## What is LU Decomposition?

LU decomposition is a method of matrix factorization that decomposes a matrix A into two triangular matrices, an upper triangular matrix U and a lower triangular matrix L, such that A = LU. The LU decomposition is commonly used for solving systems of linear equations, inverting matrices, and computing determinants.

The LU decomposition can be computed using Gaussian elimination, which is an algorithm for reducing a matrix to its row echelon form by performing a series of row operations. The row echelon form of a matrix is a triangular matrix with ones along the diagonal and zeros below the diagonal. Gaussian elimination can be used to compute both the L and U matrices simultaneously.

For a nonsingular matrix [A] on which one can successfully conduct the Naïve Gauss elimination forward elimination steps, one can always write it as

[A]=[L][U]

Where

[L]= Lower triangular matrix

[U]= Upper triangular matrix

Then if one is solving a set of equations

[A][X]=[C],

Then

[L][U][X]=[C] as ([A]=[L][U])

Multiplying both sides by [L]-1,

[L]-1[L][U][X]=[L]-1[C]

[I][U][X]=[L]-1[C] as ([L]-1[L]=[I])

[U][X]=[L]-1[C] as ([I][U]=[U])

Let

[L]-1[C]=[Z]

Then

[L][Z]=[C] …(1)

And

[U][X]=[Z] …(2)

So we can solve Equation (1) first for [Z] by using forward substitution and then use Equation (2) to calculate the solution vector [X] by back substitution.

## Decomposition of a Non-Singular Matrix

A non-singular matrix is a matrix that has an inverse. The LU decomposition of a non-singular matrix A is a factorization of A into the product of two triangular matrices L and U, such that A = LU. Here, L is a lower triangular matrix and U is an upper triangular matrix.

The LU decomposition of a non-singular matrix can be computed using Gaussian elimination with partial pivoting. This algorithm ensures that matrix A is transformed into an upper triangular matrix U with pivots on the diagonal and that the permutation matrix P is used to keep track of the row interchanges performed during the elimination process.

If forward elimination steps of the Naïve Gauss elimination methods can be applied on a non-singular matrix, then can be decomposed into LU as

The elements of the [U] matrix are exactly the same as the coefficient matrix one obtains at the end of the forward elimination steps in Naïve Gauss elimination.

The lower triangular matrix [L] has 1 in its diagonal entries. The non-zero elements on the non-diagonal elements in [L] are multipliers that made the corresponding entries zero in the upper triangular matrix [U] during forward elimination.

## Examples of LU Decomposition

Examples of LU Decomposition help to understand the topic, Here a few examples are shown which help to understand the related concepts in detail.

Example-1

Find the LU decomposition of the matrix

Solution

[A]=[L][U]

The [U] matrix is the same as found at the end of the forward elimination of the Naïve Gauss elimination method, that is

To find l21 and l31 find the multiplier that was used to make the a21 and a31 elements zero in the first step of forward elimination of the Naïve Gauss elimination method. It was

l21 = 64/25 = 2.56

l31 = 144/25 = 5.76

To find l32, what multiplier was used to make a32 element zero? Remember a32 element was made zero in the second step of forward elimination. The [A] matrix at the beginning of the second step of forward elimination was

So

l32 = -16.8/-4.8 = 3.5

Hence

Confirm [L][U]=[A].

Example-2

Use the LU decomposition method to solve the following simultaneous linear equations.

Solution

Recall that

[A][X]=[C]

and if

[A]=[L][U]

then first solving

[L][Z]=[C]

and then

[U][X]=[Z]

gives the solution vector [X].

Now in the previous example, we showed

[A]=[L][U]

First, solve

[L][Z]=[C]

to give

z1 = 106.8

2.56z1 +z2 = 177.2

5.76z1 + 3.5z2 +z3

Forward substitution starting from the first equation gives

z1 = 106.8

z2 = 177.2 - 2.56z1

= 177.2 - 2.56 × 106.8

= - 96.208

z3 = 279.2 - 5.76z1 - 3.5z2

=0.76

Hence

This matrix is the same as the right-hand side obtained at the end of the forward elimination steps of the Naïve Gauss elimination method.

Now solve

[U][X]=[Z]

From the third equation

0.7 a3 = 0.76

a3 = 0.76/0.7 = 1.0857

Substituting the value of a3 in the second equation,

Substituting the value of a2 and a3 in the first equation,

Hence the solution vector is

## Inverse of a Square Matrix Using LU Decomposition

LU decomposition is a matrix factorization technique that decomposes a square matrix into two triangular matrices, an upper triangular matrix (U) and a lower triangular matrix (L). LU decomposition is often used to solve systems of linear equations, and it can also be used to find the inverse of a square matrix.

To find the inverse of a square matrix using LU decomposition, follow these steps:

1. Perform LU decomposition on matrix A. This can be done using various techniques such as Gaussian elimination or Crout's method. Once you have obtained the matrices L and U, write the matrix equation as A = LU.

2. Solve the system of linear equations Ly = b, where b is a column vector with the same number of rows as A. This can be done by forward substitution, which involves solving for y in each row of the lower triangular matrix L.

3. Solve the system of linear equations Ux = y, where y is the solution obtained in step 2. This can be done by backward substitution, which involves solving for x in each row of the upper triangular matrix U.

4. The inverse of A is given by A-1 = x, where x is the solution obtained in step 3.

A matrix [B] is the inverse of [A] if

[A][B]=[I]=[B][A]

 Other Important GATE Topics 2's Complement Data Hazard Floating Point Representation Asynchronous Counter User-defined Data Types in C Full Subtractor

write a comment

## LU Decomposition FAQs

• LU decomposition is a matrix factorization method that decomposes a square matrix into two matrices: a lower triangular matrix (L) and an upper triangular matrix (U).

• The main purpose of LU decomposition is to simplify the process of solving a system of linear equations. It allows us to solve a system of equations by performing forward and backward substitution on the decomposed matrices instead of the original matrix.

• Gaussian Elimination is a method of solving a system of linear equations directly by reducing the augmented matrix to row echelon form. LU Decomposition, on the other hand, first decomposes the matrix into two triangular matrices and then solves the system of equations using forward and backward substitution.

• Not every matrix can be decomposed using LU Decomposition. For a matrix to be decomposed using LU Decomposition, it must be invertible and have nonzero pivots.

• LU Decomposition is used in many numerical methods such as solving linear systems, calculating determinants, finding matrix inverses, and solving differential equations.

### GATE & PSU CS

Computer ScienceGATEGATE CSENIELITOther ExamsQuick LinksMock Test