Triangular matrix

In mathematics, a triangular matrix is a special kind of square matrix. A square matrix is called ' if all the entries above the main diagonal are zero. Similarly, a square matrix is called ' if all the entries below the main diagonal are zero.
Because matrix equations with triangular matrices are easier to solve, they are very important in numerical analysis. By the LU decomposition algorithm, an invertible matrix may be written as the product of a lower triangular matrix L and an upper triangular matrix U if and only if all its leading principal minors are non-zero.

Description

A matrix of the form
is called a lower triangular matrix or left triangular matrix, and analogously a matrix of the form
is called an upper triangular matrix or right triangular matrix. A lower or left triangular matrix is commonly denoted with the variable L, and an upper or right triangular matrix is commonly denoted with the variable U or R.
A matrix that is both upper and lower triangular is diagonal. Matrices that are similar to triangular matrices are called triangularisable.
A non-square matrix with zeros above the diagonal is called a lower trapezoidal matrix. The non-zero entries form the shape of a trapezoid.

Examples

The matrix
is the lower triangular for the non symmetric matrix:
and
is the upper triangular for the non symmetric matrix:

Forward and back substitution

A matrix equation in the form or is very easy to solve by an iterative process called forward substitution for lower triangular matrices and analogously back substitution for upper triangular matrices. The process is so called because for lower triangular matrices, one first computes, then substitutes that forward into the next equation to solve for, and repeats through to. In an upper triangular matrix, one works backwards, first computing, then substituting that back into the previous equation to solve for, and repeating through.
Notice that this does not require inverting the matrix.

Forward substitution

The matrix equation Lx = b can be written as a system of linear equations
Observe that the first equation only involves, and thus one can solve for directly. The second equation only involves and, and thus can be solved once one substitutes in the already solved value for. Continuing in this way, the -th equation only involves, and one can solve for using the previously solved values for. The resulting formulas are:
A matrix equation with an upper triangular matrix U can be solved in an analogous way, only working backwards.

Applications

Forward substitution is used in financial bootstrapping to construct a yield curve.

Properties

The transpose of an upper triangular matrix is a lower triangular matrix and vice versa.
A matrix which is both symmetric and triangular is diagonal.
In a similar vein, a matrix which is both normal and triangular is also diagonal. This can be seen by looking at the diagonal entries of A^*A and AA^*.
The determinant and permanent of a triangular matrix equal the product of the diagonal entries, as can be checked by direct computation.
In fact more is true: the eigenvalues of a triangular matrix are exactly its diagonal entries. Moreover, each eigenvalue occurs exactly k times on the diagonal, where k is its algebraic multiplicity, that is, its multiplicity as a root of the characteristic polynomial of A. In other words, the characteristic polynomial of a triangular n×''n matrix A'' is exactly
that is, the unique degree n polynomial whose roots are the diagonal entries of A.
To see this, observe that is also triangular and hence its determinant is the product of its diagonal entries.

Special forms

Unitriangular matrix

If the entries on the main diagonal of a triangular matrix are all 1, the matrix is called unitriangular.
Other names used for these matrices are unit 'triangular, or very rarely normed triangular. However, a unit triangular matrix is not the same as the' ''unit matrix, and a normed'' triangular matrix has nothing to do with the notion of matrix norm.
All finite unitriangular matrices are unipotent.

Strictly triangular matrix

If all of the entries on the main diagonal of a triangular matrix are also 0, the matrix is called strictly 'triangular'.
All finite strictly triangular matrices are nilpotent of index at most n as a consequence of the Cayley–Hamilton theorem.

Atomic triangular matrix

An atomic 'triangular matrix is a special form of unitriangular matrix, where all of the off-diagonal elements are zero, except for the entries in a single column. Such a matrix is also called a Frobenius matrix, a Gauss matrix, or a Gauss transformation matrix'.

Block triangular matrix

A block triangular matrix is a block matrix that is a triangular matrix.

Upper block triangular

A matrix is upper block triangular if
where for all.

Lower block triangular

A matrix is lower block triangular if
where for all.

Triangularisability

