Omni Calculator logo

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?

The LU decomposition factors a square matrix A into the product of two matrices:

A = LU,

where:

  • L is a lower triangular matrix (all elements above the diagonal are zero); and
  • U is an upper triangular matrix (all the elements below the diagonal are zero).

💡 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:

[0123]\footnotesize \begin{bmatrix} 0 & 1 \\ 2 & 3 \\ \end{bmatrix}

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

[0123]=[1102122][u11u120u22]\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}

We see that the following equality needs to hold:

11u11=0\footnotesize \ell_{11} \cdot u_{11} = 0

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

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

which imply that neither 11=0\ell_{11} = 0 nor u11=0u_{11}=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

[2301]\footnotesize \begin{bmatrix} 2 & 3 \\ 0 & 1 \\ \end{bmatrix}

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

[2301]=[1001][2301]\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}

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:

PA=LU,\footnotesize PA = LU,

where:

  • PP is a permutation matrix (it reorders the rows of AA);
  • LL is a lower triangular matrix; and
  • UU is an upper triangular matrix.

How to find the LU decomposition?

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

A=LUA = LU

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

[a11a12a13a21a22a23a31a32a33]=[110021220313233][u11u12u130u22u2300u33]\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}

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):

[a11a12a13a21a22a23a31a32a33]=[100211031321][u11u12u130u22u2300u33]\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}

Now, we write down the system of linear equations implied by the standard matrix multiplication procedure and solve for the remaining unknown entries of LL and UU.

In our LU decomposition example, we have:

1) a11=1u112) a12=1u123) a13=1u134) a21=21u115) a22=21u12+1u226) a23=21u13+1u237) a31=31u118) a32=31u12+32u229) a33=31u13+32u23+1u33\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}

Clearly, from the first three equations we immediately get the values of u11u_{11}, u12u_{12} and u13u_{13}, which we then plug into the remaining equations. The 4th and 7th equations allow us to find 21\ell_{21} and 31\ell_{31}. Then, the 5th and 6th equations give the values of u22u_{22} and u23u_{23}. Finally, the last two equations will produce the solutions for 32\ell_{32} and u33u_{33}.

As you can see, for small matrices it's not hard to write down the system and solve it. For larger matrices, however, it's more convenient to have a bunch of ready formulas for the coefficients of LL and UU. Here they are for an n×nn\times n matrix:

  1. Find the first row of UU and the first column of LL. For each j=1,...,nj = 1, ... , n, we have
u1j=a1jj1=aj1/u1j\footnotesize \qquad \begin{aligned} u_{1j} &= a_{1j} \\ \ell_{j1} &= a_{j1} / u_{1j} \end{aligned}
  1. Next, for each i=1,...,n1i = 1, ... , n-1, we have
uii= aiip=1i1ipupiuij= aijp=1i1ipupjfor j=i+1,...,nji= 1uii(ajip=1i1jpupi)for j=i+1,...,n\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}
  1. Finally, we can determine the last entry of UU:
unn=annp=1n1npupn\footnotesize \qquad u_{nn} = a_{nn} - \sum_{p=1}^{n-1} \ell_{np} u_{pn}

How to use this LU decomposition calculator?

As we have seen in the previous section, finding LU decompositions can be difficult, or at least time-consuming, especially for larger matrices. Thankfully, Omni's LU decomposition calculator is here to help you save some time, which you may then spend chilling out! 😀

To quickly determine the LU decomposition with the help of our LU decomposition calculator, follow these steps:

  1. Choose the size of the matrix you want to find the LU decomposition of.
  2. Enter the coefficients of your matrix into the respective fields of the LU decomposition calculator.
  3. If your matrix admits an LU decomposition, the calculator will display it. Otherwise, a warning message will appear. Permute the rows of your matrix and try again.
  4. You can adjust the precision with which this LU decomposition calculator operates. Go to the advanced mode and change the precision field according to your need. By default, 3 significant figures are displayed.

Applications of the LU decomposition

As we can see, the LU decomposition factors a matrix into two triangular matrices which can be quickly done with our LU decomposition solver. Triangular matrices are very friendly to work with, e.g., when it comes to:

  • Calculating matrix determinant;
  • Finding inverse matrices; and
  • Solving systems of linear equations.

Let's discuss in more detail how the LU decomposition helps to find determinants. Recall that:

  • The determinant of a triangular matrix is the product of the diagonal entries; and
  • The determinant of a product of matrices is the product of determinants of these matrices (we say that the determinant is multiplicative)

Therefore, if we need to find det(A)\det(A) and we know the LU decomposition A=LUA = LU, then:

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

where:

  • 11...nn\ell_{11} \cdot ... \cdot \ell_{nn} are the diagonal entries of LL; and
  • u11...unnu_{11} \cdot ... \cdot u_{nn} are the diagonal entries of UU.

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.

Anna Szczepanek, PhD
Matrix size
Size
2 x 2
A = a₁a₂
b₁b₂
Matrix entries
a₁
a₂
b₁
b₂
Check out 35 similar linear algebra calculators 🔢
Adjoint matrixCharacteristic polynomialCholesky decomposition… 32 more
People also viewed…

Circumference

Use this free circumference calculator to find the area, circumference and diameter of a circle.

Equation of a circle

Equation of a circle calculator finds a circle's radius and center coordinates on a Cartesian plane.

Radius of a circle

The radius of a circle calculator returns the length of a circle's radius based on the input data: the circumference, area, or diameter.

Social Media Time Alternatives

Check what you could have accomplished if you get out of your social media bubble.
Copyright by Omni Calculator sp. z o.o.
Privacy, Cookies & Terms of Service