LU decomposition

From Academic Kids

In linear algebra, a LU decomposition, or LUP decomposition is a matrix decomposition of a matrix into a lower triangular matrix L, an upper-triangular matrix U, and a permutation matrix P. This decomposition is used in numerical analysis to solve systems of linear equations.



Let A be an invertible matrix over a field. The matrix A can be decomposed as

<math>P^{-1}A = L U <math>
<math>A = L UP <math>

where P is a permutation matrix (as is P-1), L is a lower triangular matrix, and U is an upper triangular matrix. Sometimes the permutation matrix can be chosen to be the identity matrix. In this case the decomposition becomes <math>A = L U.<math>


If the matrix A is positive definite we can construct the even simpler Cholesky decomposition

<math>A = L L^{*}<math>

with L a lower triangular matrix with positive diagonal entries, and L* the conjugate transpose of L.

Main idea

The LU decomposition is basically a modified form of Gaussian elimination. We transform the matrix A into an upper triangular matrix U by eliminating the entries below the main diagonal. The elimination is done column by column starting from the left, by multiplying A to the left with atomic lower triangular matrices.


There are two different algorithms to construct a LU-decomposition. The Doolittle decomposition constructs a unit lower triangular matrix and an upper triangular matrix, whereas the Crout algorithm constructs a lower triangular matrix and an unit upper triangular matrix.

Doolittle algorithm

Given an NxN matrix


A= (a_{n,n}) <math> we define

<math> A^{(0)} := A<math>

and then we iterate n = 1,...,N-1 as follows.

We eliminate the matrix elements below the main diagonal in the n-th column of A(n-1) by adding to i-th row of this matrix the n-th row multiplied by

<math>l_{i,n} := -\frac{a_{i,n}^{(n-1)}}{a_{n,n}^{(n-1)}}<math>

for <math>i = n+1,\ldots,N<math>. This can be done by multiplying A(n-1) to the left with the lower triangular matrix


L_n = \begin{pmatrix}

    1 &        &           &         &         & 0 \\
      & \ddots &           &         &         &   \\
      &        &         1 &         &         &   \\
      &        & l_{n+1,n} &  \ddots &         &   \\
      &        &    \vdots &         &  \ddots &   \\
    0 &        &   l_{N,n} &         &         & 1 \\

\end{pmatrix}. <math>

We set

<math> A^{(n)} := L_n A^{(n-1)}.<math>

After N-1 steps, we eliminated all the matrix elements below the main diagonal, so we obtain an upper triangular matrix A(N-1). We find the decomposition


A = L_{1}^{-1} L_{1} A^{(0)} = L_{1}^{-1} A^{(1)} = L_{1}^{-1} L_{2}^{-1} L_{2} A^{(1)} = L_{1}^{-1}L_{2}^{-1} A^{(2)} =\ldots = L_{1}^{-1} \ldots L_{N-1}^{-1} A^{(N-1)}. <math>

Denote the upper triangular matrix A(N-1) by U, and <math>L=L_{1}^{-1} \ldots L_{N-1}^{-1}<math>. Because the inverse of a lower triangular matrix Ln is again a lower triangular matrix, and the multiplication of two lower triangular matrices is again a lower triangular matrix, it follows that L is a lower triangular matrix. We obtain <math>A=LU<math>.

It is clear that in order for this algorithm to work, one needs to have <math>a_{n,n}^{(n-1)}\not=0<math> at each step (see the definition of <math>l_{i,n}<math>). If this assumption fails at some point, one needs to interchange n-th row with another row below it before continuing. This is why the LU decomposition in general looks like <math>P^{-1}A = L U <math>.

Crout algorithm

Main article Crout matrix decomposition


Solving linear equations

Given a matrix equation

<math>A x = L U x = b<math>

we want to solve the matrix A for a given b. Triangular matrices (upper and lower) can be solved directly using forward and backward substitution without using the slow Gaussian elimination process. So when we have to solve a matrix equation multiple times for different b it is faster to do a LU-decomposition of the matrix once and then solve the triangular matrices for the different b than to use Gaussian elimination each time.

Inverse matrix

The matrices L and U can be used to calculate the matrix inverse. Computer implementations that invert matrices often use this approach.

Related articles

See also

it:Decomposizione LU ja:LU分解 nl:LU-decompositie pl:Metoda LU


Academic Kids Menu

  • Art and Cultures
    • Art (
    • Architecture (
    • Cultures (
    • Music (
    • Musical Instruments (
  • Biographies (
  • Clipart (
  • Geography (
    • Countries of the World (
    • Maps (
    • Flags (
    • Continents (
  • History (
    • Ancient Civilizations (
    • Industrial Revolution (
    • Middle Ages (
    • Prehistory (
    • Renaissance (
    • Timelines (
    • United States (
    • Wars (
    • World History (
  • Human Body (
  • Mathematics (
  • Reference (
  • Science (
    • Animals (
    • Aviation (
    • Dinosaurs (
    • Earth (
    • Inventions (
    • Physical Science (
    • Plants (
    • Scientists (
  • Social Studies (
    • Anthropology (
    • Economics (
    • Government (
    • Religion (
    • Holidays (
  • Space and Astronomy
    • Solar System (
    • Planets (
  • Sports (
  • Timelines (
  • Weather (
  • US States (


  • Home Page (
  • Contact Us (

  • Clip Art (
Personal tools