In mathematics, a triangular matrix is a special kind of
square matrix
In mathematics, a square matrix is a Matrix (mathematics), matrix with the same number of rows and columns. An ''n''-by-''n'' matrix is known as a square matrix of order Any two square matrices of the same order can be added and multiplied.
Squ ...
. A square matrix is called if all the entries ''above'' the
main diagonal
In linear algebra, the main diagonal (sometimes principal diagonal, primary diagonal, leading diagonal, major diagonal, or good diagonal) of a matrix A is the list of entries a_ where i = j. All off-diagonal elements are zero in a diagonal matrix ...
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 computation, symbolic manipulations) for the problems of mathematical analysis (as distinguished from discrete mathematics). It is the study of ...
. By the
LU decomposition
In numerical analysis and linear algebra, lower–upper (LU) decomposition or factorization factors a matrix as the product of a lower triangular matrix and an upper triangular matrix (see matrix multiplication and matrix decomposition). The produ ...
algorithm, an
invertible matrix
In linear algebra, an invertible matrix (''non-singular'', ''non-degenarate'' or ''regular'') is a square matrix that has an inverse. In other words, if some other matrix is multiplied by the invertible matrix, the result can be multiplied by a ...
may be written as the
product of a lower triangular matrix ''L'' and an upper triangular matrix ''U''
if and only if
In logic and related fields such as mathematics and philosophy, "if and only if" (often shortened as "iff") is paraphrased by the biconditional, a logical connective between statements. The biconditional is true in two cases, where either bo ...
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
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 � ...
. 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
In geometry, a trapezoid () in North American English, or trapezium () in British English, is a quadrilateral that has at least one pair of parallel sides.
The parallel sides are called the ''bases'' of the trapezoid. The other two sides are ...
.
Examples
The matrix
:
is lower triangular, and
:
is upper 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. Many analytical techniques are often called bootstrap methods in reference to their self-starting or self-supporting ...
to construct a
yield curve
In finance, the yield curve is a graph which depicts how the Yield to maturity, yields on debt instruments – such as bonds – vary as a function of their years remaining to Maturity (finance), maturity. Typically, the graph's horizontal ...
.
Properties
The
transpose
In linear algebra, the transpose of a Matrix (mathematics), matrix is an operator which flips a matrix over its diagonal;
that is, it switches the row and column indices of the matrix by producing another matrix, often denoted by (among other ...
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 \mathbf is an n \times m matrix obtained by transposing \mathbf and applying complex conjugation to each entry (the complex conjugate ...
) and triangular is also diagonal. This can be seen by looking at the diagonal entries of ''A''
*''A'' and ''AA''
*.
The
determinant
In mathematics, the determinant is a Scalar (mathematics), scalar-valued function (mathematics), function of the entries of a square matrix. The determinant of a matrix is commonly denoted , , or . Its value characterizes some properties of the ...
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 is a vector that has its direction unchanged (or reversed) by a given linear transformation. More precisely, an eigenvector \mathbf v of a linear transformation T is scaled by a ...
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, 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 ...
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
In linear algebra, the main diagonal (sometimes principal diagonal, primary diagonal, leading diagonal, major diagonal, or good diagonal) of a matrix A is the list of entries a_ where i = j. All off-diagonal elements are zero in a diagonal matrix ...
of a (lower or upper) triangular matrix are all 1, the matrix is called (lower or upper) unitriangular.
Other names used for these matrices are unit (lower or upper) triangular, or very rarely normed (lower or upper) 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. It has unique properties, for example when the identity matrix represents a geometric transformation, the obje ...
'', and a ''normed'' triangular matrix has nothing to do with the notion of
matrix norm
In the field of mathematics, norms are defined for elements within a vector space. Specifically, when the vector space comprises matrices, such norms are referred to as matrix norms. Matrix norms differ from vector norms in that they must also ...
.
All finite unitriangular matrices are
unipotent
In mathematics, a unipotent element ''r'' of a ring ''R'' is one such that ''r'' − 1 is a nilpotent element; in other words, (''r'' − 1)''n'' is zero for some ''n''.
In particular, a square matrix ''M'' is a unipote ...
.
Strictly triangular matrix
If all of the entries on the main diagonal of a (lower or upper) triangular matrix are also 0, the matrix is called strictly (lower or upper) triangular.
All finite strictly triangular matrices are
nilpotent
In mathematics, an element x of a ring (mathematics), 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, along with its sister Idempotent (ring theory), idem ...
of index at most ''n'' as a consequence of the
Cayley-Hamilton theorem.
Atomic triangular matrix
An atomic (lower or upper) 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
In mathematics, a block matrix or a partitioned matrix is a matrix that is interpreted as having been broken into sections called blocks or submatrices.
Intuitively, a matrix interpreted as a block matrix can be visualized as the original matrix w ...
(partitioned 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
A flag is a piece of textile, fabric (most often rectangular) with distinctive colours and design. It is used as a symbol, a signalling device, or for decoration. The term ''flag'' is also used to refer to the graphic design employed, and fla ...
: upper triangular matrices are precisely those that preserve the standard flag
In mathematics, particularly in linear algebra, a flag is an increasing sequence of subspaces of a finite-dimensional vector space ''V''. Here "increasing" means each is a proper subspace of the next (see filtration):
:\ = V_0 \sub V_1 \sub V_2 \s ...
, which is given by the standard ordered basis and the resulting flag All flags are conjugate (as the general linear group
In mathematics, the general linear group of degree n is the set of n\times n invertible matrices, together with the operation of ordinary matrix multiplication. This forms a group, because the product of two invertible matrices is again inve ...
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 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 . In other words, a field is algebraically closed if the fundamental theorem of algebra ...
) 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
\begin
\lambda_1 1\hphantom\hphantom\\
\hphantom\lambda_1 1\hphantom\\
\hphantom\lambda_1\hphantom\\
\hphantom\lambda_2 1\hphantom\hphantom\\
\hphantom\hphantom\lambda_2\hphantom\\
\hphantom\lambda_3\hphantom\\
\hphantom\ddots\hphantom\\
...
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
In the mathematical discipline of linear algebra, the Schur decomposition or Schur triangulation, named after Issai Schur, is a matrix decomposition. It allows one to write an arbitrary complex square matrix as unitarily similar to an upper tria ...
. This means that ''A'' is unitarily equivalent (i.e. similar, using a unitary matrix 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. Matrices A that commute with matrix B are called the commutant of matrix B (and vice versa).
A set of matrices A_1, \ldot ...
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. Matrices A that commute with matrix B are called the commutant of matrix B (and vice versa).
A set of matrices A_1, \ldot ...
. 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
In mathematics, Hilbert's Nullstellensatz (German for "theorem of zeros", or more literally, "zero-locus-theorem") is a theorem that establishes a fundamental relationship between geometry and algebra. This relationship is the basis of algebraic ge ...
: commuting matrices form a commutative algebra Lie's theorem In mathematics, specifically the theory of Lie algebras, Lie's theorem states that, over an algebraically closed field of characteristic zero, if \pi: \mathfrak \to \mathfrak(V) is a finite-dimensional representation of a solvable Lie algebra, then ...
, which shows that any representation of a solvable Lie algebra
In mathematics, a Lie algebra \mathfrak is solvable if its derived series terminates in the zero subalgebra. The ''derived Lie algebra'' of the Lie algebra \mathfrak is the subalgebra of \mathfrak, denoted
: mathfrak,\mathfrak/math>
that consist ...
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 A_1,\ldots,A_k is simultaneously triangularisable if and only if the matrix p(A_1,\ldots,A_k) _i,A_j/math> is nilpotent
In mathematics, an element x of a ring (mathematics), 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, along with its sister Idempotent (ring theory), idem ...
for all polynomials ''p'' in ''k'' ''non''-commuting variables, where _i,A_j/math> is the commutator
In mathematics, the commutator gives an indication of the extent to which a certain binary operation fails to be commutative. There are different definitions used in group theory and ring theory.
Group theory
The commutator of two elements, ...
; for commuting A_i 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 _i, A_j/math> is ''strictly'' upper triangularizable (hence nilpotent), which is preserved by multiplication by any A_k 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 In mathematics, a subalgebra is a subset of an algebra, closed under all its operations, and carrying the induced operations.
"Algebra", when referring to a structure, often means a vector space or module equipped with an additional bilinear opera ...
of the associative algebra
In mathematics, an associative algebra ''A'' over a commutative ring (often a field) ''K'' is a ring ''A'' together with a ring homomorphism from ''K'' into the center of ''A''. This is thus an algebraic structure with an addition, a mult ...
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
In mathematics, a Lie algebra (pronounced ) is a vector space \mathfrak g together with an operation called the Lie bracket, an alternating bilinear map \mathfrak g \times \mathfrak g \rightarrow \mathfrak g, that satisfies the Jacobi ident ...
of square matrices of a fixed size, where the Lie bracket
In mathematics, a Lie algebra (pronounced ) is a vector space \mathfrak g together with an operation called the Lie bracket, an alternating bilinear map \mathfrak g \times \mathfrak g \rightarrow \mathfrak g, that satisfies the Jacobi identit ...
'a'', ''b''given by the commutator
In mathematics, the commutator gives an indication of the extent to which a certain binary operation fails to be commutative. There are different definitions used in group theory and ring theory.
Group theory
The commutator of two elements, ...
. The Lie algebra of all upper triangular matrices is a solvable Lie algebra
In mathematics, a Lie algebra \mathfrak is solvable if its derived series terminates in the zero subalgebra. The ''derived Lie algebra'' of the Lie algebra \mathfrak is the subalgebra of \mathfrak, denoted
: mathfrak,\mathfrak/math>
that consist ...
. 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
In mathematics, a Lie group (pronounced ) is a group (mathematics), group that is also a differentiable manifold, such that group multiplication and taking inverses are both differentiable.
A manifold is a space that locally resembles Eucli ...
.
The set of strictly upper (or lower) triangular matrices forms a nilpotent Lie algebra, denoted \mathfrak. This algebra is the derived Lie algebra of \mathfrak, the Lie algebra of all upper triangular matrices; in symbols, \mathfrak = mathfrak,\mathfrak In addition, \mathfrak 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
Functional analysis is a branch of mathematical analysis, the core of which is formed by the study of vector spaces endowed with some kind of limit-related structure (for example, Inner product space#Definition, inner product, Norm (mathematics ...
which yields nest algebras on Hilbert space
In mathematics, a Hilbert space is a real number, real or complex number, complex inner product space that is also a complete metric space with respect to the metric induced by the inner product. It generalizes the notion of Euclidean space. The ...
s.
Borel subgroups and Borel subalgebras
The set of invertible triangular matrices of a given kind (lower or upper) forms a group, indeed a Lie group
In mathematics, a Lie group (pronounced ) is a group (mathematics), group that is also a differentiable manifold, such that group multiplication and taking inverses are both differentiable.
A manifold is a space that locally resembles Eucli ...
, which is a subgroup of the general linear group
In mathematics, the general linear group of degree n is the set of n\times n invertible matrices, together with the operation of ordinary matrix multiplication. This forms a group, because the product of two invertible matrices is again inve ...
of all invertible matrices. A triangular matrix is invertible precisely when its diagonal entries are invertible (non-zero).
Over the real numbers, this group is disconnected, having 2^n components accordingly as each diagonal entry is positive or negative. The identity component is invertible triangular matrices with positive entries on the diagonal, and the group of all invertible triangular matrices is a semidirect product
In mathematics, specifically in group theory, the concept of a semidirect product is a generalization of a direct product. It is usually denoted with the symbol . There are two closely related concepts of semidirect product:
* an ''inner'' sem ...
of this group and the group of diagonal matrices
In linear algebra, a diagonal matrix is a matrix in which the entries outside the main diagonal are all zero; the term usually refers to square matrices. Elements of the main diagonal can either be zero or nonzero. An example of a 2×2 diagona ...
with \pm 1 on the diagonal, corresponding to the components.
The Lie algebra
In mathematics, a Lie algebra (pronounced ) is a vector space \mathfrak g together with an operation called the Lie bracket, an alternating bilinear map \mathfrak g \times \mathfrak g \rightarrow \mathfrak g, that satisfies the Jacobi ident ...
of the Lie group of invertible upper triangular matrices is the set of all upper triangular matrices, not necessarily invertible, and is a solvable Lie algebra
In mathematics, a Lie algebra \mathfrak is solvable if its derived series terminates in the zero subalgebra. The ''derived Lie algebra'' of the Lie algebra \mathfrak is the subalgebra of \mathfrak, denoted
: mathfrak,\mathfrak/math>
that consist ...
. These are, respectively, the standard Borel subgroup ''B'' of the Lie group GL''n'' and the standard Borel subalgebra \mathfrak of the Lie algebra gl''n''.
The upper triangular matrices are precisely those that stabilize the standard flag
In mathematics, particularly in linear algebra, a flag is an increasing sequence of subspaces of a finite-dimensional vector space ''V''. Here "increasing" means each is a proper subspace of the next (see filtration):
:\ = V_0 \sub V_1 \sub V_2 \s ...
. The invertible ones among them form a subgroup of the general linear group, whose conjugate subgroups are those defined as the stabilizer of some (other) complete flag. These subgroups are Borel subgroups. The group of invertible lower triangular matrices is such a subgroup, since it is the stabilizer of the standard flag associated to the standard basis in reverse order.
The stabilizer of a partial flag obtained by forgetting some parts of the standard flag can be described as a set of block upper triangular matrices (but its elements are ''not'' all triangular matrices). The conjugates of such a group are the subgroups defined as the stabilizer of some partial flag. These subgroups are called parabolic subgroups.
Examples
The group of 2×2 upper unitriangular matrices is isomorphic
In mathematics, an isomorphism is a structure-preserving mapping or morphism between two structures of the same type that can be reversed by an inverse mapping. Two mathematical structures are isomorphic if an isomorphism exists between the ...
to the additive group
An additive group is a group of which the group operation is to be thought of as ''addition'' in some sense. It is usually abelian, and typically written using the symbol + for its binary operation.
This terminology is widely used with structu ...
of the field of scalars; in the case of complex numbers it corresponds to a group formed of parabolic Möbius transformation
In geometry and complex analysis, a Möbius transformation of the complex plane is a rational function of the form
f(z) = \frac
of one complex number, complex variable ; here the coefficients , , , are complex numbers satisfying .
Geometrically ...
s; the 3×3 upper unitriangular matrices form the Heisenberg group
In mathematics, the Heisenberg group H, named after Werner Heisenberg, is the group of 3×3 upper triangular matrices of the form
: \begin
1 & a & c\\
0 & 1 & b\\
0 & 0 & 1\\
\end
under the operation of matrix multiplication. Elements ''a, b' ...
.
See also
* Gaussian elimination
In mathematics, Gaussian elimination, also known as row reduction, is an algorithm for solving systems of linear equations. It consists of a sequence of row-wise operations performed on the corresponding matrix of coefficients. This method can a ...
* QR decomposition
* Cholesky decomposition
In linear algebra, the Cholesky decomposition or Cholesky factorization (pronounced ) is a decomposition of a Hermitian, positive-definite matrix into the product of a lower triangular matrix and its conjugate transpose, which is useful for eff ...
* Hessenberg matrix
* Tridiagonal matrix
In linear algebra, a tridiagonal matrix is a band matrix that has nonzero elements only on the main diagonal, the subdiagonal/lower diagonal (the first diagonal below this), and the supradiagonal/upper diagonal (the first diagonal above the main ...
* Invariant subspace
References
{{Matrix classes
Numerical linear algebra
Matrices (mathematics)