A triangular matrix is a square matrix whose entries are all zero either below or above its main diagonal. These two cases are called upper triangular and lower triangular, respectively. Triangular matrices are fundamental in linear algebra because their structure makes determinants, eigenvalues, and solutions of linear systems comparatively easy to compute. Many algorithms first transform a general matrix into triangular form and then exploit these properties.
Definition and notation
Let be an matrix over a field, commonly the real numbers or complex numbers.
The matrix is upper triangular if
and lower triangular if
For example,
are upper and lower triangular matrices.
The main diagonal consists of the entries . The definition imposes no requirement that entries on the permitted side of the diagonal be nonzero. In particular, every diagonal matrix is both upper and lower triangular, as are the zero matrix and the identity matrix.
The term is normally used for square matrices. Rectangular analogues are often called upper or lower trapezoidal matrices.
Strict and unit triangular forms
A matrix is strictly upper triangular if
so its diagonal is zero as well. Strictly lower triangular matrices are defined analogously.
A unit upper triangular or unit lower triangular matrix has every diagonal entry equal to . Such matrices are also called unitriangular. “Unit” refers to the diagonal entries, not to orthogonality or unitary structure.
Algebraic properties
Upper triangular matrices of a fixed size are closed under addition, scalar multiplication, and matrix multiplication. The same statements hold for lower triangular matrices.
For upper triangular matrices and , the product satisfies
When , a potentially nonzero summand would require both and , which is impossible. Hence is upper triangular. Its diagonal satisfies
Consequently, upper triangular matrices form an algebra and a vector space of dimension
Strictly upper triangular matrices form a vector space of dimension .
The transpose of an upper triangular matrix is lower triangular, and conversely. The same reversal holds for the conjugate transpose.
Determinant, trace, and invertibility
For any triangular matrix,
Thus a triangular matrix is invertible exactly when every diagonal entry is nonzero.
If is invertible and upper triangular, its inverse is also upper triangular, with
The corresponding statements hold for lower triangular matrices. In particular, the inverse of a unit triangular matrix is unit triangular.
The trace is
Although this trace formula holds for every square matrix, triangular form also exposes the eigenvalues directly.
A triangular matrix’s rank is not, in general, the number of nonzero diagonal entries. For example,
has rank , despite having no nonzero diagonal entries. Rank must be determined from the full matrix structure.
Strict triangularity and nilpotence
Every strictly triangular matrix satisfies
Such a matrix is called nilpotent. Multiplication successively moves potentially nonzero entries farther from the diagonal until none remain.
It follows that is invertible, with the finite expansion
No limiting argument is needed because all subsequent powers vanish.
Solving triangular systems
A system of linear equations with a triangular coefficient matrix can be solved sequentially rather than by a full elimination procedure.
Back substitution
For an upper triangular system
with nonzero diagonal entries, the final equation determines . The remaining unknowns are obtained in reverse order:
This procedure is called back substitution.
For example,
gives
Forward substitution
For a lower triangular system
the equations are solved from top to bottom:
This is forward substitution.
For a dense triangular matrix, either procedure requires arithmetic operations in big-O notation, compared with for standard dense elimination of a general matrix. A unit triangular system requires no division by diagonal entries.
If a diagonal entry is zero, these formulas cannot simply be applied at that step. The system may be inconsistent or may have infinitely many solutions, depending on the other coefficients and the right-hand side.
Eigenvalues and triangularization
For a triangular matrix , the characteristic polynomial, using the convention , is
Its eigenvalues are therefore precisely its diagonal entries, counted with algebraic multiplicity.
Triangularity does not imply diagonalizability. For example,
has the repeated eigenvalue , but only one linearly independent eigenvector.
Similarity to triangular form
A matrix is triangularizable over a field if it is similar over that field to an upper triangular matrix:
for some invertible .
A square matrix over a field is triangularizable over that field if and only if its characteristic polynomial splits into linear factors there. Consequently:
- Every complex square matrix is triangularizable.
- A real square matrix is triangularizable over the real numbers exactly when all its eigenvalues are real.
- A real matrix with nonreal eigenvalues cannot be transformed into a real triangular matrix by similarity.
The Schur decomposition gives a stronger result over the complex numbers:
where is a unitary matrix and is upper triangular. Over the real numbers, the analogous real Schur form is block upper triangular, with and diagonal blocks; the latter represent nonreal conjugate eigenvalue pairs.
Invariant subspaces
Triangular form has a geometric interpretation. If a linear map has an upper triangular matrix in an ordered basis , then each subspace
is invariant under the map. These nested subspaces form a complete invariant flag:
Conversely, a basis adapted to such a flag gives an upper triangular matrix.
Role in matrix factorizations
Triangular matrices occur throughout numerical linear algebra, especially in methods that reduce general problems to triangular solves.
Gaussian elimination and LU decomposition
Gaussian elimination produces an upper triangular matrix by eliminating entries below the diagonal. The elimination multipliers can be stored in a lower triangular matrix, yielding an LU decomposition.
With row pivoting, a common convention is
where is a permutation matrix, is unit lower triangular, and is upper triangular. Solving then reduces to
Once the factors are available, multiple right-hand sides can be handled without repeating the factorization.
QR and Cholesky decompositions
In a QR decomposition,
the factor is upper triangular in the square case, or upper trapezoidal in an appropriate rectangular formulation. This structure is used in linear-system and least-squares algorithms.
For a real symmetric positive definite matrix, the Cholesky decomposition has the form
where is lower triangular with positive diagonal entries. For complex Hermitian positive definite matrices, the corresponding factorization is .
Block triangular matrices
A block upper triangular matrix has zero blocks below its block diagonal:
where the diagonal blocks and are square. They need not themselves be triangular.
Its determinant and characteristic polynomial satisfy
Thus its eigenvalues are those of its diagonal blocks, with multiplicities.
If and are invertible,
Block triangular systems are solved by block forward or back substitution. This allows algorithms to work with groups of variables and use efficient matrix operations within each block.
Numerical considerations and limitations
Triangular structure reduces computational work but does not guarantee that a problem is well conditioned. A triangular matrix can have an arbitrarily large condition number, and errors in its entries or right-hand side may then produce large changes in the solution.
Standard substitution algorithms have strong backward-error properties: under the usual arithmetic model, and excluding overflow and underflow, a computed solution can be interpreted as the exact solution of a nearby triangular system. The size of the forward error still depends on conditioning.
Small diagonal entries can lead to large intermediate values or overflow, but their absolute size alone is not a reliable conditioning test. For example, a nonzero scalar multiple of the identity has condition number in standard induced norms, however small the scalar.
In implementations, the known zero half of a triangular matrix need not be stored explicitly. Unit diagonal entries may also be implicit. When only a solution of is required, direct triangular substitution is generally preferable to explicitly constructing .