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
Numerical analysis is the study of algorithms that use numerical approximation (as opposed to symbolic manipulations) for the problems of mathematical analysis (as distinguished from discrete mathematics). It is the study of numerical methods t ...
. By the
LU decomposition algorithm, an
invertible matrix
In linear algebra, an -by- square matrix is called invertible (also nonsingular or nondegenerate), if there exists an -by- square matrix such that
:\mathbf = \mathbf = \mathbf_n \
where denotes the -by- identity matrix and the multiplicati ...
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 (or sometimes any) matrix with zeros above (below) the diagonal is called a lower (upper) trapezoidal matrix. The non-zero entries form the shape of a
trapezoid.
Examples
This matrix
:
is upper triangular and this matrix
:
is lower triangular.
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 ''L''x = 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
In general, bootstrapping usually refers to a self-starting process that is supposed to continue or grow without external input.
Etymology
Tall boots may have a tab, loop or handle at the top known as a bootstrap, allowing one to use fingers ...
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 (meaning ''A''
*''A'' = ''AA''
*, where ''A''
* is the
conjugate transpose
In mathematics, the conjugate transpose, also known as the Hermitian transpose, of an m \times n complex matrix \boldsymbol is an n \times m matrix obtained by transposing \boldsymbol and applying complex conjugate on each entry (the complex c ...
) 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
eigenvalue
In linear algebra, an eigenvector () or characteristic vector of a linear transformation is a nonzero vector that changes at most by a scalar factor when that linear transformation is applied to it. The corresponding eigenvalue, often denoted ...
s 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
In linear algebra, an eigenvector () or characteristic vector of a linear transformation is a nonzero vector that changes at most by a scalar factor when that linear transformation is applied to it. The corresponding eigenvalue, often denoted b ...
, that is, its
multiplicity as a root of the
characteristic polynomial
In linear algebra, the characteristic polynomial of a square matrix is a polynomial which is invariant under matrix similarity and has the eigenvalues as roots. It has the determinant and the trace of the matrix among its coefficients. The char ...
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'' (with multiplicities).
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 (upper or lower) triangular matrix are all 1, the matrix is called (upper or lower) unitriangular.
Other names used for these matrices are unit (upper or lower) triangular, or very rarely normed (upper or lower) triangular. However, a ''unit'' triangular matrix is not the same as the ''
unit matrix
In linear algebra, the identity matrix of size n is the n\times n square matrix with ones on the main diagonal and zeros elsewhere.
Terminology and notation
The identity matrix is often denoted by I_n, or simply by I if the size is immaterial or ...
'', 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 (upper or lower) triangular matrix are also 0, the matrix is called strictly (upper or lower) triangular.
All finite strictly triangular matrices are
nilpotent
In mathematics, an element x of a ring R is called nilpotent if there exists some positive integer n, called the index (or sometimes the degree), such that x^n=0.
The term was introduced by Benjamin Peirce in the context of his work on the cla ...
of index at most ''n'' as a consequence of the
Cayley-Hamilton theorem.
Atomic triangular matrix
An atomic (upper or lower) triangular matrix is a special form of unitriangular matrix, where all of the
off-diagonal element
In geometry, a diagonal is a line segment joining two vertices of a polygon or polyhedron, when those vertices are not on the same edge. Informally, any sloping line is called diagonal. The word ''diagonal'' derives from the ancient Greek δ ...
s 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.
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 (as the general linear group acts transitively on bases), 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
Field may refer to:
Expanses of open ground
* Field (agriculture), an area of land used for agricultural purposes
* Airfield, an aerodrome that lacks the infrastructure of an airport
* Battlefield
* Lawn, an area of mowed grass
* Meadow, a grass ...
containing all of the eigenvalues of ''A'' (for example, any matrix over an
algebraically closed field
In mathematics, a field is algebraically closed if every non-constant polynomial in (the univariate polynomial ring with coefficients in ) has a root in .
Examples
As an example, the field of real numbers is not algebraically closed, because ...
) 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 (i.e. similar, using a
unitary matrix
In linear algebra, a complex square matrix is unitary if its conjugate transpose is also its inverse, that is, if
U^* U = UU^* = UU^ = I,
where is the identity matrix.
In physics, especially in quantum mechanics, the conjugate transpose ...
as change of basis) 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 (over an algebraically closed field), the
commuting matrices In linear algebra, two matrices A and B are said to commute if AB=BA, or equivalently if their commutator ,B AB-BA is zero. A set of matrices A_1, \ldots, A_k is said to commute if they commute pairwise, meaning that every pair of matrices in the ...
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 In linear algebra, two matrices A and B are said to commute if AB=BA, or equivalently if their commutator ,B AB-BA is zero. A set of matrices A_1, \ldots, A_k is said to commute if they commute pairwise, meaning that every pair of matrices in the ...
. 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