LUDecomposition
generates a representation of the LU decomposition of matrix m as a list {l,u,p,c}, where l is lower triangular, u is upper triangular, p is a permutation matrix, and c is an approximate condition number.
Details and Options
- LU decompositions are typically used for solving linear systems of equations and for other tasks such as inverting or computing the determinant of a matrix.
- An LU decomposition of m is a pair of matrices l and u, where l is a lower triangular matrix and u is an upper triangular matrix, with the property that
. - The linear system
can be solved in two steps using the above decomposition by first solving the system 
using "forward substitution" and then solving the system 
using "backward substitution". - By default, LUDecomposition[m] returns a list
where 
is a LowerTriangularMatrix object with 
s on the diagonal, 
is an UpperTriangularMatrix object, 
is a PermutationMatrix object that reflects the row permutations or pivoting operations used during the decomposition process, and 
is a condition number. The result satisfies 
. » - For approximate numerical matrices
, c is an estimate of the 
condition number of 
, ![TemplateBox[{m, infty}, Norm2] TemplateBox[{TemplateBox[{m}, Inverse, SyntaxForm -> SuperscriptBox], infty}, Norm2]](Files/LUDecomposition.en/17.png "TemplateBox[{m, infty}, Norm2] TemplateBox[{TemplateBox[{m}, Inverse, SyntaxForm -> SuperscriptBox], infty}, Norm2]")
. If the matrix is not numerical or the condition number is otherwise unavailable, it is reported as 0. » - The following options can be given:
-
Modulus 0 prime modulus to assume for integers Pivoting True whether to allow pivoting operations TargetStructure Automatic the structure of the returned matrices - LUDecomposition[m,Modulusp] computes the decomposition of the integer matrix m with respect to the prime modulus p.
- By default, LUDecomposition will pivot (permute) rows to improve numerical stability. With the setting PivotingFalse, pivoting is disabled and
will be an identity matrix. » - Possible settings for TargetStructure include:
-
Automatic, "Structured" return l, u and p as appropriate structured matrices "Dense" return l, u and p as normal lists of lists "Sparse" returns l, u and p as sparse matrices "Classic" returns the classic output {lu,p,c} with lu being a packed version of l and u. - With the setting Target"Classic", LUDecomposition returns a list {lu,p,c} of three elements. The first element, lu, is a combination of lower and upper triangular matrices l and u, respectively, the second element p is a permutation list specifying how rows are pivoted, and for approximate numerical matrices m, the third element c is an estimate of the L∞ condition number of m. The result satisfies l.u==m〚p〛, where l and u must be computed from lu using LowerTriangularize and UpperTriangularize. »
Examples
open all close allBasic Examples (2)
Compute the LU decomposition of a matrix:
m = (| | | |
| - | - | -- |
| 1 | 1 | 1 |
| 2 | 4 | 8 |
| 3 | 9 | 27 |);
{l, u, p, c} = LUDecomposition[m]MatrixForm /@ %l.u == p.mFind the LU decomposition of a symbolic matrix:
{l, u} = Take[LUDecomposition[(| | | |
| - | - | - |
| a | b | c |
| d | e | f |
| g | h | i |)], 2];
{MatrixForm[l], MatrixForm[u]}Verify that 
equals the original matrix:
l.u//Simplify//MatrixFormScope (13)
Basic Uses (7)
Find the LU decomposition of a machine-precision matrix:
LUDecomposition[{{1.6, 2.7, 3.6}, {1.2, 3.2, 5.2}, {3.3, 3.4, 6.5}}]MatrixForm /@ %LU decomposition for a complex matrix:
MatrixForm /@ LUDecomposition[(| | | |
| ------- | ------- | ------- |
| 2 + 4 I | 9 + 9 I | 9 + 2 I |
| 2 + 9 I | 1 + 3 I | 4 I |
| 3 + 8 I | 0 | 7 + 4 I |)]Use LUDecomposition for an exact matrix:
MatrixForm /@ LUDecomposition[(| | | |
| - | - | - |
| 3 | 1 | 5 |
| 2 | 4 | 6 |
| 8 | 7 | 9 |)]LU decomposition for an arbitrary-precision matrix:
MatrixForm /@ LUDecomposition[RandomReal[5, {3, 3}, WorkingPrecision -> 10]]The precision of the result follows the precision of the input:
Precision[%]Use LUDecomposition with a symbolic matrix:
MatrixForm /@ LUDecomposition[{{a, b}, {c, d}}]The LU decomposition for a large numerical matrix is computed efficiently:
mat = RandomReal[{0, 9}, {1000, 1000}];AbsoluteTiming[LUDecomposition[mat];]LU decomposition of a wide matrix:
w = (| | | |
| - | - | -- |
| 3 | 2 | 2 |
| 2 | 3 | -2 |);
{lw, uw, pw, cw} = LUDecomposition[w];
MatrixForm /@ %LU decomposition of a tall matrix:
t = (| | |
| - | -- |
| 3 | 2 |
| 2 | 3 |
| 2 | -2 |);
{lt, ut, pt, ct} = LUDecomposition[t];
MatrixForm /@ %The upper triangular matrix has the same shape as the input matrix:
Dimensions[ut] == Dimensions[t] && Dimensions[uw] == Dimensions[w]The lower triangular matrix is square with the same number of rows as the input:
SquareMatrixQ[lw] && Length[lw] == Length[w] && SquareMatrixQ[lt] && Length[lt] == Length[t]The product of the triangular matrices gives the permuted matrices:
lw.uw == pw.w && lw.uw == pw.wSpecial Matrices (6)
Find the LU decomposition for sparse matrices:
SparseArray[{{1, 3} -> 1, {2, 2} -> 2, {3, 1} -> 3}, {3, 3}]MatrixForm /@ LUDecomposition[%]SparseArray[{{x_, y_} /; Abs[x - y] < 3 -> 3}, {5, 5}]MatrixForm /@ LUDecomposition[%]LU decompositions of structured matrices:
SymmetrizedArray[{{1, 1} -> 2, {1, 2} -> 1}, {2, 2}, Symmetric[All]]MatrixForm /@ LUDecomposition[%]Use with a QuantityArray structured matrix:
QuantityArray[{{1, 4}, {3, 5}}, {"Meters", "Seconds"}]The units go in the 
matrix; the 
matrix is dimensionless:
MatrixForm /@ LUDecomposition[%]The LU decomposition of identity matrices is trivial:
MatrixForm /@ LUDecomposition[IdentityMatrix[3]]MatrixForm /@ LUDecomposition[IdentityMatrix[{3, 4}]]LU decomposition of HilbertMatrix:
MatrixForm /@ LUDecomposition[HilbertMatrix[5]]LU decomposition for a matrix with finite field elements:
ℱ = FiniteField[19, 3];
m = {{ℱ[12], ℱ[23], ℱ[34]}, {ℱ[45], ℱ[56], ℱ[67]}, {ℱ[78], ℱ[89], ℱ[90]}};
{l, u, p, c} = LUDecomposition[m]Format the results; the nontrivial elements of 
and 
are in the finite field:
MatrixForm /@ %l.u === p.mCompute LU decomposition for a matrix of CenteredInterval objects:
(m = Map[CenteredInterval, RandomReal[{-10, 10}, {3, 3}, WorkingPrecision -> 10], {2}])//MatrixFormThe nontrivial elements are more centered intervals:
{l, u, p, c} = LUDecomposition[m];
MatrixForm /@ %Confirm "equality" in the sense that each element of 
is a subinterval of 
:
MapThread[IntervalMemberQ, {l.u, p.m}, 2]//MatrixFormThe opposite inclusion does not hold:
MapThread[IntervalMemberQ, {p.m, l.u}, 2]//MatrixFormOptions (6)
Modulus (1)
Compute the LU decomposition of an integer matrix modulus 5:
m = (| | |
| - | - |
| 1 | 2 |
| 3 | 4 |);{l, u, p, c} = LUDecomposition[m, Modulus -> 5]The product of the matrices is not the original matrix in ordinary arithmetic:
l.u == mHowever, the two are equal modulus 5:
Mod[l.u, 5] == Mod[m, 5]Pivoting (2)
By default, decompositions are computed with pivoting to reduce numerical error:
m = (| | | |
| - | - | - |
| 3 | 1 | 5 |
| 2 | 4 | 6 |
| 8 | 7 | 9 |);
{lt, ut, pt, ct} = LUDecomposition[m]Compute the decomposition with pivoting disabled:
{lf, uf, pf, cf} = LUDecomposition[m, Pivoting -> False]Now the permutation is trivial:
pf == IdentityMatrix[3]However, both are valid decompositions:
{lt.ut == pt.m, lf.uf == m}If pivoting is disabled, the decomposition may be impossible:
LUDecomposition[{{0, 1}, {1, 0}}, Pivoting -> False]//Head
With the default value of the option, a decomposition is possible:
LUDecomposition[{{0, 1}, {1, 0}}]TargetStructure (3)
By default, the matrices are returned as structured objects:
m = {{1.6, 2.7, 3.6}, {1.2, 3.2, 5.2}, {3.3, 3.4, 6.5}};{l, u, p, c} = LUDecomposition[m]Have them returned as normal lists of lists:
{ld, ud, pd, cd} = LUDecomposition[m, TargetStructure -> "Dense"]Although the matrices are different objects, the results are equal:
{l, u, p, c} == {ld, ud, pd, cd}Obtain the results as spare arrays:
m = RandomReal[1, {3, 3}];
LUDecomposition[m, TargetStructure -> "Sparse"]This result is equal to the default, structured output:
% == LUDecomposition[m]Obtain the "Classic" form with lower and upper parts merged:
{lu, pList, c} = LUDecomposition[m = {{1, 1, 1}, {2, 4, 8}, {3, 9, 27}}, TargetStructure -> "Classic"]l = LowerTriangularize[lu, -1] + IdentityMatrix[3]u = UpperTriangularize[lu]Convert the permutation list to a permutation matrix:
p = PermutationMatrix[pList]Check that the results agree with the results from the default return form:
{l, u, p, c} == LUDecomposition[m]Applications (4)
The LU decomposition of a matrix 
decomposes a matrix into lower triangular (
) and upper triangular (
) parts that satisfy 
, where 
is a row permutation of 
:
d = 100;
m = RandomReal[1, {d, d}];
{l, u, p, n} = LUDecomposition[m];Verify the decomposition l.up.m:
Max[l.u - p.m]//ChopIllustrate the structure by using MatrixPlot:
Row[{MatrixPlot[l, PlotTheme -> "Minimal", ImageSize -> 100], ".", MatrixPlot[u, PlotTheme -> "Minimal", ImageSize -> 100], " == ", MatrixPlot[p.m, PlotTheme -> "Minimal", ImageSize -> 100]}]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:
system = {w + 8 x + y + 2 z == 3, 6 w + 8 x + 3 y + z == 5, 7 w + 2 x + 3 y + 8 z == 5, 2 w + 8 x + 3 y + 4 z == 6};Rewrite the system in matrix form 
and compute the LU decomposition of 
:
v = {w, x, y, z};
m = {{1, 8, 1, 2}, {6, 8, 3, 1}, {7, 2, 3, 8}, {2, 8, 3, 4}};
b = {3, 5, 5, 6};
{l, u, p, c} = LUDecomposition[m]Extract the 
and 
matrices; as 
, the original system can be reordered into 
:
p.system == Thread[l.u.v == p.b]Introduce new variables 
and set 
; the result is a triangular system in 
:
ν = {ω, ξ, ψ, ζ};
tri1 = Reverse[Thread[u.v == ν]];
Column[tri1]Substituting 
into 
gives 
, a triangular system in 
:
tri2 = Thread[l.ν == p.b];
Column[tri2]The eight triangular equations together give the same result for 
as the original system of equations:
v /. Solve[Join[tri1, tri2], Join[v, ν]]SolveValues[system, v]LU decompositions are mainly used to solve linear systems. Here is a 5×5 random matrix:
m = RandomReal[1, {5, 5}];LinearSolve[m] sets up an LU decomposition in a functional form convenient for solving:
luf = LinearSolve[m]This solves the system m.x=b for x:
b = ConstantArray[1, 5];
x = luf[b]Verify that x is indeed the solution:
m.xThis can be done manually with the output of LUDecomposition as well:
{l, u, p, c} = LUDecomposition[m]Solve the system with two backsolves:
y = LinearSolve[l, p.b];
x == LinearSolve[u, y]Up to sign, the determinant of 
is given by the product of the diagonal elements of 
:
m = RandomReal[1, {100, 100}, WorkingPrecision -> 10];{l, u, p, c} = LUDecomposition[m];Compute the product of the diagonal elements of 
Tr[u, Times]![TemplateBox[{m}, Det]](Files/LUDecomposition.en/50.png "TemplateBox[{m}, Det]"){kind=small}
Det[m]The sign can be fixed using the signature of the permutation represented by 
:
Det[m] == p["PermutationSignature"]Tr[u, Times]Properties & Relations (9)
Compute the LU decomposition of a matrix:
m = (| | | | | | |
| ------------------ | ------------------- | ------------------- | ------------------- | ------------------- | -------------------- |
| 0.7372293027827486 | 0.4751290760555402 | 0.7369097019897646 | 0.7231193916430927 | 0.9310045711997348 | 0.6260631184842838 |
| 0.0789341238693051 | 0.19937990746699152 | 0.06258129368985865 | 0.4754666530752132 | 0.7896644678158828 | 0.2881308853046789 |
| 0.9731846467939502 | 0.7947134735777408 | 0.6587005264278951 | 0.5758094900468378 | 0.2238061097208106 | 0.5964764017770123 |
| 0.7339417582698653 | 0.9016621690699067 | 0.883328445734211 | 0.49437318019679655 | 0.5661595087344482 | 0.026355960950372292 |
| 0.8539182422103526 | 0.26761673429222776 | 0.28383799679450417 | 0.10104583973749515 | 0.7000769066668582 | 0.08224110693819786 |
| 0.7152636281667595 | 0.612419951541082 | 0.5931025662252389 | 0.03896744411832098 | 0.03888946067952048 | 0.8570448326296252 |);
{l, u, p, c} = LUDecomposition[m];l is lower triangular and has ones along the diagonal:
{LowerTriangularMatrixQ[l], Diagonal[l]}UpperTriangularMatrixQ[u]l.u is equal to the permutation of the rows of m given by p:
l.u - p.m//ChopIf 
is a rectangular matrix, the 
matrix is square with the same number of rows as 
:
m = (| | | | |
| ------------------- | ------------------- | ------------------- | ------------------ |
| 0.30829046842088226 | 0.20823341560318998 | 0.6802727745899382 | 0.7359722172503973 |
| 0.02896486249431529 | 0.13207973322572908 | 0.4268624401071355 | 0.9429634233037159 |
| 0.47606447358059123 | 0.2480736415405338 | 0.13202945134919064 | 0.5612849334301935 |);
{l, u, p, c} = LUDecomposition[m];
l//MatrixFormThe 
matrix has the same shape as 
:
u//MatrixFormThe basic identity 
still holds:
l.u == p.mIf m decomposes to {l,u,p,c}, then Det[m] is the product of the diagonal entries of u and the signature of the permutation represented by p:
m = RandomInteger[9, {5, 5}];
{l, u, p, c} = LUDecomposition[m];
Det[m] == p["PermutationSignature"] * Times@@Diagonal[u]If a matrix is singular, the 
matrix will have a zero along the diagonal:
m = (| | | |
| - | - | - |
| 1 | 2 | 3 |
| 4 | 5 | 6 |
| 7 | 8 | 9 |);
LUDecomposition[m][[2]]//MatrixForm
The CholeskyDecomposition of a positive definite Hermitian matrix h:
h = {{2, 1}, {1, 2}};
PositiveDefiniteMatrixQ[h] && HermitianMatrixQ[h]MatrixForm[u = CholeskyDecomposition[h]]This gives a kind of LU decomposition via ConjugateTranspose:
MatrixForm[l = ConjugateTranspose[u]]l.u == hThis is generally a different decomposition from the one given by LUDecomposition:
First[LUDecomposition[h]]//MatrixFormLDLDecomposition[m] can be computed directly from LUDecomposition[m] when the latter returns a trivial permutation:
mat = {{3, -4, 5}, {-4, 8, -2}, {5, -2, 11}};
{Subscript[l, 1], d} = LDLDecomposition[mat];
{Subscript[l, 2], u, perm, c} = LUDecomposition[mat];
perm == IdentityMatrix[3]The two lower diagonal matrices are the same, and the diagonal entries of 
and 
are the same:
Subscript[l, 1] == Subscript[l, 2] && Diagonal[d] == Diagonal[u]The condition number of an invertible numerical matrix is ![TemplateBox[{m, infty}, Norm2] TemplateBox[{TemplateBox[{m}, Inverse, SyntaxForm -> SuperscriptBox], infty}, Norm2]](Files/LUDecomposition.en/62.png "TemplateBox[{m, infty}, Norm2] TemplateBox[{TemplateBox[{m}, Inverse, SyntaxForm -> SuperscriptBox], infty}, Norm2]"){kind=small}
:
m = (| | | |
| ------------------ | ------------------- | ------------------- |
| 0.9637800089256072 | 0.3042587156828416 | 0.48071231769669276 |
| 0.3587145233629381 | 0.13162298748174095 | 0.3966367219176594 |
| 0.7709299957993119 | 0.1433296531709578 | 0.23663508727905658 |);{Last[LUDecomposition[m]], Norm[m, Infinity]Norm[Inverse[m], Infinity]}The value returned by LUDecomposition is only an estimate:
a = (| | | |
| ------------------ | ------------------ | ------------------- |
| 0.2517124514003679 | 0.5277081839753666 | 0.8620540689438185 |
| 0.7379879479540143 | 0.0932600906028429 | 0.644610213285628 |
| 0.8151891835895801 | 0.9986863319371879 | 0.43253101038750685 |);{Last[LUDecomposition[a]], Norm[a, Infinity]Norm[Inverse[a], Infinity]}If the condition number is not available, it is reported as 0:
LUDecomposition[{{1.5, a}, {3.2, 4.1}}] //LastThe condition number 
is the same condition number reported by LinearSolve[m]:
m = RandomReal[1, {100, 100}];LinearSolve[m]Last[LUDecomposition[m]]Interactive Examples (1)
Visualize LU decompositions, where ![P=TemplateBox[{p}, Transpose]=TemplateBox[{p}, Inverse]](Files/LUDecomposition.en/64.png "P=TemplateBox[{p}, Transpose]=TemplateBox[{p}, Inverse]"){kind=small}
and hence 
:
Manipulate[
SeedRandom[sr];
With[{m = Table[Random[Integer, {0, max}], {n}, {n}]},
{l, u, perm, c} = Quiet[LUDecomposition[m]];
p = Transpose[perm];
Text[...]],
{{n, 4, "matrix rank"}, 2, 5, 1, Appearance -> "Labeled"}, {{max, 4, "maximum entry"}, 1, 9, 1, Appearance -> "Labeled"}, {{sr, 1, "seed random"}, 1, 100, 1}, SaveDefinitions -> True, TrackedSymbols :> {n, max, sr}]Text
Wolfram Research (1996), LUDecomposition, Wolfram Language function, https://reference.wolfram.com/language/ref/LUDecomposition.html (updated 2026).
CMS
Wolfram Language. 1996. "LUDecomposition." Wolfram Language & System Documentation Center. Wolfram Research. Last Modified 2026. https://reference.wolfram.com/language/ref/LUDecomposition.html.
APA
Wolfram Language. (1996). LUDecomposition. Wolfram Language & System Documentation Center. Retrieved from https://reference.wolfram.com/language/ref/LUDecomposition.html