Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
In mathematics, a triangular matrix is a special kind of square matrix. A square matrix is called if all the entries above the main diagonal 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. By the LU decomposition algorithm, an invertible matrix may be written as the product of a lower triangular matrix L and an upper triangular matrix U if and only if all its leading principal minors are non-zero. 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. 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. This matrix is upper triangular and this matrix is lower triangular. 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. 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.
Olivier Sauter, Stefano Coda, Justin Richard Ball, Alberto Mariani, Matteo Vallar, Filippo Bagnato
Stefano Coda, Justin Richard Ball
Stefano Coda, Stephan Brunner, Oleg Krutkin, Umesh Kumar, Mackenzie Peter-Fulford Van Rossem, Samuele Mazzi