LU Decomposition Method

To factories 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

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

[Tex]\begin{equation*} x_1 + x_2 + x_3 = 1 \end{equation*} \begin{equation*} 4x_1 + 3x_2 – x_3 = 6 \end{equation*} \begin{equation*} 3x_1 + 5x_2 + 3x_3 = 4 \end{equation*} [/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]\begin{equation} R_2 \to R_2 – 4R_1 \end{equation}  [/Tex][Tex]\begin{equation} R_3 \to R_3 – 3R_1 \end{equation} [/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]\begin{equation} R_3 \to R_3 – (-2)R_2 \end{equation} [/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]

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 method of factorizing a matrix as a product of two triangular matrices has various applications such as a solution of a system of equations, which itself is an integral part of many applications such as finding current in a circuit and solution of discrete dynamical system problems; finding the inverse of a matrix and finding the determinant of the matrix.