# LUDecomposition

generates a representation of the LU decomposition of a square matrix m.

# Details and Options • LUDecomposition returns a list of three elements. The first element is a combination of upper and lowertriangular matrices, the second element is a vector specifying rows used for pivoting, and for approximate numerical matrices m the third element is an estimate of the L condition number of m.

# Examples

open allclose all

## Basic Examples(2)

Compute the LU decomposition of a matrix:

l is the strictly lower triangular part of lu with ones assumed along the diagonal:

u is the upper triangular part of lu:

l.u reconstructs the original matrix:

Find the LU decomposition of a symbolic matrix:

Extract the and matrices:

Verify that equals the original matrix:

## Scope(11)

### Basic Uses(7)

Find the LU decomposition of a machine-precision matrix:

Since is not an identity permutation, is the permuted matrix rather than :

LU decomposition for a complex matrix:

Format the result:

Use LUDecomposition with an exact matrix:

LU decomposition for an arbitrary-precision matrix:

Use LUDecomposition with a symbolic matrix:

The LU decomposition for a large numerical matrix is computed efficiently:

LU decomposition of a non-square matrix:

The and matrices have the same shape as :

The matrix is square, with the same number of rows as  gives the permuted matrix :

### Special Matrices(4)

Find the LU decomposition for sparse matrices:

LU decompositions of structured matrices:

Use with a QuantityArray structured matrix:

The units go in the matrix; the matrix is dimensionless:

LU decomposition of an identity matrix gives the input as both and :

LU decomposition of HilbertMatrix:

## Applications(4)

The LU decomposition of a matrix decomposes a matrix into lower triangular ( ) and upper triangular ( ) parts that satisfy , where is a column permutation of :

Extract the lower and upper parts of the decomposition:

Verify the decomposition l.uap:

Illustrate the structure by using MatrixPlot:

A triangular linear system is a system of linear equations in which the first equation has one variable and each subsequent equation introduces exactly one additional variable. Rewrite the following system in four variables as two triangular linear systems in eight variables:

Rewrite the system in matrix form and compute the LU decomposition of :

Extract the and matrices; as , the original system can be reordered into :

Introduce new variables and set ; the result is a triangular system in :

Substituting into gives , a triangular system in :

The eight triangular equations together give the same result for as the original system of equations:

LU decompositions are mainly used to solve linear systems. Here is a 5×5 random matrix:

LinearSolve[m] sets up an LU decomposition in a functional form convenient for solving:

This solves the system m.x=b for x:

Verify that x is indeed the solution:

This can be done manually with the output of LUDecomposition as well:

Extract the lower and upper parts of the decomposition:

Solve the system with two backsolves:

m is a random 100×100 matrix:

Compute the LU decomposition of m:

Up to sign, the determinant of m is given by the product of the diagonal elements of lu:

The sign can be fixed using Signature[p]:

## Properties & Relations(9)

m is a 6×6 matrix:

Compute the LU decomposition of m:

l is the strictly lowertriangular part of lu with ones assumed along the diagonal:

u is the uppertriangular part of lu:

l.u is equal to to the permutation of the rows of m given by p:

If is a rectangular matrix, the matrix is square with the same number of rows as :

The matrix has the same shape as :

The basic identity still holds:

The permutation list returned by LUDecomposition can be converted to a matrix using PermutationMatrix. The identity then holds:

If m decomposes to {lu,p,c}, then Det[m] is the product of the diagonal entries of lu and Signature[p]:

If a matrix is singular, the matrix will have a zero along the diagonal: The CholeskyDecomposition of a positive-definite, Hermitian matrix h:

This gives a kind of LU decomposition via ConjugateTranspose:

This is generally a different decomposition from the one given by LUDecomposition:

The condition number of an invertible numerical matrix is :

The value returned by LUDecomposition is only an estimate:

The condition number of an exact or symbolic matrix is reported as 0:

The condition number is the same condition number reported by LinearSolve[m]