LU Decomposition Calculator (2024)

Welcome to Omni's LU decomposition calculator! Here you can determine the LU decompositions, learn what the LU decomposition is, and what its applications are. Moreover, we discuss when the LU decomposition exists (LU decomposition problems), and teach you how to find the LU decomposition by hand.

What does it mean to decompose a matrix?

To decompose (or factorize) a matrix means to write the matrix as a product of two or more matrices. This can significantly simplify some matrix operations because the matrices into which we decompose the original matrix have special properties, so we can easily perform various operations on them rather than on the original matrix. To discover matrix decompositions other than the LU decomposition discussed here, visit our QR decomposition calculator, the Cholesky decomposition calculator, and the singular value decomposition (SVD).

What is the LU decomposition?

💡 Did you know that it was the Polish mathematician Tadeusz Banachiewicz who introduced the LU decomposition in 1938.

Does the LU decomposition always exist? LU decomposition problems

Do you think it would be all too perfect if we could take any square matrix and write it as the product of a lower and upper triangular matrices? You're right, it may happen that a matrix does not admit an LU decomposition. For instance, let's take a look at the following 2x2 matrix:

$$\footnotesize\begin{bmatrix}0 & 1 \\2 & 3 \\\end{bmatrix}$$[02​13​]

and try to write it as a product of a lower-triangular and upper-triangular matrices:

$$\footnotesize\begin{bmatrix}0 & 1 \\2 & 3 \\\end{bmatrix}=\begin{bmatrix}\ell_{11} & 0 \\\ell_{21} & \ell_{22} \\\end{bmatrix}\cdot\begin{bmatrix}u_{11} & u_{12} \\0 & u_{22} \\\end{bmatrix}$$[02​13​]=[ℓ11​ℓ21​​0ℓ22​​]⋅[u11​0​u12​u22​​]

We see that the following equality needs to hold:

$$\footnotesize \ell_{11} \cdot u_{11} = 0$$ℓ11​⋅u11​=0

which implies that either $\ell_{11} = 0$ℓ11​=0 or $u_{11} = 0$u11​=0. Next, however, we have the following equalities:

$$\footnotesize\begin{aligned}&\text{1) }\ell_{11} \cdot u_{12} = 1 \\&\text{2) }\ell_{21} \cdot u_{11} = 2 \\\end{aligned}$$​1)ℓ11​⋅u12​=12)ℓ21​⋅u11​=2​

which imply that neither $\ell_{11} = 0$ℓ11​=0 nor $u_{11}=0$u11​=0 can hold. Hence, there is a contradiction with the assumption that our matrix can be written as a product of a lower and upper triangular matrix. However, once we permute it rows, we arrive at

$$\footnotesize\begin{bmatrix}2 & 3 \\0 & 1 \\\end{bmatrix}$$[20​31​]

which is an upper-triangular matrix! Hence, the LU decomposition is trivial:

$$\footnotesize\begin{bmatrix}2 & 3 \\0 & 1 \\\end{bmatrix}=\begin{bmatrix}1 & 0 \\0 & 1 \\\end{bmatrix}\cdot\begin{bmatrix}2 & 3 \\0 & 1 \\\end{bmatrix}$$[20​31​]=[10​01​]⋅[20​31​]

It turns out that even if the LU decomposition is not possible for a square matrix, there always exists a permutation of rows of the matrix such that the LU factorization is achievable for this permuted matrix. This is called LU factorization with partial pivoting and can be written as:

$$\footnotesizePA = LU,$$PA=LU,

How to find the LU decomposition?

For a general $n × n$n×n matrix $A$A, we assume that the factorization follows the below LU decomposition formula

$$A = LU$$A=LU

which exists and we can write it down explicitly. For instance, for a $3\times3$3×3 matrix, we have:

$$\footnotesize\begin{aligned}&\begin{bmatrix}a_{11} & a_{12} & a_{13} \\a_{21} & a_{22} & a_{23} \\a_{31} & a_{32} & a_{33} \\\end{bmatrix} \\[15pt]=&\begin{bmatrix}\ell_{11} & 0 & 0 \\\ell_{21} & \ell_{22} & 0 \\\ell_{31} & \ell_{32} & \ell_{33} \\\end{bmatrix}\!\cdot\!\begin{bmatrix}u_{11} & u_{12} & u_{13} \\0 & u_{22} & u_{23} \\0 & 0 & u_{33} \\\end{bmatrix}\end{aligned}$$=​[a11​a21​a31​​a12​a22​a32​​a13​a23​a33​​][ℓ11​ℓ21​ℓ31​​0ℓ22​ℓ32​​00ℓ33​​]⋅[u11​00​u12​u22​0​u13​u23​u33​​]​

As you can see, there are more unknowns on the left-hand side of the equation than on the right-hand side, so some of them can be set to any non-zero value. It's common to set all the entries of the main diagonal of the lower triangular matrix to ones (such a matrix is called a unit triangular matrix):

