Triangular matrix

In the mathematical discipline of linear algebra, a triangular matrix is a special kind of square matrix where the entries below or above the main diagonal are zero. Because matrix equations with triangular matrices are easy to solve they are very important in numerical analysis. The LU decomposition gives an algorithm to decompose any invertible matrix A into a normed lower triangle matrix L and an upper triangle matrix U.

Contents

1 Definition

2 Notes

3 Examples

4 Application

5 See also

Definition

A matrix

$\mathbf{L}= \begin{bmatrix} l_{1,1} & & & & 0 \\ l_{2,1} & l_{2,2} & & & \\ l_{3,1} & l_{3,2} & \ddots & & \\ \vdots & \vdots & \ddots & \ddots & \\ l_{n,1} & l_{n,2} & \ldots & l_{n,n-1} & l_{n,n} \end{bmatrix}$

is called lower triangular matrix or left triangular matrix, and analogously a matrix of the form

$\mathbf{U} = \begin{bmatrix} u_{1,1} & u_{1,2} & u_{1,3} & \ldots & u_{1,n} \\ & u_{2,2} & u_{2,3} & \ldots & u_{2,n} \\ & & \ddots & \ddots & \vdots \\ & & & \ddots & u_{n-1,n}\\ 0 & & & & u_{n,n} \end{bmatrix}$

is called upper triangular matrix or right triangular matrix.

If the entries on the principal diagonal are 1, the matrix is termed unit upper/lower or normed upper/lower triangular.

The matrix

$\mathbf{L}_n = \begin{bmatrix} 1 & & & & & 0 \\ & \ddots & & & & \\ & & 1 & & & \\ & & l_{n+1,n} & \ddots & & \\ & & \vdots & & \ddots & \\ 0 & & l_{n,n} & & & 1 \\ \end{bmatrix}$

is called atomic lower triangular matrix, with

$\mathbf{U}_n = \begin{bmatrix} 1 & & & l_{1,n} & & 0 \\ & \ddots & & \vdots & & \\ & & \ddots & l_{n-1,n} & & \\ & & & 1 & & \\ & & & & \ddots & \\ 0 & & & & & 1 \\ \end{bmatrix}$

being called atomic upper triangular matrix.

Notes

The identity matrix is a normed upper and lower triangular matrix.

The product of two upper triangular matrices is upper triangular, so the set of upper triangular matrices forms an algebra. Algebras of upper triangular matrices have a natural generalisation in functional analysis which yields nest algebras.

The transpose of a upper triangular matrix is a lower triangular matrix and vice versa.

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. The variable R has the added benefit of being the same initial for the German term for 'right.'

Generally, operations can be performed on triangular matrices within half the time.

Examples

$\begin{bmatrix} 1 & 4 & 2 \\ 0 & 3 & 4 \\ 0 & 0 & 1 \\ \end{bmatrix}$

is upper triangular and

$\begin{bmatrix} 1 & 0 & 0 \\ 2 & 8 & 0 \\ 4 & 9 & 7 \\ \end{bmatrix}$

is lower triangular.

Application

A matrix equation in the form

$\mathbf{L}\mathbf{x} = \mathbf{b}$

$\mathbf{U} \mathbf{x} = \mathbf{b}$

is very easy to solve. The matrix equation Lx= b can be written as a system of linear equations

$\begin{matrix} x_1 & & & & & = & b_1 \\ l_{2,1} x_1 & + & x_2 & & & = & b_2 \\ \vdots & & \vdots & \ddots & & & \vdots \\ l_{m,1} x_1 & + & l_{m,2} x_2 & + \ldots + & x_m & = & b_m \\ \end{matrix}$

which can be solved by the following recursive relation

$\begin{matrix} x_1 & = & b_1 \\ x_2 & = & b_2 - l_{2,1} b_1 \\ & \vdots & \\ x_m & = & b_m - \sum_{i=1}^{m-1} l_{m,i}x_i \end{matrix} :$

A matrix equation with a normed upper triangular matrix U can be solved in an analogous way.