LU Decomposition of a Matrix

Introduction

We present examples on how to find the LU decomposition of a matrix using the row operations .
Examples with detailed solutions are also included.
To obtain an LU decomposition, we use elementary matrices multiplication that are equivalent to row operations. However, interchanging rows is not allowed.


LU Decomposition of a Matrix

An LU decomposition of a given matrix A can be written as

A = LU

where L is a lower triangular matrix and U is an upper triangular matrix.
Conditions
An invertible matrix A has an LU decomposition if and only if all its leading principal minors are different from zero.
The kth order leading principal minor Mk is the determinant of the kth order principal submatrix formed by deleting the last n - k rows and the last n - k columns.
Example:
Let 4 by 4 Square Matrix
The 4 leading principal minors are
Principal Minors of a Matrix

\( \)\( \)\( \)

Elementary Matrices

An elementary matrix is a matrix that differs from the identity matrix by one single elementary operation.
Example of an elementary matrix: \( \begin{bmatrix} 1 & 0 & 0\\ 0 & 1 & 0 \\ - 3 & 0 & 1 \end{bmatrix} \) It differs from the identity \( \begin{bmatrix} 1 & 0 & 0\\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix} \) matrix by one element only and that is \( -3 \) .

Let us consider the \( 3 \) by \( 3 \) matrix \( A \) given by:
\( A = \begin{bmatrix} 1 & 0 & -2\\ 0 & -2 & 1 \\ 3 & 3 & 1 \end{bmatrix} \)

