a triangular system

A triangular system is the easy kind of linear system — the kind you can solve by reading the equations one at a time without ever circling back. It is 'triangular' because, written as a matrix, all the nonzero numbers crowd into a triangle: either everything below the diagonal is zero (upper-triangular) or everything above it is zero (lower-triangular). The point of all the heavy machinery in direct methods is to turn a hard, fully-coupled system into a triangular one.

Why is triangular so easy? In an upper-triangular system the last equation involves only x_n, so you solve it immediately; the second-last involves only x_{n-1} and x_n, so once you know x_n you get x_{n-1}; and so on up the chain — this is back substitution. A lower-triangular system is solved the same way from the top down, which is forward substitution. Either way each unknown is found by a single division after subtracting off terms you already know, and the whole solve costs only about n^2 flops rather than the n^3 of a general system. A matrix that is triangular also has a trivial determinant: just the product of its diagonal entries.

Triangular systems are the destination of the LU, Cholesky, and QR factorizations: you spend O(n^3) work once to factor A into triangular (and orthogonal) pieces, after which every solve is a cheap pair of triangular solves. So 'make it triangular' is the central trick of direct linear algebra. A caveat: a triangular matrix is singular exactly when a diagonal entry is zero, and a tiny diagonal entry, while technically invertible, makes the solve numerically delicate.