Compute LU Factorization

The LU factorization expresses an m×n matrix A as follows: P*A = L*U. Here L is an m×m lower triangular matrix that contains 1s on the main diagonal, U is an m×n matrix upper triangular matrix, and P is a permutation matrix. To compute the LU decomposition of a matrix, use the linalg::factorLU function. For example, compute the LU decomposition of the following square matrix:

A := matrix([[0, 0, 1], [1, 2, 3], [0, 1, 2]]):
[L, U, p] := linalg::factorLU(A)

Instead of returning the permutation matrix P, MuPAD® returns the list p with numbers corresponding to row exchanges in the matrix A. For an n×n matrix, the list p represents the following permutation matrix with indices i and j ranging from 1 to n:

.

Using this expression, restore the permutation matrix P from the list p:

P := matrix(3, 3):
for i from 1 to 3 do
   P[i, p[i]] := 1
end_for:
P

More efficiently, compute the result of applying the permutation matrix to A without restoring the permutation matrix itself:

PA := matrix(3, 3):
for i from 1 to 3 do
  PA[i, 1..3] := A[p[i], 1..3]
end_for:
PA

The product of the lower triangular matrix L and the upper triangular matrix U is the original matrix A with the rows interchanged according to the permutation matrix P:

testeq(PA = L*U)

Now, compute the LU decomposition for the 3 ×2 matrix B:

B := matrix([[1, 2], [3, 4], [5, 6]]):
[L, U, p] := linalg::factorLU(B)

The permutation matrix for this LU factorization shows that the order of the rows does not change. Therefore, the product of the lower triangular matrix L and the upper triangular matrix U gives the original matrix A:

testeq(B = L*U)

Was this topic helpful?