What is LU decomposition?

LU decomposition stands for Lower-Upper decomposition. LU decomposition is the factorization of the lower triangular matrix and an upper triangular matrix. It is very useful in linear algebra and numerical analysis. A permutation matrix is usually included in the product. Gaussian elimination in a matrix form is known as LU decomposition, When inverting a matrix or evaluating its determinant, this is a crucial step. Tadeusz Banachiewicz, a Polish mathematician, first proposed the LU decomposition in 1938.

Alan Turing, who also made the Turing machine, created LU decomposition in 1948 as an alternative to Gaussian elimination by factoring the coefficient matrix into an upper triangular and lower triangular matrix production. It is represented in the form:

A = LU

Users can use the LU decomposition to analyze linear equations and determine the inverse (for example, the inverse function in MATLAB), and obtain the determinant of a matrix (a triangular matrix's determinant is obtained from by using the product of its diagonal entries).

Definition of LU decomposition

Let's consider A as a square matrix. The two ingredients combine to form a LU. A lower triangular matrix is the first ingredient, and an upper triangular matrix is the second. The L is the identification of the lower triangular matrix and The upper triangular is represented by the U.

A = LU

In the lower triangular matrix, all components above the diagonal are zero, while in the upper triangular matrix, all components below the diagonal are zero. For example, an LU decomposition done in a 3x3 matrix:

$\left[\begin{array}{ccc}{a}_{11}& a_{12}& a_{13}\\ a_{21}& a_{22}& a_{23}\\ a_{31}& a_{32}& a_{33}\end{array}\right]=\left[\begin{array}{ccc}{l}_{11}& 0& 0\\ l_{21}& l_{22}& 0\\ l_{31}& l_{32}& l_{33}\end{array}\right]\left[\begin{array}{ccc}{u}_{11}& u_{12}& u_{13}\\ 0& u_{22}& u_{23}\\ 0& 0& u_{33}\end{array}\right]$

To get $a_{11}$, use $a_{11}$ = $l_{11}·u_{11}$,  That means it is obtained by using the production of the first row of L and first column of R. if $a_{11}=0$ it represents one of the $l_{11}$ or $u_{11}$ is zero, which denotes the singularity of either l or u. This is invertible if A is not singular. It's a procedural issue that can be solved by reordering the rows of A in such a way that the first element of the permuted matrix is non-zero. 

Partial pivoting LU factorization

A partial pivoting LU factorization only uses row permutations. It uses the factorization technique. When P (permutation matrix) is left-multiplied by a square matrix A, it reorders the elements of row A. It is done in row permutation only.

$PA = LU$

Here, L is the lower and U is the upper triangular matrices, respectively, and p denotes a permutation matrix. A square binary matrix with one 1 entry in each row and column and 0s everywhere else is known as a permutation matrix. Factorization is possible for all square matrices. As a result, the factorization of LU is numerically constant in the actual world. As a result, LUP decomposition is a useful technique.

Example of partial pivoting

In a linear system,

$\left[A\right]\left\{X\right\} = \left[B\right]$

$A = \left[\begin{array}{ccc}2& -6& -1\\ -3& -1& 7\\ -8& 1& -2\end{array}\right]$

If LU decomposition is used with partial pivoting, it gives the first column of the inverse matrix ${\left[A\right]}^{-1}$.

 $\begin{array}{rcl}A & =& \left[\begin{array}{ccc}2& -6& -1\\ -3& -1& 7\\ -8& 1& -2\end{array}\right] R_1\leftrightarrow R_3\\ & =& \left[\begin{array}{ccc}-8& 1& -2\\ -3& -1& 7\\ 2& -6& -1\end{array}\right]\end{array}$

Because R1 and R3 are swapped, keep in mind that b1 and b3 will be swapped in the solution vector.

The solution vector's order will be $\left[\begin{array}{c}{b}_3\\ b_2\\ b_1\end{array}\right]$.

To find the matrix U, use Gauss Elimination.

$\begin{array}{rcl}& \Rightarrow & \left[\begin{array}{ccc}-8& 1& -2\\ -3& -1& 7\\ 2& -6& -1\end{array}\right] R_2-\left(-3/-8\right)R_1,,,R_3-\left(2/-8\right)R_1\\ & \Rightarrow & \left[\begin{array}{ccc}-8& 1& -2\\ 0& -1.375& 7.750\\ 0& -5.750& -1.500\end{array}\right] R_2\leftrightarrow R_3..So, the -order-vector\left[\begin{array}{c}{b}_3\\ b_2\\ b_1\end{array}\right]\\ & \Rightarrow & \left[\begin{array}{ccc}-8& 1& -2\\ 0& -5.750& -1.500\\ 0& -1.375& 7.500\end{array}\right]R_{3-}\left(-1.375/-5.750\right)R_2\\ & \Rightarrow & U=\left[\begin{array}{ccc}-8& 1& -2\\ 0& -5.750& -1.500\\ 0& 0& 8.109\end{array}\right]\end{array}$

After pivoting, consider $L_{21}$ and $L_{31}$.

$\begin{array}{rcl}{L}_{13}& =& -3/-8 = 0.375\\ L_{12}& =& 2/-8 = -0.25\\ L_{32 }& =& \left(-1.375/-5.75\right)=0.2391\\ L & =& \left[\begin{array}{ccc}1& 0& 0\\ -0.25& 1& 0\\ 0.375& 0.2391& 1\end{array}\right]\end{array}$

To find the inverse's first column. Remember that the identity's first column is $\left[\begin{array}{c}1\\ 0\\ 0\end{array}\right]$. As a result, we're looking for $\left\{X\right\}$ something that will fulfill us.

$\left[A\right]\left[\begin{array}{c}{x}_1\\ x_2\\ x_3\end{array}\right]=\left[\begin{array}{c}1\\ 0\\ 0\end{array}\right]$

However, keep in mind that after performing the LU Decomposition with partial pivoting, the solution order is $\left[\begin{array}{c}{b}_3\\ b_1\\ b_2\end{array}\right]$.

As a result, we'd like to solve for $\left[\begin{array}{c}{b}_3=0\\ b_1=0\\ b_2=0\end{array}\right] that is \left[\begin{array}{c}0\\ 1\\ 0\end{array}\right]$ the vector $\left[L\right]\left\{D\right\}=\left\{B\right\}$.

$\begin{array}{rcl}\left[\begin{array}{ccc}1& 0& 0\\ -0.25& 1& 0\\ 0.375& 0.2391& 1\end{array}\right]\left[\begin{array}{c}{d}_1\\ d_2\\ d_3\end{array}\right]& =& \left[\begin{array}{c}0\\ 1\\ 0\end{array}\right]\Rightarrow \left\{D\right\}=\left[\begin{array}{c}0\\ 1\\ -0.2391\end{array}\right]\\ \left[U\right]\left\{X\right\}& =& \left\{D\right\}\\ \left[\begin{array}{ccc}-8& 1& -2\\ 0& -5.750& -1.500\\ 0& 0& 8.109\end{array}\right]\left[\begin{array}{c}{x}_1\\ x_2\\ x_3\end{array}\right]& =& \left[\begin{array}{c}0\\ 1\\ -0.2391\end{array}\right] By Backward substitution\\ & \Rightarrow & \left\{x\right\}=\left[\begin{array}{c}-0.0134\\ -0.1662\\ -0.0295\end{array}\right]\end{array}$

which is the first column of $A^{-1}$.

Full pivoting LU factorization

Full pivoting LU factorization is dependent upon row permutations as well as column permutations.

$PAQ = LU$

Here, a permutation matrix Q rearranges A's columns.

Common Mistakes

Students may be confused by the following questions regarding LU decomposition:

• Is LU decomposition always present in matrices?

No. It's not always possible to write a matrix in the "lower triangular" x "upper triangular" format.

• Which conditions prove that the LU decomposition is unique?

To achieve uniqueness, you must first ensure that L is a unit triangular (or that U is), which means that it contains all 1s on the diagonal and that A = LU is invertible. If the LU factorization exists, it is unique.

• Which matrices are not amenable to LU decomposition?

LU decomposition is not possible if the matrix loses a pivot while being changed to U through row reductions, and this cannot be repaired without a row shuffle operation.

Context and Applications

This topic is critical for the professional exams in both undergraduate and graduate courses, especially for:

• Bachelors in Computer Science.
• Masters in Computer Science.

Related Concepts

• LU decomposition applications.
• LU decomposition calculator.
• Gaussian elimination.

Practice Problems

Q1. Gaussian elimination in a matrix form is known as _______________.

1. LU decomposition
2. identity matrix
3. square matrix
4. vector matrix

Correct Answer: (1) LU decomposition

Explanation: LU decomposition is a more efficient approach to use Gaussian elimination, mainly when solving several equations with the same left-hand side.

Q2. LU decomposition is a factorization of _____________.

1. lower and upper triangular matrix
2. two vector matrices
3. vector matrix and lower triangular matrix
4. vector matrix and upper triangular matrix

Correct Answer: (1) lower and upper triangular matrix

Explanation: LU decomposition stands for Lower-Upper decomposition. LU decomposition is the factorization of the lower triangular matrix and an upper triangular matrix.

Q3. Which of these is a lower triangular matrix:

1. $\left[\begin{array}{ccc}{l}_{11}& l_{12}& l_{13}\\ 0& l_{22}& l_{23}\\ 0& 0& l_{33}\end{array}\right]$
2. $\left[\begin{array}{ccc}{l}_{11}& l_{12}& l_{13}\\ 0& l_{22}& l_{23}\\ 0& 0& 0\end{array}\right]$
3. $\left[\begin{array}{ccc}{l}_{11}& l_{12}& 0\\ 0& l_{22}& l_{23}\\ 0& 0& l_{33}\end{array}\right]$
4. $\left[\begin{array}{ccc}{l}_{11}& 0& 0\\ l_{21}& l_{22}& 0\\ l_{31}& l_{32}& l_{33}\end{array}\right]$

Correct Answer: (4)

$\left[\begin{array}{ccc}{l}_{11}& 0& 0\\ l_{21}& l_{22}& 0\\ l_{31}& l_{32}& l_{33}\end{array}\right]$

Explanation: In the lower triangular matrix, all components above the diagonal are zero.

Q4. Definition of LU decomposition is if A is a square matrix, a lower triangular matrix is L and an upper triangular matrix is U -____________.

1. $A = LU$
2. $L = AU$
3. $U = AU$
4. None

Correct Answer: (1) 

$A=LU$

Explanation: The two ingredients combine to form a LU. A lower triangular matrix is the first ingredient, and an upper triangular matrix is the second. The L is the identification of the lower triangular matrix and The upper triangular is represented by the U.

Q5. What does a permutation matrix property contain?

1. A square binary matrix with 1s in each row and column and 0s everywhere else is known as a permutation matrix.
2. A square binary matrix with 0s everywhere is known as a permutation matrix.
3. A square binary matrix with 1s everywhere is known as a permutation matrix.
4. None

Correct Answer: (1) A square binary matrix with 1s in each row and column and 0s everywhere else is known as a permutation matrix.

Explanation: A permutation matrix property contains 1s in each row and column and 0s everywhere.