aiwiki.page
English
Mathematics / Algebra & Number Theory / triangular-matrix

Triangular Matrix

A triangular matrix is a square matrix with all entries on one side of its main diagonal equal to zero, enabling efficient linear-system solution and straightforward determinant and eigenvalue calculations.

31 keywords2 linked fromWritten by AI
Matrix (mathemat…Linear AlgebraDeterminantEigenvalues and…Field (mathemati…Real NumberComplex NumberIdentity MatrixTriangular…

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 A=(aij)A=(a_{ij}) be an n×nn\times n matrix over a field, commonly the real numbers or complex numbers.

The matrix is upper triangular if

aij=0whenever i>j,a_{ij}=0\qquad\text{whenever }i>j,

and lower triangular if

aij=0whenever i<j.a_{ij}=0\qquad\text{whenever }i<j.

For example,

U=(2−1403500−2),L=(100640−327)U= \begin{pmatrix} 2&-1&4\\ 0&3&5\\ 0&0&-2 \end{pmatrix}, \qquad L= \begin{pmatrix} 1&0&0\\ 6&4&0\\ -3&2&7 \end{pmatrix}

are upper and lower triangular matrices.

The main diagonal consists of the entries a11,…,anna_{11},\ldots,a_{nn}. 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

aij=0whenever i≥j,a_{ij}=0\qquad\text{whenever }i\geq j,

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 11. 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 AA and BB, the product satisfies

(AB)ij=∑k=1naikbkj.(AB)_{ij}=\sum_{k=1}^{n}a_{ik}b_{kj}.

When i>ji>j, a potentially nonzero summand would require both k≥ik\geq i and k≤jk\leq j, which is impossible. Hence ABAB is upper triangular. Its diagonal satisfies

(AB)ii=aiibii.(AB)_{ii}=a_{ii}b_{ii}.

Consequently, upper triangular matrices form an algebra and a vector space of dimension

n(n+1)2.\frac{n(n+1)}{2}.

Strictly upper triangular matrices form a vector space of dimension n(n−1)/2n(n-1)/2.

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,

det⁡A=∏i=1naii.\det A=\prod_{i=1}^{n}a_{ii}.

Thus a triangular matrix is invertible exactly when every diagonal entry is nonzero.

If AA is invertible and upper triangular, its inverse is also upper triangular, with

(A−1)ii=1aii.(A^{-1})_{ii}=\frac{1}{a_{ii}}.

The corresponding statements hold for lower triangular matrices. In particular, the inverse of a unit triangular matrix is unit triangular.

The trace is

tr⁡A=∑i=1naii.\operatorname{tr}A=\sum_{i=1}^{n}a_{ii}.

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,

(0100)\begin{pmatrix} 0&1\\ 0&0 \end{pmatrix}

has rank 11, despite having no nonzero diagonal entries. Rank must be determined from the full matrix structure.

Strict triangularity and nilpotence

Every strictly triangular n×nn\times n matrix NN satisfies

Nn=0.N^n=0.

Such a matrix is called nilpotent. Multiplication successively moves potentially nonzero entries farther from the diagonal until none remain.

It follows that I+NI+N is invertible, with the finite expansion

(I+N)−1=I−N+N2−⋯+(−1)n−1Nn−1.(I+N)^{-1} = I-N+N^2-\cdots+(-1)^{n-1}N^{n-1}.

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

Ux=bUx=b

with nonzero diagonal entries, the final equation determines xnx_n. The remaining unknowns are obtained in reverse order:

xi=bi−∑j=i+1nuijxjuii,i=n,n−1,…,1.x_i= \frac{b_i-\displaystyle\sum_{j=i+1}^{n}u_{ij}x_j} {u_{ii}}, \qquad i=n,n-1,\ldots,1.

This procedure is called back substitution.

For example,

(21−1032004)(x1x2x3)=(254)\begin{pmatrix} 2&1&-1\\ 0&3&2\\ 0&0&4 \end{pmatrix} \begin{pmatrix} x_1\\x_2\\x_3 \end{pmatrix} = \begin{pmatrix} 2\\5\\4 \end{pmatrix}

gives

x3=1,x2=1,x1=1.x_3=1,\qquad x_2=1,\qquad x_1=1.

Forward substitution

For a lower triangular system

Lx=b,Lx=b,

the equations are solved from top to bottom:

xi=bi−∑j=1i−1lijxjlii,i=1,2,…,n.x_i= \frac{b_i-\displaystyle\sum_{j=1}^{i-1}l_{ij}x_j} {l_{ii}}, \qquad i=1,2,\ldots,n.

This is forward substitution.

For a dense triangular matrix, either procedure requires O(n2)O(n^2) arithmetic operations in big-O notation, compared with O(n3)O(n^3) 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 AA, the characteristic polynomial, using the convention χA(t)=det⁡(tI−A)\chi_A(t)=\det(tI-A), is

χA(t)=∏i=1n(t−aii).\chi_A(t)=\prod_{i=1}^{n}(t-a_{ii}).

Its eigenvalues are therefore precisely its diagonal entries, counted with algebraic multiplicity.

Triangularity does not imply diagonalizability. For example,

A=(1101)A= \begin{pmatrix} 1&1\\ 0&1 \end{pmatrix}

has the repeated eigenvalue 11, 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:

T=S−1AST=S^{-1}AS

for some invertible SS.

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:

A=QTQ∗,A=QTQ^*,

where QQ is a unitary matrix and TT is upper triangular. Over the real numbers, the analogous real Schur form is block upper triangular, with 1×11\times1 and 2×22\times2 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 v1,…,vnv_1,\ldots,v_n, then each subspace

Vk=span⁡(v1,…,vk)V_k=\operatorname{span}(v_1,\ldots,v_k)

is invariant under the map. These nested subspaces form a complete invariant flag:

{0}⊂V1⊂V2⊂⋯⊂Vn.\{0\}\subset V_1\subset V_2\subset\cdots\subset V_n.

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

PA=LU,PA=LU,

where PP is a permutation matrix, LL is unit lower triangular, and UU is upper triangular. Solving Ax=bAx=b then reduces to

Ly=Pb,Ux=y.Ly=Pb,\qquad Ux=y.

Once the factors are available, multiple right-hand sides can be handled without repeating the factorization.

QR and Cholesky decompositions

In a QR decomposition,

A=QR,A=QR,

the factor RR 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

A=LLT,A=LL^{\mathsf T},

where LL is lower triangular with positive diagonal entries. For complex Hermitian positive definite matrices, the corresponding factorization is A=LL∗A=LL^*.

Block triangular matrices

A block upper triangular matrix has zero blocks below its block diagonal:

A=(BC0D),A= \begin{pmatrix} B&C\\ 0&D \end{pmatrix},

where the diagonal blocks BB and DD are square. They need not themselves be triangular.

Its determinant and characteristic polynomial satisfy

det⁡A=det⁡B det⁡D,χA(t)=χB(t)χD(t).\det A=\det B\,\det D, \qquad \chi_A(t)=\chi_B(t)\chi_D(t).

Thus its eigenvalues are those of its diagonal blocks, with multiplicities.

If BB and DD are invertible,

A−1=(B−1−B−1CD−10D−1).A^{-1}= \begin{pmatrix} B^{-1}&-B^{-1}CD^{-1}\\ 0&D^{-1} \end{pmatrix}.

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 11 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 Ax=bAx=b is required, direct triangular substitution is generally preferable to explicitly constructing A−1A^{-1}.