A matrix that is similar to a triangular matrix is referred to as triangularizable. Abstractly, this is equivalent to stabilizing a flag: upper triangular matrices are precisely those that preserve the standard flag, which is given by the standard ordered basis and the resulting flag All flags are conjugate, so any matrix that stabilises a flag is similar to one that stabilizes the standard flag.
Any complex square matrix is triangularizable. In fact, a matrix A over a field containing all of the eigenvalues of A is similar to a triangular matrix. This can be proven by using induction on the fact that A has an eigenvector, by taking the quotient space by the eigenvector and inducting to show that A stabilizes a flag, and is thus triangularizable with respect to a basis for that flag.
A more precise statement is given by the Jordan normal form theorem, which states that in this situation, A is similar to an upper triangular matrix of a very particular form. The simpler triangularization result is often sufficient however, and in any case used in proving the Jordan normal form theorem.
In the case of complex matrices, it is possible to say more about triangularization, namely, that any square matrix A has a Schur decomposition. This means that A is unitarily equivalent to an upper triangular matrix; this follows by taking an Hermitian basis for the flag.

Simultaneous triangularisability

A set of matrices are said to be if there is a basis under which they are all upper triangular; equivalently, if they are upper triangularizable by a single similarity matrix P. Such a set of matrices is more easily understood by considering the algebra of matrices it generates, namely all polynomials in the denoted Simultaneous triangularizability means that this algebra is conjugate into the Lie subalgebra of upper triangular matrices, and is equivalent to this algebra being a Lie subalgebra of a Borel subalgebra.
The basic result is that, the commuting matrices or more generally are simultaneously triangularizable. This can be proven by first showing that commuting matrices have a common eigenvector, and then inducting on dimension as before. This was proven by Frobenius, starting in 1878 for a commuting pair, as discussed at commuting matrices. As for a single matrix, over the complex numbers these can be triangularized by unitary matrices.
The fact that commuting matrices have a common eigenvector can be interpreted as a result of Hilbert's Nullstellensatz: commuting matrices form a commutative algebra over which can be interpreted as a variety in k-dimensional affine space, and the existence of a eigenvalue corresponds to this variety having a point, which is the content of the Nullstellensatz. In algebraic terms, these operators correspond to an algebra representation of the polynomial algebra in k variables.
This is generalized by Lie's theorem, which shows that any representation of a solvable Lie algebra is simultaneously upper triangularizable, the case of commuting matrices being the abelian Lie algebra case, abelian being a fortiori solvable.
More generally and precisely, a set of matrices is simultaneously triangularisable if and only if the matrix is nilpotent for all polynomials p in k ''non-commuting variables, where is the commutator; for commuting the commutator vanishes so this holds. This was proven by Drazin, Dungey, and Gruenberg in 1951; a brief proof is given by Prasolov in 1994. One direction is clear: if the matrices are simultaneously triangularisable, then is strictly'' upper triangularizable, which is preserved by multiplication by any or combination thereof – it will still have 0s on the diagonal in the triangularizing basis.

Algebras of triangular matrices

Upper triangularity is preserved by many operations:

The sum of two upper triangular matrices is upper triangular.
The product of two upper triangular matrices is upper triangular.
The inverse of an upper triangular matrix, if it exists, is upper triangular.
The product of an upper triangular matrix and a scalar is upper triangular.

Together these facts mean that the upper triangular matrices form a subalgebra of the associative algebra of square matrices for a given size. Additionally, this also shows that the upper triangular matrices can be viewed as a Lie subalgebra of the Lie algebra of square matrices of a fixed size, where the Lie bracket given by the commutator. The Lie algebra of all upper triangular matrices is a solvable Lie algebra. It is often referred to as a Borel subalgebra of the Lie algebra of all square matrices.
All these results hold if upper triangular is replaced by lower triangular throughout; in particular the lower triangular matrices also form a Lie algebra. However, operations mixing upper and lower triangular matrices do not in general produce triangular matrices. For instance, the sum of an upper and a lower triangular matrix can be any matrix; the product of a lower triangular with an upper triangular matrix is not necessarily triangular either.
The set of unitriangular matrices forms a Lie group.
The set of strictly upper triangular matrices forms a nilpotent Lie algebra, denoted This algebra is the derived Lie algebra of, the Lie algebra of all upper triangular matrices; in symbols, In addition, is the Lie algebra of the Lie group of unitriangular matrices.
In fact, by Engel's theorem, any finite-dimensional nilpotent Lie algebra is conjugate to a subalgebra of the strictly upper triangular matrices, that is to say, a finite-dimensional nilpotent Lie algebra is simultaneously strictly upper triangularizable.
Algebras of upper triangular matrices have a natural generalization in functional analysis which yields nest algebras on Hilbert spaces.