[TOC]

`lu`

LU decomposition

Introduction

In the following, $\mathbb{K}$ is either $\mathbb{R}$ (real) or $\mathbb{C}$ (complex). If $A\in\mathbb{K}^{n\times n}$ is non-singular, there exists a unique decomposition

where $L\in\mathbb{K}^{n\times n}$ is a unit lower triangular matrix and $U\in\mathbb{K}^{n\times n}$ is an upper triangular matrix.

💡 A unit triangular matrix $A$ has all of its diagonal elements equal to 1, i.e., $A_{ii}=1$ .

Let $A\in\mathbb{K}^{m\times n}$ be a rectangular matrix and $r=\min\{m, n\}$ . If the first $r$ principle leading submatrices are nonsingular, there exists the decomposition

where $L\in\mathbb{K}^{m\times m}$ is a unit lower triangular matrix and $U\in\mathbb{K}^{m\times n}$ is an upper triangular matrix.

The matrix $A$ can be permuted before factorisation to improve stability. Let $P\in\mathbb{R}^{m\times m}$ be a given (real) permutation matrix. Then, it holds that

where $P'$ is the transpose of $P$ .

Usages

`Y = lu(A)`

`Y = lu(A, perm)`

A is a numeric (non-character) matrix, which can be real or complex.
The function call Y = lu(A) returns a matrix Y which has the same size as A. Elements on and above the main diagonal of Y are equal to the corresponding elements in $U$ of Equation (3) , and elements below the main diagonal of Y are equal to the corresponding elements in $L$ of Equation (3).
perm should be either 'vector' or 'matrix'. However, perm has not effect here and will be ignored. Hence, Y = lu(A, perm) and Y = lu(A) give the same results regardless of perm's value.

`[PtL, U] = lu(A)`

`[PtL, U] = lu(A, perm)`

A is a numeric (non-character) matrix, which can be real or complex.
It returns matrices PtL and U, which correspond to $P'L$ and $U$ in Equation (3), respectively. ( $P'L$ is sometimes called the permuted lower triangular matrix.)
As a result PtL * U == A.
perm should be either 'vector' or 'matrix'. However, perm has not effect here and will be ignored. Hence, [PtL, U] = lu(A, perm) and [PtL, U] = lu(A) give the same results regardless of perm's value.

`[L, U, P] = lu(A)`

`[L, U, P] = lu(A, 'matrix')`

`[L, U, e] = lu(A, 'vector')`

A is a numeric (non-character) matrix, which can be real or complex.
If 'matrix' is used, L, U and P correspond to matrices $L$ , $U$ and $P$ of Equation (3), respectively.
If 'vector' is used, e is a vector containing information about the permutation used in the decomposition. To convert e to a permutation matrix Q, we can do the following
```
Q = zeros(size(A,1));
for r = 1:size(A,1)
    Q(r,e(r)) = 1;
end
```
After the above conversion, L, U and Q correspond to $L$ , $U$ and $P$ in Equation (3), respectively.
[L,U,P] = lu(A) and [L,U,P] = lu(A,'matrix') give the same results.

Examples

Permutation matrix and permutation vector returned by lu.

Input

% Randomly generated matrix
a = randi(10,4,5);

% P contains permutation information
[L,U,e] = lu(a,'vector');

% Construct a permuation matrix Q using e
Q = zeros(size(a,1));
for r = 1:size(a,1)
    Q(r,e(r)) = 1;
end

% Permutation matrix T given by lu with type equal to 'matrix'
[L,U,T] = lu(a,'matrix');

% Permutation matrices Q and T are the same
Q
T

Output

Q =
 0.000   0.000   0.000   1.000
 1.000   0.000   0.000   0.000
 0.000   0.000   1.000   0.000
 0.000   1.000   0.000   0.000

T =
 0.000   0.000   0.000   1.000
 1.000   0.000   0.000   0.000
 0.000   0.000   1.000   0.000
 0.000   1.000   0.000   0.000

As seen from the example below, elements on and above the main diagonal of Y are equal to U, and elements below the main diagonal of Y are equal to L.

Input

A = randi(10,3,5);
[L,U,P] = lu(A);
Y = lu(A);
L
U
Y

Output

L =
 1.000   0.000   0.000
 0.700   1.000   0.000
 0.600  -0.235   1.000

U =
 10.00   7.000   6.000   5.000   8.000
 0.000   5.100   3.800   3.500  -0.600
 0.000   0.000  -0.706   6.824  -3.941

Y =
 10.00   7.000   6.000   5.000   8.000
 0.700   5.100   3.800   3.500  -0.600
 0.600  -0.235  -0.706   6.824  -3.941

LU decomposition of a random matrix.

Input

% Generate a random matrix
A = rand(6,4);

% LU decomposition
[L,U] = lu(A);

% L*U and A are (apprxoimately) identical
L*U-A

Output

ans = 1e-16 × 
 0.000   1.110   1.110   0.278
 1.110   0.000   0.000   0.000
 0.069   0.000   0.000  -0.278
 0.000  -0.278   0.000   0.000
 0.000   0.000   0.000   0.000
 0.000   0.555  -0.278   0.000