# LU decomposition

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.

 Contents

## Definition

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

[itex]P^{-1}A = L U [itex]
[itex]A = L UP [itex]

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 [itex]A = L U.[itex]

## Notes

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

[itex]A = L L^{*}[itex]

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.

## Algorithms

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

[itex]

A= (a_{n,n}) [itex] we define

[itex] A^{(0)} := A[itex]

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

[itex]l_{i,n} := -\frac{a_{i,n}^{(n-1)}}{a_{n,n}^{(n-1)}}[itex]

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

[itex]

L_n = \begin{pmatrix}

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


\end{pmatrix}. [itex]

We set

[itex] A^{(n)} := L_n A^{(n-1)}.[itex]

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

[itex]

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)}. [itex]

Denote the upper triangular matrix A(N-1) by U, and [itex]L=L_{1}^{-1} \ldots L_{N-1}^{-1}[itex]. 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 [itex]A=LU[itex].

It is clear that in order for this algorithm to work, one needs to have [itex]a_{n,n}^{(n-1)}\not=0[itex] at each step (see the definition of [itex]l_{i,n}[itex]). 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 [itex]P^{-1}A = L U [itex].

### Crout algorithm

Main article Crout matrix decomposition

## Applications

### Solving linear equations

Given a matrix equation

[itex]A x = L U x = b[itex]

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.

## See also

##### Navigation

Academic Kids Menu

• Art and Cultures
• Art (http://www.academickids.com/encyclopedia/index.php/Art)
• Architecture (http://www.academickids.com/encyclopedia/index.php/Architecture)
• Cultures (http://www.academickids.com/encyclopedia/index.php/Cultures)
• Music (http://www.academickids.com/encyclopedia/index.php/Music)
• Musical Instruments (http://academickids.com/encyclopedia/index.php/List_of_musical_instruments)
• Biographies (http://www.academickids.com/encyclopedia/index.php/Biographies)
• Clipart (http://www.academickids.com/encyclopedia/index.php/Clipart)
• Geography (http://www.academickids.com/encyclopedia/index.php/Geography)
• Countries of the World (http://www.academickids.com/encyclopedia/index.php/Countries)
• Maps (http://www.academickids.com/encyclopedia/index.php/Maps)
• Flags (http://www.academickids.com/encyclopedia/index.php/Flags)
• Continents (http://www.academickids.com/encyclopedia/index.php/Continents)
• History (http://www.academickids.com/encyclopedia/index.php/History)
• Ancient Civilizations (http://www.academickids.com/encyclopedia/index.php/Ancient_Civilizations)
• Industrial Revolution (http://www.academickids.com/encyclopedia/index.php/Industrial_Revolution)
• Middle Ages (http://www.academickids.com/encyclopedia/index.php/Middle_Ages)
• Prehistory (http://www.academickids.com/encyclopedia/index.php/Prehistory)
• Renaissance (http://www.academickids.com/encyclopedia/index.php/Renaissance)
• Timelines (http://www.academickids.com/encyclopedia/index.php/Timelines)
• United States (http://www.academickids.com/encyclopedia/index.php/United_States)
• Wars (http://www.academickids.com/encyclopedia/index.php/Wars)
• World History (http://www.academickids.com/encyclopedia/index.php/History_of_the_world)
• Human Body (http://www.academickids.com/encyclopedia/index.php/Human_Body)
• Mathematics (http://www.academickids.com/encyclopedia/index.php/Mathematics)
• Reference (http://www.academickids.com/encyclopedia/index.php/Reference)
• Science (http://www.academickids.com/encyclopedia/index.php/Science)
• Animals (http://www.academickids.com/encyclopedia/index.php/Animals)
• Aviation (http://www.academickids.com/encyclopedia/index.php/Aviation)
• Dinosaurs (http://www.academickids.com/encyclopedia/index.php/Dinosaurs)
• Earth (http://www.academickids.com/encyclopedia/index.php/Earth)
• Inventions (http://www.academickids.com/encyclopedia/index.php/Inventions)
• Physical Science (http://www.academickids.com/encyclopedia/index.php/Physical_Science)
• Plants (http://www.academickids.com/encyclopedia/index.php/Plants)
• Scientists (http://www.academickids.com/encyclopedia/index.php/Scientists)
• Social Studies (http://www.academickids.com/encyclopedia/index.php/Social_Studies)
• Anthropology (http://www.academickids.com/encyclopedia/index.php/Anthropology)
• Economics (http://www.academickids.com/encyclopedia/index.php/Economics)
• Government (http://www.academickids.com/encyclopedia/index.php/Government)
• Religion (http://www.academickids.com/encyclopedia/index.php/Religion)
• Holidays (http://www.academickids.com/encyclopedia/index.php/Holidays)
• Space and Astronomy
• Solar System (http://www.academickids.com/encyclopedia/index.php/Solar_System)
• Planets (http://www.academickids.com/encyclopedia/index.php/Planets)
• Sports (http://www.academickids.com/encyclopedia/index.php/Sports)
• Timelines (http://www.academickids.com/encyclopedia/index.php/Timelines)
• Weather (http://www.academickids.com/encyclopedia/index.php/Weather)
• US States (http://www.academickids.com/encyclopedia/index.php/US_States)

Information

• Home Page (http://academickids.com/encyclopedia/index.php)
• Contact Us (http://www.academickids.com/encyclopedia/index.php/Contactus)

• Clip Art (http://classroomclipart.com)