The LU decomposition, or also known as lower upper factorization, is one of the methods of solving square systems of linear equations. As its name implies, the LU factorization decomposes matrix A into a product of two matrices: a lower triangular matrix L and an upper triangular matrix U. The decomposition can be represented as follows:

Here, we can see , , and so on. A lower triangular matrix is a matrix that contains values in its lower triangle with the remaining upper triangle populated with zeros. The converse is true for an upper triangular matrix.

The definite advantage of the LU decomposition method over the Cholesky decomposition method is that it works for any square matrices. The latter method only works for symmetric and positive definite matrices.

Remember the previous example of a 3 by 3 matrix A. This time, though, we will use the linalg package of the SciPy module for the LU decomposition:

""" LU decomposition with SciPy """
import scipy.linalg as linalg
import numpy as np

A = np.array([[2., 1., 1.],
              [1., 3., 2.],
              [1., 0., 0.]])
B = np.array([4., 5., 6.])

LU = linalg.lu_factor(A)
x = linalg.lu_solve(LU, B) 

To view the values of x, execute the following command:

>>> print x
[  6.  15. -23.]

We get the same values of 6, 15, and -23 for , , and respectively.

Note that we used the lu_factor function of scipy.linalg here, which gives the LU variable as the pivoted LU decomposition of matrix A. We used the lu_solve function that takes in the pivoted LU decomposition and the vector B to solve the equation system.

We can display the LU decomposition of matrix A using the lu function. The lu function returns three variables : the permutation matrix P, the lower triangular matrix L, and the upper triangular matrix U, individually:

>>> P, L, U = scipy.linalg.lu(A)

When we print out these variables, we can conclude the relationship between the LU factorization and matrix A as follows:

The LU decomposition can be viewed as the matrix form of Gaussian elimination performed on two simpler matrices: the upper triangular and lower triangular matrices.