Let us add \( - 3 \) times row (1) to row (3) in the above matrix to obtain a new matrix \( B' \) given by.
\( B' = \begin{bmatrix} 1 & 0 & -2\\ 0 & -2 & 1 \\ 0 & 3 & 7 \end{bmatrix} \)

Another way of obtaining matrix \( B' \) from matrix \( A \) is to multiply matrix \( A \) by the elementary matrix \( E_1= \begin{bmatrix} 1 & 0 & 0\\ 0 & 1 & 0 \\ - 3 & 0 & 1 \end{bmatrix} \) which has been obtained from the identity matrix by adding \( - 3 \) times row (1) to row (3).

We can check that \( B' = E_1 A \) as follows
\( B' = \begin{bmatrix} 1 & 0 & -2\\ 0 & -2 & 1 \\ 0 & 3 & 7 \end{bmatrix} = \begin{bmatrix} 1 & 0 & 0\\ 0 & 1 & 0 \\ - 3 & 0 & 1 \end{bmatrix} \begin{bmatrix} 1 & 0 & -2\\ 0 & -2 & 1 \\ 3 & 3 & 1 \end{bmatrix} \)

In general adding \( k \) times row \( j (=3 \; \text{for example})\) to row \( m (=4 \; \text{for example})\) in a \( 4 \times 4 \) is equivalent to multiplying by an elementary matrix of the form: \[ E_1 = \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0\\ 0 & 0 & k & 1 \end{bmatrix} \]
which differs from the identity matrix by one elememnt at row \( m (=4)\) and column \( j (=3)\); it is \( k \) instead of zero.

One of the most important properties of elemetary matrices is their inverse. The inverse of the last matrix is simply \[ E_1^{-1} \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0\\ 0 & 0 & - k & 1 \end{bmatrix} \]
You do not change a matrix if you multiply it by the product \( \color{red}{E_1^{-1}} \color{blue}{E_1} \) since it is the identity matrix.

An online LU matrix decomposition calculator is included and may be used to check the solutions and answers below.


Examples with Solutions

Example 1
Find the \( LU \) composition of matrix \( A = \begin{bmatrix} 1 & -1 \\ 2 & -1 \end{bmatrix} \).

Solution to Example 1
The idea is to use multiplications by elementary matrices to rewrite the product on the right as a product of a lower triangular matrix (L) and an upper triangular matrix (U).
We proceed by transforming the given matrix into a upper triangualar matrix which has zeros below the diagonal.
In order to create a zero at the begining of row (2), we need to add \( -2 \) times row (1) to row (2) which is equivalent to multiplying by the elementary matrix \( \begin{bmatrix} 1 & 0 \\ -2 & 1 \end{bmatrix} \) and because we do not want to change matrix \( A \) we also need to multiply by the inverse of \( \begin{bmatrix} 1 & 0 \\ -2 & 1 \end{bmatrix} \).
hence
\( A = \begin{bmatrix} 1 & -1 \\ 2 & -1 \end{bmatrix} = \color{red}{ \begin{bmatrix} 1 & 0 \\ -2 & 1 \end{bmatrix} ^{-1}} \color{blue}{ \begin{bmatrix} 1 & 0 \\ -2 & 1 \end{bmatrix} } \begin{bmatrix} 1 & -1 \\ 2 & -1 \end{bmatrix} \)

The inverse of \( \begin{bmatrix} 1 & 0 \\ -2 & 1 \end{bmatrix} \) is easily given by \( \begin{bmatrix} 1 & 0 \\ 2 & 1 \end{bmatrix} \)

Simplify the above such that there is a lower and an upper triangular matrices
\( A = \begin{bmatrix} 1 & -1 \\ 2 & -1 \end{bmatrix} = \color{red}{ \begin{bmatrix} 1 & 0 \\ 2 & 1 \end{bmatrix} } \color{blue}{ \begin{bmatrix} 1 & 0 \\ -2 & 1 \end{bmatrix} } \begin{bmatrix} 1 & -1 \\ 2 & -1 \end{bmatrix} = \begin{bmatrix} 1 & 0 \\ 2 & 1 \end{bmatrix} \begin{bmatrix} 1 & -1 \\ 0 & 1 \end{bmatrix} \)

Matrix \( A \) is now written as the product of a lower matrix \( \begin{bmatrix} 1 & 0 \\ 2 & 1 \end{bmatrix} \) and an upper triangular matrix \( \begin{bmatrix} 1 & -1 \\ 0 & 1 \end{bmatrix} \).



Example 2
Find the \( LU \) composition of matrix \( A = \begin{bmatrix} -1 & -1 & 2\\ 2 & 0 & 3\\ -3 & 2 & -1 \end{bmatrix} \).

Solution to Example 2
We need to create a zero at column (1) row (2) by adding \( 2 \) times row (1) to row (2). Using elementary matrices we can write
\( A = \begin{bmatrix} -1 & -1 & 2\\ 2 & 0 & 3\\ -3 & 2 & -1 \end{bmatrix} = \color{red}{ \begin{bmatrix} 1 & 0 & 0\\ 2 & 1 & 0\\ 0 & 0 & 1 \end{bmatrix} ^{-1} } \color{blue}{ \begin{bmatrix} 1 & 0 & 0\\ 2 & 1 & 0\\ 0 & 0 & 1 \end{bmatrix} } \begin{bmatrix} -1 & -1 & 2\\ 2 & 0 & 3\\ -3 & 2 & -1 \end{bmatrix} \)

Simplify the above keeping the lower triangular matrix separate
\( A = \begin{bmatrix} -1 & -1 & 2\\ 2 & 0 & 3\\ -3 & 2 & -1 \end{bmatrix} = \color{red}{ \begin{bmatrix} 1 & 0 & 0\\ -2 & 1 & 0\\ 0 & 0 & 1 \end{bmatrix} } \begin{bmatrix} -1 & -1 & 2\\ 0 & -2 & 7\\ -3 & 2 & -1 \end{bmatrix} \)

We now need to create a zero at column (1) row (3) of the matrix on the right by adding \( - 3 \) times row (1) to row (3). Using elementary matrices, we write \( A = \begin{bmatrix} -1 & -1 & 2\\ 2 & 0 & 3\\ -3 & 2 & -1 \end{bmatrix} = \begin{bmatrix} 1 & 0 & 0\\ -2 & 1 & 0\\ 0 & 0 & 1 \end{bmatrix} \color{red}{ \begin{bmatrix} 1 & 0 & 0\\ 0 & 1 & 0\\ -3 & 0 & 1 \end{bmatrix} ^{-1} } \color{blue}{ \begin{bmatrix} 1 & 0 & 0\\ 0 & 1 & 0\\ -3 & 0 & 1 \end{bmatrix} } \begin{bmatrix} -1 & -1 & 2\\ 0 & -2 & 7\\ -3 & 2 & -1 \end{bmatrix} \)

Simplify keeping the lower triangular matrix separate
\( A = \begin{bmatrix} -1 & -1 & 2\\ 2 & 0 & 3\\ -3 & 2 & -1 \end{bmatrix} = \begin{bmatrix} 1 & 0 & 0\\ -2 & 1 & 0\\ 3 & 0 & 1 \end{bmatrix} \begin{bmatrix} -1 & -1 & 2\\ 0 & -2 & 7\\ 0 & 5 & -7 \end{bmatrix} \)

We now need to create a zero at column (2) row (3) of the matrix on the right by adding \( \dfrac{5}{2} \) times row (1) to row (3). Using elementary matrices, we write \( A = \begin{bmatrix} -1 & -1 & 2\\ 2 & 0 & 3\\ -3 & 2 & -1 \end{bmatrix} = \begin{bmatrix} 1 & 0 & 0\\ -2 & 1 & 0\\ 3 & 0 & 1 \end{bmatrix} \color{red}{ \begin{bmatrix} 1 & 0 & 0\\ 0 & 1 & 0\\ 0 & 5/2 & 1 \end{bmatrix}^{-1} } \color{blue}{ \begin{bmatrix} 1 & 0 & 0\\ 0 & 1 & 0\\ 0 & 5/2 & 1 \end{bmatrix} } \begin{bmatrix} -1 & -1 & 2\\ 0 & -2 & 7\\ 0 & 5 & -7 \end{bmatrix} \)

Simplify and keep lower and upper triangualar matrices
\( A = \begin{bmatrix} -1 & -1 & 2\\ 2 & 0 & 3\\ -3 & 2 & -1 \end{bmatrix} = \begin{bmatrix} 1 & 0 & 0\\ -2 & 1 & 0\\ 3 &-\frac{5}{2} & 1 \end{bmatrix} \begin{bmatrix} -1&-1&2\\ 0&-2&7\\ 0&0&\frac{21}{2} \end{bmatrix} \)

The given matrix has been written as the product of a lower and an upper triangular matrices.



Example 3
Find the \( LU \) composition of matrix \( A = \begin{bmatrix} -1 & -1 & -4 & -1\\ -2 & 0 & -4 & -4\\ 1 & -1 & 2 & 3 \\ 0 & 1 & 1 & -1 \end{bmatrix} \).

Solution to Example 3
We will combine row operations and hence reduce the steps.
1) Add \( \color{red}{- 2} \) times row (1) to row (2)
2) Add \( \color{red}{1} \) time row (1) to row (3)
\( A = \begin{bmatrix} -1 & -1 & -4 & -1\\ -2 & 0 & -4 & -4\\ 1 & -1 & 2 & 3 \\ 0 & 1 & 1 & -1 \end{bmatrix} = \begin{bmatrix} 1 & 0 & 0 & 0\\ \color{red}{2} & 1 & 0 & 0\\ \color{red}{-1} & 0 & 1 & 0\\ 0 & 0 & 0 & 1 \end{bmatrix} \begin{bmatrix} -1 & -1 & -4 & -1\\ 0 & 2 & 4 & -2\\ 0 & -2 & -2 & 2 \\ 0 & 1 & 1 & -1 \end{bmatrix} \)

1) Add \( \color{red}{1} \) times row (2) to row (3)
2) Add \( \color{red}{- 1/2} \) time row (2) to row (4)
\( A = \begin{bmatrix} -1 & -1 & -4 & -1\\ -2 & 0 & -4 & -4\\ 1 & -1 & 2 & 3 \\ 0 & 1 & 1 & -1 \end{bmatrix} = \begin{bmatrix} 1 & 0 & 0 & 0\\ 2 & 1 & 0 & 0\\ -1 & \color{red}{-1} & 1 & 0\\ 0 & \color{red}{1/2} & 0 & 1 \end{bmatrix} \begin{bmatrix} -1 & -1 & -4 & -1\\ 0 & 2 & 4 & -2\\ 0 & 0 & 2 & 0 \\ 0 & 0 & -1 & 0 \end{bmatrix} \)

1) Add \( \color{red}{1/2} \) times row (3) to row (4)
\( A = \begin{bmatrix} -1 & -1 & -4 & -1\\ -2 & 0 & -4 & -4\\ 1 & -1 & 2 & 3 \\ 0 & 1 & 1 & -1 \end{bmatrix} = \begin{bmatrix} 1 & 0 & 0 & 0\\ 2 & 1 & 0 & 0\\ -1 & -1 & 1 & 0\\ 0 & 1/2 & \color{red}{-1/2} & 1 \end{bmatrix} \begin{bmatrix} -1 & -1 & -4 & -1\\ 0 & 2 & 4 & -2\\ 0 & 0 & 2 & 0 \\ 0 & 0 & 0 & 0 \end{bmatrix} \)

