Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
Linear algebra is a branch of mathematics that studies vector spaces, also called linear spaces, along with linear functions that input one vector and output another. Such functions are called linear maps and can be represented by matrices if a basis is given. Thus matrix theory is often...
, a triangular matrix is a special kind of square matrix where either all the entries below or all the entries above the main diagonal are zero. A matrix which is conjugate to a triangular matrix is called triangularizable.
In mathematics, a matrix is a rectangular array of numbers, symbols, or expressions. The individual items in a matrix are called its elements or entries. An example of a matrix with six elements isMatrices of the same size can be added or subtracted element by element...
equations with triangular matrices are easier to solve they are very important in numerical analysis
Numerical analysis
Numerical analysis is the study of algorithms that use numerical approximation for the problems of mathematical analysis ....
In linear algebra, LU decomposition is a matrix decomposition which writes a matrix as the product of a lower triangular matrix and an upper triangular matrix. The product sometimes includes a permutation matrix as well. This decomposition is used in numerical analysis to solve systems of linear...
gives an algorithm to decompose any invertible matrix A into two triangular factors: a normed lower triangle matrix L and an upper triangle matrix U.
Description
A matrix of the form
is called lower triangular matrix or left triangular matrix, and analogously a matrix of the form
is called upper triangular matrix or right triangular matrix.
The standard operations on triangular matrices conveniently preserve the triangular form: the sum and product of two upper triangular matrices is again upper triangular. The inverse of an upper triangular matrix is also upper triangular, and of course we can multiply an upper triangular matrix by a constant and it will still be upper triangular. This means that the upper triangular matrices form a subalgebra
Subalgebra
In mathematics, the word "algebra", when referring to a structure, often means a vector space or module equipped with an additional bilinear operation. Algebras in universal algebra are far more general: they are a common generalisation of all algebraic structures...
of the ring of square matrices for any given size. The analogous result holds for lower triangular matrices. Note, however, that the product of a lower triangular with an upper triangular matrix does not preserve triangularity.
Strictly triangular matrix
A triangular matrix with zero entries on the main diagonal is strictly upper or lower triangular. All strictly triangular matrices are nilpotent
Nilpotent matrix
In linear algebra, a nilpotent matrix is a square matrix N such thatN^k = 0\,for some positive integer k. The smallest such k is sometimes called the degree of N....
, and they form a nilpotent Lie algebra, denoted Strictly upper triangular matrices are the derived Lie algebra of the Lie algebra of all upper triangular matrices; symbolically, Strictly upper triangular matrices are the Lie algebra of the Lie group of unitriangular matrices.
In fact, by Engel's theorem, any nilpotent Lie algebra is conjugate to a subalgebra of the strictly upper triangular matrices: a nilpotent Lie algebra is simultaneously strictly upper triangularizable.
Unitriangular matrix
If the entries on the main diagonal are 1, the matrix is called (upper or lower) unitriangular. All unitriangular matrices are unipotent
Unipotent
In mathematics, a unipotent element r of a ring R is one such that r − 1 is a nilpotent element, in other words such that some power n is zero....
. Other names used for these matrices are unit (upper or lower) triangular (of which "unitriangular" might be a contraction), or normed upper/lower triangular (very rarely used). However a unit triangular matrix is not the same as the unit matrix
Identity matrix
In linear algebra, the identity matrix or unit matrix of size n is the n×n square matrix with ones on the main diagonal and zeros elsewhere. It is denoted by In, or simply by I if the size is immaterial or can be trivially determined by the context...
, and a normed triangular matrix has nothing to do with the notion of matrix norm.
Unitriangular matrices form a Lie group, whose Lie algebra is the strictly upper triangular matrices.
Gauss matrix
A Gauss matrix is a special form of a unitriangular matrix, where all of the off-diagonal entries are zero, except for the entries in one column. Such a matrix is also called atomic upper/lower triangular or Gauss transformation matrix. So an atomic lower triangular matrix is of the form
The inverse of an atomic triangular matrix is again atomic triangular. Indeed, we have
i.e., the single column of off-diagonal entries are replaced in the inverse matrix by their additive inverses.
Special properties
A matrix which is simultaneously upper and lower triangular is diagonal
Diagonal matrix
In linear algebra, a diagonal matrix is a matrix in which the entries outside the main diagonal are all zero. The diagonal entries themselves may or may not be zero...
In linear algebra, the identity matrix or unit matrix of size n is the n×n square matrix with ones on the main diagonal and zeros elsewhere. It is denoted by In, or simply by I if the size is immaterial or can be trivially determined by the context...
is the only matrix which is both upper and lower unitriangular.
A matrix which is simultaneously triangular and normal
Normal matrix
A complex square matrix A is a normal matrix ifA^*A=AA^* \ where A* is the conjugate transpose of A. That is, a matrix is normal if it commutes with its conjugate transpose.If A is a real matrix, then A*=AT...
, is also diagonal. This can be seen by looking at the diagonal entries of A*A and AA*, where A is a normal, triangular matrix.
In linear algebra, the determinant is a value associated with a square matrix. It can be computed from the entries of the matrix by a specific arithmetic expression, while other ways to determine its value exist as well...
of a triangular matrix equals the product of the diagonal entries. Since for any triangular matrix A the matrix , whose determinant is the characteristic polynomial
Characteristic polynomial
In linear algebra, one associates a polynomial to every square matrix: its characteristic polynomial. This polynomial encodes several important properties of the matrix, most notably its eigenvalues, its determinant and its trace....
of A, is also triangular, the diagonal entries of A in fact give the multiset
Multiset
In mathematics, the notion of multiset is a generalization of the notion of set in which members are allowed to appear more than once...
of eigenvalues of A (an eigenvalue with multiplicity m occurs exactly m times as diagonal entry).
The variable L is commonly used for lower triangular matrix, standing for lower/left, while the variable U or R is commonly used for upper triangular matrix, standing for upper/right.
Many operations can be performed more easily on triangular matrices than on general matrices. Notably matrix inversion (when possible) can be done by back substitution, avoiding the complications of general Gaussian elimination
Gaussian elimination
In linear algebra, Gaussian elimination is an algorithm for solving systems of linear equations. It can also be used to find the rank of a matrix, to calculate the determinant of a matrix, and to calculate the inverse of an invertible square matrix...
.
The inverse of a triangular matrix is also triangular.
The product of two lower triangular matrices produces a lower triangular matrix.
The product of two upper triangular matrices produces an upper triangular matrix.
Triangularisability
A matrix that is similar to a triangular matrix is referred to as triangularisable. Abstractly, this is equivalent to stabilising 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 stabilises the standard flag.
Any complex square matrix is triangularisable. In fact, a matrix A over a field
Field (mathematics)
In abstract algebra, a field is a commutative ring whose nonzero elements form a group under multiplication. As such it is an algebraic structure with notions of addition, subtraction, multiplication, and division, satisfying certain axioms...
In mathematics, a field F is said to be algebraically closed if every polynomial with one variable of degree at least 1, with coefficients in F, has a root in F.-Examples:...
) 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 stabilises a flag, and is thus triangularisable with respect to a basis for that flag.
In linear algebra, a Jordan normal form of a linear operator on a finite-dimensional vector space is an upper triangular matrix of a particular form called Jordan matrix, representing the operator on some basis...
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 triangularisation, namely, that any square matrix A has a Schur decomposition
Schur decomposition
In the mathematical discipline of linear algebra, the Schur decomposition or Schur triangulation, named after Issai Schur, is a matrix decomposition.- Statement :...
. 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 the (over an algebraically closed field), commuting matrices
Commuting matrices
In linear algebra, a set of matrices A_1,\ldots,A_k is said to commute if they commute pairwise, meaning A_iA_j = A_jA_i for every pair i, j .- Properties :Commuting matrices over an algebraically closed field are simultaneously triangularizable; indeed,...
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
Commuting matrices
In linear algebra, a set of matrices A_1,\ldots,A_k is said to commute if they commute pairwise, meaning A_iA_j = A_jA_i for every pair i, j .- Properties :Commuting matrices over an algebraically closed field are simultaneously triangularizable; indeed,...
. 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
Hilbert's Nullstellensatz
Hilbert's Nullstellensatz is a theorem which establishes a fundamental relationship between geometry and algebra. This relationship is the basis of algebraic geometry, an important branch of mathematics. It relates algebraic sets to ideals in polynomial rings over algebraically closed fields...
: commuting matrices form a commutative algebra over which can be interpreted as a variety in k-dimensional affine space, and the existence of a (common) eigenvalue (and hence a common eigenvector) corresponds to this variety having a point (being non-empty), which is the content of the (weak) 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 triangularisable, 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
Nilpotent
In mathematics, an element x of a ring R is called nilpotent if there exists some positive integer n such that xn = 0....
for all polynomials p in k non-commuting variables, where is the commutator
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:...
; note that for commuting the commutator vanishes so this holds. This was proven in ; a brief proof is given in . One direction is clear: if the matrices are simultaneously triangularisable, then is strictly upper triangularizable (hence nilpotent), which is preserved by multiplication by any or combination thereof – it will still have 0s on the diagonal in the triangularizing basis.
Generalizations
Because the product of two upper triangular matrices is again upper triangular, the set of upper triangular matrices forms an algebra
Associative algebra
In mathematics, an associative algebra A is an associative ring that has a compatible structure of a vector space over a certain field K or, more generally, of a module over a commutative ring R...
. Algebras of upper triangular matrices have a natural generalization in functional analysis
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 and the linear operators acting upon these spaces and respecting these structures in a suitable sense...
In functional analysis, a branch of mathematics, nest algebras are a class of operator algebras that generalise the upper-triangular matrix algebras to a Hilbert space context. They were introduced by John Ringrose in the mid-1960s and have many interesting properties...
The mathematical concept of a Hilbert space, named after David Hilbert, generalizes the notion of Euclidean space. It extends the methods of vector algebra and calculus from the two-dimensional Euclidean plane and three-dimensional space to spaces with any finite or infinite number of dimensions...
s.
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
Trapezoid
In Euclidean geometry, a convex quadrilateral with one pair of parallel sides is referred to as a trapezoid in American English and as a trapezium in English outside North America. A trapezoid with vertices ABCD is denoted...
.
Borel subgroups and Borel subalgebras
The set of invertible triangular matrices of a given kind (upper or lower) forms a group
Group (mathematics)
In mathematics, a group is an algebraic structure consisting of a set together with an operation that combines any two of its elements to form a third element. To qualify as a group, the set and the operation must satisfy a few conditions called group axioms, namely closure, associativity, identity...
In mathematics, a Lie group is a group which is also a differentiable manifold, with the property that the group operations are compatible with the smooth structure...
In mathematics, the general linear group of degree n is the set of n×n invertible matrices, together with the operation of ordinary matrix multiplication. This forms a group, because the product of two invertible matrices is again invertible, and the inverse of an invertible matrix is invertible...
of all invertible matrices; invertible is equivalent to all diagonal entries being invertible (non-zero).
Over the real numbers, this group is disconnected, having 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
Semidirect product
In mathematics, specifically in the area of abstract algebra known as group theory, a semidirect product is a particular way in which a group can be put together from two subgroups, one of which is a normal subgroup. A semidirect product is a generalization of a direct product...
of this group and diagonal entries with on the diagonal, corresponding to the components.
In mathematics, a Lie algebra is an algebraic structure whose main use is in studying geometric objects such as Lie groups and differentiable manifolds. Lie algebras were introduced to study the concept of infinitesimal transformations. The term "Lie algebra" was introduced by Hermann Weyl in the...
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. These are, respectively, the standard Borel subgroup
Borel subgroup
In the theory of algebraic groups, a Borel subgroup of an algebraic group G is a maximal Zariski closed and connected solvable algebraic subgroup.For example, in the group GLn ,...
B of the Lie group GLn and the standard Borel subalgebra of the Lie algebra gln.
The upper triangular matrices are precisely those that stabilize the standard flag. 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 subgroup
Borel subgroup
In the theory of algebraic groups, a Borel subgroup of an algebraic group G is a maximal Zariski closed and connected solvable algebraic subgroup.For example, in the group GLn ,...
s. 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 by 2 upper unitriangular matrices is isomorphic to the additive group
Additive group
An additive group may refer to:*an abelian group, when it is written using the symbol + for its binary operation*a group scheme representing the underlying-additive-group functor...
of the field of scalars; in the case of complex numbers it corresponds to a group formed of parabolic Möbius transformations; the 3 by 3 upper unitriangular matrices form the Heisenberg group.
Examples
The matrix
is upper triangular and
is lower triangular.
The matrix
is atomic lower triangular. Its inverse is
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.
Algorithm
The following is an example implementation of this algorithm in the C# programming language
Programming language
A programming language is an artificial language designed to communicate instructions to a machine, particularly a computer. Programming languages can be used to create programs that control the behavior of a machine and/or to express algorithms precisely....
In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...
performs poorly in C# due to the inefficient handling of non-jagged matrices
Matrix (mathematics)
In mathematics, a matrix is a rectangular array of numbers, symbols, or expressions. The individual items in a matrix are called its elements or entries. An example of a matrix with six elements isMatrices of the same size can be added or subtracted element by element...
in this language. Nonetheless, the method of forward and backward substitution can be highly efficient.
double[] luEvaluate(double[,] L, double[,] U, Vector b)
{
// Ax = b -> LUx = b. Then y is defined to be Ux
int i = 0;
int j = 0;
int n = b.Count;
double[] x = new double[n];
double[] y = new double[n];
// Forward solve Ly = b
for (i = 0; i < n; i++)
{
y[i] = b[i];
for (j = 0; j < i; j++)
{
y[i] -= L[i, j] * y[j];
}
y[i] /= L[i, i];
}
// Backward solve Ux = y
for (i = n - 1; i >= 0; i--)
{
x[i] = y[i];
for (j = i + 1; j < n; j++)
{
x[i] -= U[i, j] * x[j];
}
x[i] /= U[i, i];
}
return x;
}
Applications
Forward substitution is used in financial bootstrapping
Bootstrapping (finance)
Bootstrapping is a method for constructing a fixed-income yield curve from the prices of a set of coupon-bearing products by forward substitution....
In finance, the yield curve is the relation between the interest rate and the time to maturity, known as the "term", of the debt for a given borrower in a given currency. For example, the U.S. dollar interest rates paid on U.S...
Linear algebra is a branch of mathematics that studies vector spaces, also called linear spaces, along with linear functions that input one vector and output another. Such functions are called linear maps and can be represented by matrices if a basis is given. Thus matrix theory is often...
In linear algebra, Gaussian elimination is an algorithm for solving systems of linear equations. It can also be used to find the rank of a matrix, to calculate the determinant of a matrix, and to calculate the inverse of an invertible square matrix...
In linear algebra, a QR decomposition of a matrix is a decomposition of a matrix A into a product A=QR of an orthogonal matrix Q and an upper triangular matrix R...
In linear algebra, the Cholesky decomposition or Cholesky triangle is a decomposition of a Hermitian, positive-definite matrix into the product of a lower triangular matrix and its conjugate transpose. It was discovered by André-Louis Cholesky for real matrices...
In linear algebra, a Hessenberg matrix is a special kind of square matrix, one that is "almost" triangular. To be exact, an upper Hessenberg matrix has zero entries below the first subdiagonal, and a lower Hessenberg matrix has zero entries above the first superdiagonal...
Strictly upper triangular matrices are the derived Lie algebra of the Lie algebra 
of all upper triangular matrices; symbolically, 
Strictly upper triangular matrices are the Lie algebra of the Lie group of unitriangular matrices.
, whose determinant is the characteristic polynomial
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 stabilises the standard flag.
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.
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
over 
which can be interpreted as a variety in k-dimensional affine space, and the existence of a (common) eigenvalue (and hence a common eigenvector) corresponds to this variety having a point (being non-empty), which is the content of the (weak) Nullstellensatz. In algebraic terms, these operators correspond to an algebra representation of the polynomial algebra in k variables.
is simultaneously triangularisable if and only if the matrix 
is nilpotent
is the commutator
the commutator vanishes so this holds. This was proven in ; a brief proof is given in . One direction is clear: if the matrices are simultaneously triangularisable, then 
is strictly upper triangularizable (hence nilpotent), which is preserved by multiplication by any 
or combination thereof – it will still have 0s on the diagonal in the triangularizing basis.
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
on the diagonal, corresponding to the components.
of the Lie algebra gln.
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.
, 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 
.
) 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 
.
