Wolfram Function Repository

Instant-use add-on functions for the Wolfram Language

Function Repository Resource:

 UpperTriangularDecomposition

Source Notebook

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

Contributed by: Daniel Lichtblau

ResourceFunction["UpperTriangularDecomposition"][mat]

gives an upper triangular matrix u and a corresponding conversion matrix c.

Details and Options

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.
With "EchelonForm"→True the matrix u is the same as that given by RowReduce[mat].
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.

Examples

Basic Examples (2) 

Compute the upper triangular decomposition of a matrix:

In[1]:=
mat = {{1, 2}, {3, 4}}; {u, c} = ResourceFunction["UpperTriangularDecomposition"][mat]
Out[2]=

Check the result:

In[3]:=
c . mat == u
Out[3]=

Scope (3) 

Input can be symbolic:

In[4]:=
ResourceFunction["UpperTriangularDecomposition"][{{a, b}, {c, d}}]
Out[4]=

The input need not be square:

In[5]:=
ResourceFunction[ "UpperTriangularDecomposition"][{{1, 2, 3}, {4, 5, 6}}]
Out[5]=

Input can be a sparse or structured array:

In[6]:=
cm = CauchyMatrix[{1, 2, 3}, {1, 5, 6}]; ResourceFunction["UpperTriangularDecomposition"][cm] == ResourceFunction["UpperTriangularDecomposition"][Normal@cm] == ResourceFunction["UpperTriangularDecomposition"][SparseArray@cm]
Out[7]=

Options (2) 

Create a random integer matrix:

In[8]:=
SeedRandom[1234]; mat = RandomInteger[{-10, 10}, {4, 6}]
Out[9]=

Compute the upper triangular decomposition:

In[10]:=
ResourceFunction["UpperTriangularDecomposition"][mat]
Out[10]=

Now compute an upper triangular decomposition modulo a prime:

In[11]:=
ResourceFunction["UpperTriangularDecomposition"][mat, Modulus -> 29]
Out[11]=

Create a random integer matrix:

In[12]:=
SeedRandom[1234]; mat = RandomInteger[{-10, 10}, {4, 6}]
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]:=
{rred, c} = ResourceFunction["UpperTriangularDecomposition"][mat, "EchelonForm" -> True]
Out[14]=

Check the result:

In[15]:=
c . mat == rred
Out[15]=

Properties and Relations (13) 

Create a symmetric positive definite matrix:

In[16]:=
SeedRandom[1234]; mat0 = RandomInteger[{-10, 10}, {6, 6}]; mat = mat0 + Transpose[mat0] + 80*IdentityMatrix[6]
Out[17]=

Check that it is actually positive definite:

In[18]:=
PositiveDefiniteMatrixQ[mat]
Out[18]=

Compute the upper triangular decomposition:

In[19]:=
{u, c} = ResourceFunction["UpperTriangularDecomposition"][mat]
Out[19]=

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

In[20]:=
Inverse[c] . u == mat
Out[20]=

We can get a different upper triangular factorization using CholeskyDecomposition:

In[21]:=
ch = CholeskyDecomposition[mat]
Out[21]=

Check the result:

In[22]:=
Transpose[ch] . ch == mat
Out[22]=

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

In[23]:=
{q, r} = QRDecomposition[mat]; Short /@ {q, r}
Out[24]=

Check the result:

In[25]:=
Expand[q . mat] == r
Out[25]=

We get yet another triangular factorization of mat using LUDecomposition:

In[26]:=
{lu, perm, cond} = LUDecomposition[mat]
Out[26]=

Recover the two triangular factors:

In[27]:=
getL[mat_] := With[{r = Length[mat]}, PadRight[LowerTriangularize[mat, -1], {r, r}, 0] + IdentityMatrix[r]] {l, u} = {getL[lu], UpperTriangularize[lu]}
Out[28]=

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

In[29]:=
l . u == mat[[perm]]
Out[29]=

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

In[30]:=
c = Inverse[l] . PermutationMatrix[perm]
Out[30]=

Check this:

In[31]:=
c . mat == u
Out[31]=

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

Possible Issues (2) 

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

In[32]:=
mat = {{1, 2}, {3, 4}}; ResourceFunction["UpperTriangularDecomposition"][N@mat]
Out[33]=

This is different from the exact case:

In[34]:=
ResourceFunction["UpperTriangularDecomposition"][mat]
Out[34]=

Requirements

Wolfram Language 13.0 (December 2021) or above

Version History

  • 1.0.0 – 14 June 2024

Source Metadata

Related Resources

License Information