$$\footnotesize\begin{aligned}&\begin{bmatrix}a_{11} & a_{12} & a_{13} \\a_{21} & a_{22} & a_{23} \\a_{31} & a_{32} & a_{33} \\\end{bmatrix} \\[15pt]=&\begin{bmatrix}1 & 0 & 0 \\\ell_{21} & 1 & 0 \\\ell_{31} & \ell_{32} & 1 \\\end{bmatrix}\!\cdot\!\begin{bmatrix}u_{11} & u_{12} & u_{13} \\0 & u_{22} & u_{23} \\0 & 0 & u_{33} \\\end{bmatrix}\end{aligned}$$=​[a11​a21​a31​​a12​a22​a32​​a13​a23​a33​​][1ℓ21​ℓ31​​01ℓ32​​001​]⋅[u11​00​u12​u22​0​u13​u23​u33​​]​

$$\footnotesize\begin{aligned}\text{1) } a_{11} &= 1 \cdot u_{11}\\\text{2) } a_{12} &= 1 \cdot u_{12}\\\text{3) } a_{13} &= 1 \cdot u_{13}\\\text{4) } a_{21} &= \ell_{21} \cdot u_{11}\\\text{5) } a_{22} &= \ell_{21} \cdot u_{12} + 1 \cdot u_{22} \\\text{6) } a_{23} &= \ell_{21} \cdot u_{13} + 1 \cdot u_{23} \\\text{7) } a_{31} &= \ell_{31} \cdot u_{11} \\\text{8) } a_{32} &= \ell_{31} \cdot u_{12} + \ell_{32} \cdot u_{22} \\\text{9) } a_{33} &= \ell_{31} \cdot u_{13} + \ell_{32} \cdot u_{23} + 1 \cdot u_{33} \end{aligned}$$1)a11​2)a12​3)a13​4)a21​5)a22​6)a23​7)a31​8)a32​9)a33​​=1⋅u11​=1⋅u12​=1⋅u13​=ℓ21​⋅u11​=ℓ21​⋅u12​+1⋅u22​=ℓ21​⋅u13​+1⋅u23​=ℓ31​⋅u11​=ℓ31​⋅u12​+ℓ32​⋅u22​=ℓ31​⋅u13​+ℓ32​⋅u23​+1⋅u33​​

$$\footnotesize\qquad\begin{aligned}u_{1j} &= a_{1j} \\\ell_{j1} &= a_{j1} / u_{1j}\end{aligned}$$u1j​ℓj1​​=a1j​=aj1​/u1j​​

$$\footnotesize\qquad\begin{aligned}u_{ii} =&\ a_{ii} - \sum_{p=1}^{i-1} \ell_{ip} u_{pi} \\[1.5em]u_{ij} =&\ a_{ij} - \sum_{p=1}^{i-1}\ell_{ip} u_{pj} \\[1.5em]&\quad \text{for } j = i+1, ..., n \\[1.5em]\ell_{ji} =&\ \frac{1}{u_{ii}} \left( a_{ji} - \sum_{p=1}^{i-1} \ell_{jp}u_{pi}\right)\\[1.5em]&\quad \text{for } j = i+1, ..., n \\\end{aligned}$$uii​=uij​=ℓji​=​aii​−p=1∑i−1​ℓip​upi​aij​−p=1∑i−1​ℓip​upj​forj=i+1,...,nuii​1​(aji​−p=1∑i−1​ℓjp​upi​)forj=i+1,...,n​

$$\footnotesize\qquadu_{nn} = a_{nn} - \sum_{p=1}^{n-1} \ell_{np} u_{pn}$$unn​=ann​−p=1∑n−1​ℓnp​upn​

How to use this LU decomposition calculator?

Applications of the LU decomposition

$$\footnotesize\begin{aligned}\det(A) &= \det(L) \cdot \det(U) \\&= (\ell_{11} \cdot ... \cdot \ell_{nn})( u_{11} \cdot ... \cdot u_{nn} ),\end{aligned}$$det(A)​=det(L)⋅det(U)=(ℓ11​⋅...⋅ℓnn​)(u11​⋅...⋅unn​),​

FAQ

Does every square matrix have an LU decomposition?

No, some square matrices do not have an LU decomposition. However, it is always possible to permute the rows of a square matrix in such a way that after this permutation it will have an LU decomposition.

What is L and U in the LU decomposition?

L stands for a Lower triangular matrix and U for an Upper triangular matrix. When a matrix A is LU-decomposed, it will deliver a pair of such matrices L and U.

How do I find the inverse of a matrix using LU decomposition?

Recall the inverse principle: if A = LU, then A⁻¹ = U⁻¹L⁻¹ (mind the change in order!). Then find the inverses of U and L. It will be quite easy because of the many zeros contained in these matrices.