Problem of the week - LU decomposition

An LU decomposition (or factorization) of a matrix A is the product of a lower triangular matrix L and an upper triangular matrix U that is equal to A. One of the motivation for an LU decomposition is the fact that this decomposition can be used as an alternative method to solve systems of linear equations, where once the matrix of the system has been decomposed, the solution of the system can be obtained by solving two easy systems, one by the method of forward substitution and the other by the method of backward substitution. The LU decomposition is another approach designed to exploit triangular systems.

Although is very common to be asked to find an LU decomposition for a square matrix, the concepts are extended to rectangular matrices as well. In this problem of the week, you should deal with the LU decomposition for a rectangular matrix.

Given the matrix A:

┌              ┐
│ 3  -1  2  -3 │
│ 3  -2  3   0 │
│ 6  -4  7  -3 │
└              ┘

Find a lower triangular L and an upper triangular U so that A = LU.

Compute all the leading principal minors of the matrix A to verify if it has LU factorization, where all diagonal entries of U be non-zero. All leading principal minors must be non-zero.

│ 3 │ = 3

│ 3  -1 │
│ 3  -2 │ = 3•(-2) - (-1)•3 = -3

│ 3  -1  2 │
│ 3  -2  3 │ = 3•(-2)•7 + (-1)•3•6 + 3•(-4)•2 - 2•(-2)•6 - (-1)•3•7 - 3•(-4)•3 = -3
│ 6  -4  7 │

Place the Identity matrix to the right side of the matrix A.

┌                        ┐
│ 3  -1  2  -3 | 1  0  0 │
│ 3  -2  3   0 | 0  1  0 │
│ 6  -4  7  -3 | 0  0  1 │
└                        ┘

Transform the matrix A to row echelon form without using row operations of first kind (interchange two rows). Make the same operations to the Identity matrix.

r2 <———> r2 - r1
r3 <———> r3 - 2•r1
┌                         ┐
│ 3  -1  2  -3 |  1  0  0 │
│ 0  -1  1   3 | -1  1  0 │
│ 0  -2  3   3 | -2  0  1 │
└                         ┘
r3 <———> r3 - 2•r2
┌                          ┐
│ 3  -1  2  -3 |  1   0  0 │
│ 0  -1  1   3 | -1   1  0 │
│ 0   0  1  -3 |  0  -2  1 │
└                          ┘

The result of transforming A into row echelon form, is the upper triangular matrix U.

    ┌              ┐
    │ 3  -1  2  -3 │
U = │ 0  -1  1   3 │
    │ 0   0  1  -3 │
    └              ┘

Invert the resulting matrix at the right side. Let's do it using row operations, because the fact that this matrix is upper triangular, facilitates this step.

┌                     ┐
│  1   0  0 | 1  0  0 │
│ -1   1  0 | 0  1  0 │
│  0  -2  1 | 0  0  1 │
└                     ┘
r2 <———> r2 + r1
┌                    ┐
│ 1   0  0 | 1  0  0 │
│ 0   1  0 | 1  1  0 │
│ 0  -2  1 | 0  0  1 │
└                    ┘
r3 <———> r3 + 2•r2
┌                   ┐
│ 1  0  0 | 1  0  0 │
│ 0  1  0 | 1  1  0 │
│ 0  0  1 | 2  2  1 │
└                   ┘

The resulting matrix when computing the inverse is the lower triangular matrix L.

    ┌         ┐
    │ 1  0  0 │
L = │ 1  1  0 │
    │ 2  2  1 │
    └         ┘