LU Decomposition - Definitions

Definitions

Let A be a square matrix. An LU decomposition is a decomposition of the form

where L is a lower triangular matrix and U is an upper triangular matrix. This means that L has only zeros above the diagonal and U has only zeros below the diagonal. For example, for a 3-by-3 matrix A, its LU decomposition looks like this:

However, not all "well behaved" matrices can be factorized into this form. For example, it is easy to verify (by expanding the matrix multiplication) that . Therefore, if, then at least one of and has to be zero. However, in either case the product LU becomes singular, while A is not necessarily singular. This means such matrices cannot be LU decomposed. To overcome this limitation, LUP decomposition is commonly used.

An LUP decomposition (also called a LU decomposition with partial pivoting) is a decomposition of the form

where L and U are again lower and upper triangular matrices, and P is a permutation matrix which, when left-multiplied to A, reorders the rows of A. It turns out that all square matrices can be factorized in this form, and the factorization is numerically stable in practice. This makes LUP decomposition a useful technique in practice.

An LU decomposition with full pivoting takes the form

where L, U and P are defined same as before, and Q is a permutation matrix that reorders the columns of A.

An LDU decomposition is a decomposition of the form

where D is a diagonal matrix and L and U are unit triangular matrices, meaning that all the entries on the diagonals of L and U are one.

Above we required that A be a square matrix, but these decompositions can all be generalized to rectangular matrices as well. In that case, L and P are square matrices which each have the same number of rows as A, while U is exactly the same shape as A. Upper triangular should be interpreted as having only zero entries below the main diagonal, which starts at the upper left corner.