12.1. Matrix Factorizations

When solving a linear algebra problem, matrix factoring is usually the first and most important step. Consider, for example, the available options for solving a system of linearly independent equations of the form \(\mathbf{A}\,\bm{x} = \bm{b}\). For pedagogical reasons, beginning students might be instructed to use Gaussian elimination with an augmented matrix. Computing the inverse of \(\bf{A}\) is not a good option. However, if \(\bf{A}\) is square, then LU decomposition followed by a substitution algorithm works well. If \(\bf{A}\) is over-determined, then a numerically stable strategy is to use the orthogonal QR decomposition. A substitution algorithm can quickly find a solution if the factoring procedure yields a diagonal or triangular system. If a matrix factor is a unitary matrix, the transpose operation finds its inverse.

When elimination procedures are used to factor a matrix, each step of the procedure shifts a matrix element to zero, which is offset by entries in another matrix factor. Multiplication of the factors restores the original matrix. For example, in LU decomposition (\(\mathbf{A} = \mathbf{L\,U}\)), row operations are applied to \(\bf{A}\) to produce the upper triangular \(\bf{U}\). Correspondingly, entries are added to the lower triangular \(\bf{L}\) such that multiplying \(\bf{L}\) and \(\bf{U}\) together yields a product equal to \(\bf{A}\). The objective is to produce triangular factors that can be used with substitution to solve a system of equations (\(\mathbf{A}\,\bm{x} = \mathbf{L\, U}\,\bm{x} = \bm{b}\)).

Orthogonal matrix factoring algorithms use a different strategy. Transformation matrices are designed to change matrix elements to zeros with multiplication. For example, the QR decomposition (\(\mathbf{A} = \mathbf{Q\,R}\)) algorithm sequentially uses Householder transforms, \(\mathbf{H}_i\), that when multiplied to \(\bf{A}\) give zeros below the diagonal of the \(i{\text{th}}\) column. Matrix \(\bf{R}\) starts as \(\bf{A}\) but moves closer to upper triangular form with each procedure on the columns (\(\mathbf{R}_i = \mathbf{H}_i\,\mathbf{R}_{i-1}\)). The product of transposed transformation matrices forms the \(\bf{Q}\) matrix, \(\mathbf{Q}_i = \mathbf{Q}_{i-1}\,\mathbf{H}_i^H\).