The given matrix has been written as the product of a lower and an upper triangular matrices.



Example 4
Which of the following invertible matrices haven an LU decomposition?
a) \( \begin{bmatrix} 0 & -1\\ -1 & 2 & \end{bmatrix} \)   ,   b) \( \begin{bmatrix} -1 & -1 & -4 \\ -2 & 0 & -4 \\ 1 & -1 & 2 \end{bmatrix} \)   ,   c) \( \begin{bmatrix} 2 & 2 & 8 & 2\\ 0 & 2 & 4 & -2\\ 1 & 0 & 2 & 0 \\ 0 & 4 & -1 & 0 \end{bmatrix} \)

Solution to Example 4
a)
Calculate all principal minors.
\( M_1 = Det \begin{bmatrix} 0\\ \end{bmatrix} = 0 \) , \( M_2 = Det \begin{bmatrix} 0 & -1\\ -1 & 2 & \end{bmatrix} = -1 \)
The matrix is invertible and one of its leading principal minors is equal to zero, therefore the given matrix does not have an LU decomposition.

b)
\( M_1 = Det \begin{bmatrix} -1\\ \end{bmatrix} = -1 \) , \( M_2 = Det \begin{bmatrix} -1 & -1\\ -2 & 0& \end{bmatrix} = -2 \) , \( M_3 = Det \begin{bmatrix} -1 & -1 & -4 \\ -2 & 0 & -4 \\ 1 & -1 & 2 \end{bmatrix} = -4\)
The matrix is invertible and none of its leading principal minors is equal to zero, therefore the given matrix has an LU decomposition given by:
\( \begin{bmatrix} -1 & -1 & -4 \\ -2 & 0 & -4 \\ 1 & -1 & 2 \end{bmatrix} = \begin{bmatrix} 1 & 0 & 0 \\ 2 & 1 & 0 \\ -1 & -1 & 1 \end{bmatrix} \begin{bmatrix} -1 & -1 & -4 \\ 0 & 2 & 4 \\ 0 & 0 & 2 \end{bmatrix} \)

