4.1210 min read

Permutation and Triangular Matrices

Two special types of matrices arise in Gaussian elimination: permutation matrices and triangular matrices.

A permutation matrix has exactly one 1 in each row and column (all other entries 0). Multiplying by a permutation matrix on the left permutes the rows. Permutation matrices are always invertible, with $P^{-1} = P^T$ .

An upper triangular matrix has all zeros below the diagonal; a lower triangular matrix has all zeros above. Triangular systems can be solved in $O(n^2)$ by forward or back substitution. The product of two triangular matrices (same type) is triangular.

Formal View

Definition 4.12 — Triangular Matrices

U \in \mathbb{R}^{n \times n}

is upper triangular if

u_{ij} = 0

for

i > j

L

is lower triangular if

l_{ij} = 0

for

i < j

. A triangular matrix is invertible iff all diagonal entries are nonzero, and its inverse is also triangular of the same type.

Why This Matters

Triangular matrices are computationally cheap to work with and arise naturally in LU decomposition.

Solving triangular systems costs $O(n^2)$ — much cheaper than $O(n^3)$ for general systems
The Cholesky factorization ( $A = LL^T$ ) for positive definite matrices is a triangular decomposition
LU decomposition (next section) expresses every matrix as a product of triangular matrices

Learning Resources

Triangular matrices and permutations

MIT OpenCourseWare

Permutation matrices and triangular systems.

49 min

Quiz

Question 1

An upper triangular matrix with all nonzero diagonal entries is invertible.

Common Mistakes

Thinking a triangular matrix is always invertible — a zero diagonal entry makes it singular.
Confusing upper and lower triangular when setting up LU factorization.