Recall that Gaussian elimination transforms a matrix to upper triangular form in stages. LU factorization is intimately connected with Gaussian elimination. Here,, where and are vectors of subscripts, denotes the submatrix formed from the intersection of the rows indexed by and the columns indexed by.

In fact, such determinantal formulas hold for all the elements of and : The left side of this equation is unit lower triangular and the right side is upper triangular therefore both sides must equal the identity matrix, which means that and, as required.Įquating leading principal submatrices in gives, which implies that. Indeed if has LU factorizations then the are necessarily nonsingular and so. However, if is nonsingular and has an LU factorization then the factorization is unique. Note that the (non)singularity of plays no role in Theorem 1. If is singular for some then the factorization may exist, but if so it is not unique. The matrix has a unique LU factorization if and only if is nonsingular for. Denote by the leading principal submatrix of of order. Conditions for existence and uniqueness are given in the following result (see Higham, 2002, Thm. įor a given, an LU factorization may or may not exist, and if it does exist it may not be unique. In particular, solving a linear system reduces to solving the triangular systems and, since then.

Example:Īn LU factorization simplifies the solution of many problems associated with linear systems. “Unit” means that has ones on the diagonal. An LU factorization of an matrix is a factorization, where is unit lower triangular and is upper triangular.

Lu factorization calculator