c)
\( M_1 = Det \begin{bmatrix} 2\\ \end{bmatrix} = 2 \) , \( M_2 = Det \begin{bmatrix} 2 & 2\\ 0 & 2& \end{bmatrix} = 4 \) , \( M_3 = Det \begin{bmatrix} 2& 2 & 8 \\ 0 & 2 & 4 \\ 1 & 0 & 2 \end{bmatrix} = 0\) , \( M_4 = Det \begin{bmatrix} 2 & 2 & 8 & 2\\ 0 & 2 & 4 & -2\\ 1 & 0 & 2 & 0 \\ 0 & 4 & -1 & 0 \end{bmatrix} = -72\)
The matrix is invertible and one of its leading principal minors is equal to zero, therefore the given matrix does not have an LU decomposition.


Questions with Answers

Find the LU decomposition, if any, of the matrices:
a) \( \begin{bmatrix} 3 & -1\\ -1 & 2 & \end{bmatrix} \)   ,   b) \( \begin{bmatrix} 2 & -1 & -1 \\ 1 & 2 & 0\\ 2 & -1 & 2 \end{bmatrix} \)   ,   c) \( \begin{bmatrix} -1 & 2 & 0 & 2\\ 2 & 2 & 0 & -2\\ 1 & 0 & -2 & 0 \\ 2 & 4 & -1 & 0 \end{bmatrix} \)
Answers
a)
\( \begin{bmatrix} 3 & -1\\ -1 & 2 & \end{bmatrix} = \begin{bmatrix} 1 & 0\\ -1/3 & 1 & \end{bmatrix} \begin{bmatrix} 3 & -1\\ 0 & 5/3 & \end{bmatrix} \)

b)
\( \begin{bmatrix} 2 & -1 & -1 \\ 1 & 2 & 0\\ 2 & -1 & 2 \end{bmatrix} = \begin{bmatrix} 1 & 0 & 0 \\ 1/2 & 1 & 0\\ 1 & 0 & 1 \end{bmatrix} \begin{bmatrix} 2 & -1 & -1 \\ 0 & 5/2 & 1/2\\ 0 & 0 & 3 \end{bmatrix} \)

c)
\( \begin{bmatrix} -1 & 2 & 0 & 2\\ 2 & 2 & 0 & -2\\ 1 & 0 & -2 & 0 \\ 2 & 4 & -1 & 0 \end{bmatrix} = \begin{bmatrix} 1 & 0 & 0 & 0\\ -2 & 1 & 0 & 0\\ -1 & 1/3 & 1 & 0 \\ -2 & 4/3 & 1/2 & 1 \end{bmatrix} \begin{bmatrix} -1 & 2 & 0 & 2\\ 0 & 6 & 0 & 2\\ 0 & 0 & -2 & 4/3 \\ 0 & 0 & 0 & 2/3 \end{bmatrix} \)



More References and links

  1. row operations
  2. Row Operations and Elementary Matrices
  3. Online LU Matrix Decomposition Calculator
  4. Triangular Matrices
  5. identity matrix
  6. Determinant of a Square Matrix
  7. matrix inverse
  8. linear algebra
  9. Find the Inverse of a Matrix Using Row Reduction - Calculator - Calculator
  10. Solve a system of linear equations by elimination
  11. elementary matrices
  12. Linear Algebra and its Applications - 5 th Edition - David C. Lay , Steven R. Lay , Judi J. McDonald
  13. Elementary Linear Algebra - 7 th Edition - Howard Anton and Chris Rorres