# Wolfram Function Repository

Instant-use add-on functions for the Wolfram Language

Function Repository Resource:

Find an upper triangular form and conversion matrix for a given matrix

Contributed by:
Daniel Lichtblau

ResourceFunction["UpperTriangularDecomposition"][ gives an upper triangular matrix |

The result is given in the form {*u*,*c*} where *u* is an upper triangular matrix, *c* is a square matrix with same number of rows as *mat*, and *c*.*mat*==*u*.

ResourceFunction["UpperTriangularDecomposition"] takes an option "EchelonForm" (default False). When set to True, the resulting matrix *u* will be the reduced echelon form of *mat*.

With "EchelonForm"→True all elements in pivot positions will be normalized to 1 using division, and t. With the default setting of "EchelonForm"→False these divisions do not take place. In this case if the input does not contain fractions then neither will the resulting matrices.

Matrices comprised of approximate numbers will always give the full echelon form, regardless of the option setting.

The matrix *c* in effect records the operations required to go from the input *mat* to the upper triangular form *u*.

When there are no symbolic parameters present in *mat*, the conversion matrix *c* is guaranteed to be invertible, so we also have the identity Inverse[*c*].*u*==*mat*. This is a particular type of factorization of *mat*.

Like RowReduce, ResourceFunction["UpperTriangularDecomposition"] takes a Modulus option (default 0).

One use case for the triangular rather than echelon form arises when a matrix has symbolic parameters. One might wish to find relations for which a matrix pivot will vanish.

Another is that this matrix factorization will most often avoid producing fractions or radicals when none were present in the input. This is in contrast to LUDecomposition, CholeskyDecomposition and QRDecomposition.

Compute the upper triangular decomposition of a matrix:

In[1]:= |

Out[2]= |

Check the result:

In[3]:= |

Out[3]= |

Input can be symbolic:

In[4]:= |

Out[4]= |

The input need not be square:

In[5]:= |

Out[5]= |

Input can be a sparse or structured array:

In[6]:= |

Out[7]= |

Create a random integer matrix:

In[8]:= |

Out[9]= |

Compute the upper triangular decomposition:

In[10]:= |

Out[10]= |

Now compute an upper triangular decomposition modulo a prime:

In[11]:= |

Out[11]= |

Create a random integer matrix:

In[12]:= |

Out[13]= |

Compute the full row echelon decomposition {*rred*,*c*} such that *rred* is in reduced row echelon form and *c*.*mat*==*rred*:

In[14]:= |

Out[14]= |

Check the result:

In[15]:= |

Out[15]= |

Create a symmetric positive definite matrix:

In[16]:= |

Out[17]= |

Check that it is actually positive definite:

In[18]:= |

Out[18]= |

Compute the upper triangular decomposition:

In[19]:= |

Out[19]= |

Check that the decomposition is correct, now using the inverse of *c* and multiplying by *u* to recover *mat*:

In[20]:= |

Out[20]= |

We can get a different upper triangular factorization using CholeskyDecomposition:

In[21]:= |

Out[21]= |

Check the result:

In[22]:= |

Out[22]= |

Another factorization with an upper triangular factor is obtained using QRDecomposition:

In[23]:= |

Out[24]= |

Check the result:

In[25]:= |

Out[25]= |

We get yet another triangular factorization of *mat* using LUDecomposition:

In[26]:= |

Out[26]= |

Recover the two triangular factors:

In[27]:= |

Out[28]= |

Check that the product of these factors gives *mat* transformed by the permutation *perm* used by LUDecomposition:

In[29]:= |

Out[29]= |

Use the permutation and lower factor to find the conversion matrix for an upper triangular decomposition:

In[30]:= |

Out[30]= |

Check this:

In[31]:= |

Out[31]= |

One will notice that of all these factorizations, only UpperTriangularizeMatrix avoids both fractions and radicals.

If the input matrix is approximate the full echelon form will be computed:

In[32]:= |

Out[33]= |

This is different from the exact case:

In[34]:= |

Out[34]= |

Wolfram Language 13.0 (December 2021) or above

- 1.0.1 – 16 September 2024
- 1.0.0 – 14 June 2024

This work is licensed under a Creative Commons Attribution 4.0 International License